Knapsack Cryptosystem【折半+查找】

链接：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 ***** 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

题目大意：
先输入一个数字$n$n，代表有一个大小为$n$n的数组$(1\le n \le 36)$(1≤n≤36)，再输入一个数字$s$s，下面一行输入$n$n个数字，要从这$n$n个数字里面选取任意个数字使其和等于$s$s，通过输出一串长度为$n$n的01字符串来表示选或不选。

解题思路：
首先想到的是枚举所有选择的情况，但发现其时间复杂度已经到达了$2^{36}$236，明显会超时，因此想到折半的方法，将其时间复杂度降为$2^{18}$218，接近$1e6$1e6，也就是将数组分为两部分，枚举前半部份所有的选择情况，将其和存在一个数组中，同理处理后半部分，后面判断其和是否能组成$s$s，仅需枚举前半部分的所有情况，通过用 $s-$s−前半部分的和 ,查找其在后半部分是否存在即可。

代码：

//#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int maxn = (int)1e5 + 5;
const ll mod = 1e9+7;
ll arr[40];
struct node1
{
    ll num;
    int id;
}sum_qian[1001000];
struct node2
{
    ll num;
    int id;
}sum_hou[1001000];
bool cmp1(node1 a,node1 b) {
    return a.num<b.num;
}
bool cmp2(node2 a,node2 b) {
    return a.num<b.num;
}
ll get_sum(int id,int len) {
	ll sum=0;
	while(id) {
		if(id&1) {
			sum+=arr[len];
		}
		id>>=1;
		len++;
	}
	return sum;
}
int main() 
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    #endif
    //freopen("out.txt", "w", stdout);
    //ios::sync_with_stdio(0),cin.tie(0);
    int n;
    ll s;
   	cin>>n>>s;
    rep(i,1,n) {
    	cin>>arr[i];
    }
    int nape=n/2;
    for(int i=0;i<(1<<nape);i++) {
    	sum_qian[i].num=get_sum(i,1);
        sum_qian[i].id=i;
    }
    int len_qian=(1<<nape);
  	int t1=nape;
    int start=nape+1;
    nape=n-nape;
    for(int i=0;i<(1<<nape);i++) {
    	sum_hou[i].num=get_sum(i,start);
        sum_hou[i].id=i;
    }
    int len_hou=(1<<nape);
    int t2=nape;
    sort(sum_qian,sum_qian+len_qian,cmp1);
    sort(sum_hou,sum_hou+len_hou,cmp2);
    int qian=-1,hou=-1;
    for(int i=0;i<len_qian;i++) {
    	ll nape;
        if(s>=sum_qian[i].num)
            nape=s-sum_qian[i].num;
        else 
            continue;
    	int l=0,r=len_hou;
    	int id=-1;
    	while(r-l>1) {
    		int mid=(r+l)>>1;
    		if(sum_hou[mid].num==nape) {
    			id=sum_hou[mid].id;
    			break;
    		}
    		else if(sum_hou[mid].num>nape) {
    			r=mid;
    		}
    		else {
    			l=mid;
    		}
  		}
    	if(id!=-1) {
    		qian=sum_qian[i].id;
    		hou=id;
    		break;
    	}
    }
    if(qian!=-1&&hou!=-1) {
    	for(int i=1;i<=t1;i++) {
    		cout<<(qian&1);
    		qian>>=1;
    	}
    	for(int i=1;i<=t2;i++) {
    		cout<<(hou&1);
    		hou>>=1;
    	}
    	cout<<endl;
    }
    return 0;
}