[牛客暑期多校第九场][折半搜索]D-Knapsack Cryptosystem

发布于 2019-08-16  887 次阅读


第一次写博客...本场比赛爆0了...写写这一道签到题
给定最多36个数字和sum 问从中选出一些数字可以组成sum 问选出哪些数字可以组成 输出01串 0代表不选1代表选
思路 折半搜索 将n分为前后两部分 前半部分枚举所有情况 这个地方枚举利用了2进制 i从0(全不选) 一直枚举到(1<<n/2)-1(即01111111...)就是前半部分全选 枚举完之后将前半部分所有的和存入set和map(貌似可以用unorder_map,好像更快) set用于后半部分求和的时候搜索用 map用来寻找和这个和所对应的i(枚举的方法)
之后再看后半部分 同理 枚举情况 不过这次是枚举完一种情况就去set里搜一下 如果搜得到 就从Map中直接调出第一种枚举的方法 之后输出就可以了

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pi;
int n, p, q;
set<ll> s;
map<ll, int>f;
ll a[36], sum;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    p = n / 2;//分两半
    q = n - p;//另一半
    cin >> sum;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < (1 << p); i++) {//比如100000000代表一半  从0开始枚举一半的所有状态
        ll ret = 0;
        for (int j = 0; j < p; j++) {
            if (i & (1 << j)) {//如果i上这位为1 那么加上去
                ret += a[j];
            }
        }
        s.insert(ret);//存进set
        f[ret] = i;
    }
    for (int i = 0; i < (1 << q); i++) {//枚举另一半
        ll ret = 0;
        for (int j = 0; j < q; j++) {
            if (i & (1 << j)) {
                ret += a[j + p];//后半部分
            }
        }
        //每算完一次 就去s中查找一次
        if (s.find(sum - ret) != s.end()) {//如果找到了
            int x = f[sum - ret];
            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("");
            break;
        }
    }
    return 0;
}

愿风指引你的道路,愿你的刀刃永远锋利。