2017Nowcoder Girl初赛重现赛
题目总体不算难。
但是DP太弱。状压写不来。
我还是有点菜。
总体体验的话，就是数据量小，你尽管暴力。
A
打表以后 ，upper_bound 查找一下即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100005];
int main()
{
for(int i=1;i<=100000;i++)
{
a[i]=(ll)i*i;
}
ll n;
cin>>n;
int t = upper_bound(a+1,a+100000,n)-a;
//cout<<t<<endl;
cout<<a[t-1]<<endl;
return 0;
}
B
N可以得到 奇数，G可以得到偶数，给定n ，倒推回去就可以
#include <bits/stdc++.h>
using namespace std;
char ch[]= {'N','G'};
vector<int>v;
int main()
{
int n;
cin>>n;
while(n)
{
if(n%2==0)
{
v.push_back(1);
n=(n-2)/2;
}
else
{
v.push_back(0);
n=(n-1)/2;
}
}
int len = v.size();
for(int i=len-1;i>=0;i--)
{
printf("%c",ch[v[i]]);
}
printf("\n");
return 0;
}
C 从左往后搜索，模拟交换即可
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+50;
const int mod=1e9+7;
int a[maxn];
int n;
typedef long long ll;
ll change(int x)
{
for(int i=x+1;i<=n;i++)
{
swap(a[i],a[i-1]);
if(a[i]!=i) return i-x;
}
return 0;
}
int main()
{
//int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
ll ans=0;
for(int i=1;i<=n;i++)
{
if(a[i]==i) ans +=change(i);
}
cout<<ans<<endl;
return 0;
}
D
n 只有10 ，暴力每一种选法，判断删去最小数能否成立，选择其中数目最多的即可
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define sc(x) scanf("%d",&x)
using namespace std;
int n,s;
int p[20];
int a[20];
int main()
{
cin>>n>>s;
for(int i=0;i<n;i++)
{
cin>>p[i];
}
int ans=0;
for(int i=1;i<(1<<n);i++)
{
bitset<11>ch(i);
int mmin=100000;
int cnt=0;
int tmp=0;
for(int j=0;j<n;j++)
{
if(ch[j]==1)
{
mmin = min(mmin,p[j]);
tmp +=p[j];
cnt++;
}
}
if(tmp-mmin<s&&tmp>=s) ans = max(ans,cnt);
}
cout<<ans<<endl;
return 0;
}
E题
状压dp
对于 k>=5的情况，显然选择每个状态的最大值即可
但是对于k<5的情况
首先，我们可以将k小于5的情况 分解
假设 k=4
那么我们可以取1个含有5种属性的最大值，或者两个拼成5种属性的最大值，或者3个、4个
那么，我们枚举每一种拼法。在这种拼法下，取求得含有指定种属性值的最大的装备
然后将其拼凑在一起即可
dp[i][j] 表示 状态i 下，j个子集组合起来的最大值
对于每一种状态 u，v
i= u|v
dp[i][j]=max(dp[i][j],dp[u][j−1]+dp[v][1])
#include <bits/stdc++.h>
#define cl(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=1e5+50;
typedef long long ll;
ll a[maxn][6];
ll r[6];
ll dp[1<<5][6];
ll ans=0;
int main()
{
int n,k;
cin>>n>>k;
rep(i,1,n) rep(j,1,5)
{
cin>>a[i][j];
r[j]=max(r[j],a[i][j]);
}
if(k>=5)
{
ans = r[1]+r[2]+r[3]+r[4]+r[5];
cout<<ans<<endl;;
return 0;
}
else
{
dp[0][0]=0;
ans=0;
for(int i=0; i<(1<<5); i++)
{
bitset<5>ch(i);
rep(j,1,n)
{
ll tmp = 0;
rep(k,0,4)
{
if(ch[k]!=0) tmp+=a[j][k+1];
}
dp[i][1]=max(dp[i][1],tmp);
}
ans = max((ll)dp[i][1],ans);
}
rep(v,2,k)
{
rep(i,0,31) rep(j,0,31)
{
if(!(i&j))
{
dp[i|j][v] = max(dp[i|j][v],dp[i][v-1]+dp[j][1]);
ans = max(dp[i|j][v],ans);
}
}
}
cout<<ans<<endl;
}
return 0;
}
F
简单dp
类似背包
dp[i][j]表示前i种物品 共j颗珠子的方案数
dp[i][j]+=dp[i−1][j−k](li≤k≤ri)
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=1e5+50;
typedef long long ll;
ll dp[30][150];
ll r[30],l[30];
int main()
{
int n,m;
cin>>n>>m;
rep(i,1,n) cin>>l[i]>>r[i];
dp[0][0]=1;
rep(i,1,n) rep(j,0,m)
{
rep(k,l[i],r[i])
if(j-k>=0)
dp[i][j]+=dp[i-1][j-k];
//cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
}
cout<<dp[n][m]<<endl;
return 0;
}
CVTE公司福利 269人发布
