2019牛客暑期多校训练营（第九场）

D 超大背包折半搜索

从n个数中找出若干个数字使它们的和为给定的s，输出一个01序列

1 <= n <= 36， 0 <= s < 9 * 10 ^ 18，  0 < ai < 2 * 10 ^ 17

折半搜索

处理出前半边每种取法的和（最多2^18种情况），对于后半边，计算当前情况的和，然后在set中查找有没有sum-res这个值。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll sum;
ll a[37];
map<ll,int>f;//2^18不超过int int 2^31-1 long long 2^63-1
set<ll>ss;
int main(){
    scanf("%d %lld",&n,&sum);
    for (int i=0;i<n;i++){
        scanf("%lld",&a[i]);
    }
    int p=n/2, q=n-p;//36=18+18
    for(int i=0;i<(1<<p);++i){//2^p种可能
        ll res=0;
        for(int j=0;j<p;++j) if( i&(1<<j) ) res+=a[j]; //a[0],a[1],……,a[p-1]
        ss.insert(res);
        f[res]=i;
    }
    for(int i=0;i<(1<<q);++i){
        ll res=0;
        for(int j=0;j<q;++j) if( i&(1<<j) ) res+=a[p+j];
        if(ss.count(sum-res)){
            int x=f[sum-res];
            for(int j=0;j<p;++j) printf("%d",(bool)(x&(1<<j)));
            for(int j=0;j<q;++j) printf("%d",(bool)(i&(1<<j)));
            puts("");
            return 0;
        }/*else{
            ss.insert(res);
            f[res]=i+p;
        }*/ //一定有
    }
    return 0;
}