牛客小白月赛23H——奇怪的背包问题增加了

网址：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;
} 

打卡第13天，在家里的学习的效率虽然不如学校，但是家里自己的自由度也更高。继续加油！！！