2017Nowcoder Girl初赛重现赛（C++全解）

本文主要是介绍2017Nowcoder Girl初赛重现赛（C++全解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最近看到的，刷一下来练手
https://ac.nowcoder.com/acm/contest/315#question
平方数

    int main(){cin>>n;ll q=sqrt(n);if(q*q<=n)cout<<q*q<<endl;return 0;}

勇气获得机

int main(){cin>>n;stack<char>ans;while(n>0){if(n&1){ans.push('N');n=(n-1)/2;}else{ans.push('G');n=(n-2)/2;}}while(!ans.empty()){cout<<ans.top();ans.pop();}return 0;
}

排列
就是位置和数值相同的表示要被交换，注意相邻都相同时可以少换一次

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
const int mod=1e9+7;
const int maxn=1e5;
ll n,b;
int a[maxn+5];
int main(){cin>>n;int sum=0;for(int i=0;i<n;i++){cin>>a[i];if(a[i]==i+1){sum++;if(i>0&&a[i-1]==i){sum--;a[i]=i;}}}cout<<sum<<endl;return 0;
}

打车
n就10，暴力，排序，贪心求和，然后从最大的里面去减去不可以用的钱

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
const int mod=1e9+7;
const int maxn=1000;
ll n,b;
int a[maxn+5];
int main(){cin>>n>>b;int sum=0;for(int i=0;i<n;i++)cin>>a[i];sort(a,a+n);int i;sum=0;for(i=0;i<n;i++){if(sum<b){sum+=a[i];if(sum>=b)break;}}//cout<<sum<<endl;int ans=i+1;for(int j=i-1;j>=0;j--){if((sum-a[j])>=b){sum-=a[j];ans--;}}cout<<ans<<endl;return 0;
}

勇敢的妞妞
以下是看了别人的代码意识到的
k>=5时，一定能找到最优
k<=5时
我们不对武器做要求，我们对属性做要求
属性有5位，把属性位对答案有贡献的枚举出来，这里状压枚举子集
dp【状态子集】【贡献这个子集的武器数】
先求出任意一个武器在这个属性位状态下的值，然后对所有武器求一个最值
然后dp【状态子集】【0】
ans=dp【状态全集】【武器数i】
=max(dp,dp【状态子集】【前几个贡献者i-1】+dp【状态子集的补集】【当前贡献者】)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
const int mod=1e9+7;
const int maxn=1e4;
ll a[maxn+5][6];
ll dp[35][6];//35的状态下有6个武器  的最大值
int main(){ll n,m;cin>>n>>m;if(m>5)m=5;for(int i=1;i<=n;i++){for(int j=0;j<5;j++){cin>>a[i][j];}}mem(dp,0);ll ans=0;///预处理子集最值for(int i=0;i<(1<<5);i++){for(int j=1;j<=n;j++){ll cnt=0;for(int k=0;k<5;k++){if(i&(1<<k))cnt+=a[j][k];}dp[i][1]=max(dp[i][1],cnt);//一个武器会产生的最大值}ans=max(ans,dp[i][1]);///!!!(一个武器也可以最优)}///找补集for(int i=2;i<=m;i++){for(int j=0;j<(1<<5);j++){for(int k=0;k<(1<<5);k++){if(j&k)continue;//j,k不互补dp[j|k][i]=max(dp[j|k][i],dp[j][i-1]+dp[k][1]);ans=max(ans,dp[j|k][i]);}}}cout<<ans<<endl;return 0;
}

美丽的项链
我看数据范围，以为是dfs就行，事实证明，我天真了。
dp[i][j]:到第i种珠子，用掉j个位置的方案数

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
const int mod=1e9+7;
const int maxn=1000;
ll n,m;
int l[25];
int r[25];
ll dp[25][105];
int main(){cin>>n>>m;for(int i=1;i<=n;i++)cin>>l[i]>>r[i];mem(dp,0);for(int i=1;i<=n;i++){if(i==1){for(int p=l[i];p<=r[i];p++)dp[i][p]=1;}else for(int j=0;j<=m;j++){for(int p=l[i];p<=r[i];p++){if(j>=p)dp[i][j]+=dp[i-1][j-p];}}}cout<<dp[n][m]<<endl;return 0;
}

这篇关于2017Nowcoder Girl初赛重现赛（C++全解）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---