牛客小白月赛23h奇怪的背包问题增加了，二进制
奇怪的背包问题增加了
https://ac.nowcoder.com/acm/contest/4784/H
加数ci<2^30，所以如果加数和大于2^30，则一定有组合可以构成2^30
注意这里和一般加法不同，一般的如234+567，而这里就好比 只允许加上1,10,100。。。而不允许加上567这样的数字
然后就是找到这样的组合，这里从大到小排列这些ci，初始sum=2^30，如果ci<sum就取，sum-=ci
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
struct Good{
ll k,no;
};
Good good[N];
ll t,m,ans[N],sum,v,bag;
bool cmp(Good a,Good b){
return a.k>b.k;
}
int main(){
cin>>t;
for(int i=0;i<t;i++){
memset(ans,0,sizeof ans);
sum=0;
cin>>m;
for(int j=0;j<m;j++){
cin>>good[j].k;
good[j].no=j;
sum+=1<<good[j].k;
}
if(sum<(1<<30)) cout<<"impossible"<<endl;
else {
sort(good,good+m,cmp);
bag=1<<30;
for(int j=0;j<m;j++){
v=1<<good[j].k;
if(v<=bag){
bag-=v;
ans[good[j].no]=1;
}
}
for(int j=0;j<m;j++){
cout<<ans[j];
}cout<<endl;
}
}
return 0;
} 创作不易，点赞再走
投递字节跳动等公司10个岗位 >
