2019牛客暑期多校训练营（第九场）D-Knapsack Cryptosystem（思维+子集和）

>传送门<
题意：给你一个有n个元素的数组，一个sum，让你找到数组的子集使得子集元素和等于sum，保证只有一个解决方案。

（其中1≤n≤36，0≤ sum<9*10¹⁸，0<ai<2*10¹⁷）

思路：写这题的时候队友直接搜子集，然后我就满脸？？？2³⁶，老哥你确定不会爆？于是天真的我发现和背包不是很像么，然后就用背包写，写完后发现W是9*10¹⁸，此时我的内心对我自己也是？？？

所以暴搜肯定是不行的，有一个很巧妙的思路，就是将数组分成两个区域，18个元素我们完全可以暴力枚举子集，并放到set里，然后再对右区域枚举子集，O(1)检查sum - 子集和是否存在就行了，完美~

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e5 + 10;

ll a[maxn];

set<ll> s;

map<ll, ll> mp;

int main()

{

    int n, p, q;

    ll sum;

    scanf("%d %lld", &n, &sum);

    for(int i = 0; i < n; ++i) scanf("%lld", &a[i]);

    p = n / 2; q = n - p;

    //先枚举左区间

    for(int i = 0; i < (1 << p); i++) {

        ll tmp = 0;

        for(int j = 0; j < p; j++) {

            if(i & (1 << j))

                tmp += a[j];

        }

        s.insert(tmp);

        mp[tmp] = 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[p + j];

        }

        //找到答案了

        if(s.find(sum - ret) != s.end()) {

            ll x = mp[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)));

            printf("\n");

            return 0;

        }

    }

    return 0;

}

这题用到了这些知识点：子集的生成，set的用法，map的用法

巴特西

2019牛客暑期多校训练营（第九场）D-Knapsack Cryptosystem（思维+子集和）

最新文章

热门文章