网址：https://ac.nowcoder.com/acm/contest/4784/H
题目描述
有一个容量为2^30的背包，和m件物品，第i件物品的体积为c_i，你需要从中选出若干件，使得选出的物品的体积恰好等于背包容量。这些物品有一个奇怪的特性，那就是c_i = 2^ki，其中0<=ki<30，即所有c_i都是2的幂。
输入描述:
第一行，是一个正整数T(1≤T≤100000)，表示接下来要输入T组测试数据
接下来有T测试数据的输入，对于每组测试数据，输入格式如下：
第一行，一个整数m(1≤m≤100000,∑m≤10^5)
第二行，用空格隔开的m个非负整数，第i个数字是ki(0≤ki<30)
输出描述:
依次输出T行，按照输入数据的顺序依次给出每组测试数据的答案，对于一组测试数据：
如果存在一种符合条件的方案，则输出一个长度为m的01串，从前往后的第i位如果是1表示原序列中第i个物品被选中装进背包，为0则表示这个物品不被选中。
如果不存在符合条件的方案，请输出impossible
示例1
输入
2
4
29 1 28 28
7
0 0 1 2 3 4 15
输出
1011
impossible
题解：
这里要明白2^30=2^29+2^29.2^29=2^28/+2^28,....2^1=2^0+2^0；
所以只需要将所有的输入数据按照从小到大的顺序(pow(2,ki))进行排列，然后从后向前进行遍历相加，知道所加之和等于2^30为止，记录相加过的所有ki即可。
AC代码：
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int a[100005];
int b[100005];
int c[40];
int main(){
int t,m;
cin>>t;
int maxn=pow(2,30);
while(t--){
cin>>m;
memset(c,0,sizeof(c));
for(int i=0;i<m;i++) cin>>a[i],b[i]=a[i];
sort(a,a+m);
int sum=0;
for(int i=m-1;i>=0;i--){
sum+=pow(2,a[i]);
c[a[i]]++;
if(sum==maxn) break;
}
if(sum!=maxn){
cout<<"impossible"<<endl;
continue;
}
for(int i=0;i<m;i++){
if(c[b[i]]) cout<<1,c[b[i]]--;
else cout<<0;
}
cout<<endl;
}
return 0;
} 
京公网安备 11010502036488号