鏈接：https://ac.nowcoder.com/acm/contest/889/D
來源：牛客網

Amy asks Mr. B problem D. Please help Mr. B to solve the following problem.

Amy wants to crack Merkle–Hellman knapsack cryptosystem. Please help it.

Given an array {ai} with length n, and the sum s.
Please find a subset of {ai}, such that the sum of the subset is s.

For more details about Merkle–Hellman knapsack cryptosystem Please read
https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem
https://blog.nowcoder.net/n/66ec16042de7421ea87619a72683f807
Because of some reason, you might not be able to open Wikipedia.
Whether you read it or not, this problem is solvable.
輸入描述:
The first line contains two integers, which are n(1 <= n <= 36) and s(0 <= s < 9 * 1018)
The second line contains n integers, which are {ai}(0 < ai < 2 * 1017).

{ai} is generated like in the Merkle–Hellman knapsack cryptosystem, so there exists a solution and the solution is unique.
Also, according to the algorithm, for any subset sum s, if there exists a solution, then the solution is unique.
輸出描述:
Output a 01 sequence.

If the i-th digit is 1, then ai is in the subset.
If the i-th digit is 0, then ai is not in the subset.
示例1
輸入
復制
8 1129
295 592 301 14 28 353 120 236
輸出
復制
01100001
說明
This is the example in Wikipedia.
示例2
輸入
復制
36 68719476735
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 2147483648 4294967296 8589934592 17179869184 34359738368
輸出
復制
111111111111111111111111111111111111
卡了好久這個題，做出來之后才想起來原來之前學校校賽的時候出過類似的題目，淚目！！
要是直接做的話，2^36肯定會超時，那么我們變換一下，求一下這個序列的前一半的所有組合的值，總共 2^18中情況，并且把路徑記錄下來。剩下的一半找出來之后，二分查找能否組成m。然后輸出路徑就行。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=2e6+100; struct node{ll sum;string s;bool operator <(const node &a)const{return a.sum>sum;} }p[maxx]; ll a[maxx],b[maxx]; int n,cnt,flag=0;ll m;void dfs(int pos,int top,ll sum,string s) {if(pos==top){p[++cnt].sum=sum;p[cnt].s=s;return ;}dfs(pos+1,top,sum,s+"0");dfs(pos+1,top,sum+a[pos],s+"1"); } void dfs1(int pos,int top,ll sum,string s) {if(flag) return ;if(pos==top){//if(s=="111111111111111111") cout<<sum<<endl;int x=lower_bound(b+1,b+1+cnt,m-sum)-b;if(b[x]+sum==m) {cout<<p[x].s<<s<<endl;flag=1;}return;}dfs1(pos+1,top,sum,s+"0");dfs1(pos+1,top,sum+a[pos],s+"1"); } int main() {while(~scanf("%d%lld",&n,&m)){cnt=0;flag=0;for(int i=0;i<n;i++) scanf("%lld",&a[i]);dfs(0,n/2,0,"");sort(p+1,p+1+cnt);for(int i=1;i<=cnt;i++) b[i]=p[i].sum;dfs1(n/2,n,0,"");} }

努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的Knapsack Cryptosystem（2019牛客多校折半查询）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。