欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2019牛客暑期多校训练营(第九场)

程序员文章站 2024-03-20 18:42:16
...

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;
}

 

相关标签: 折半搜索