【题解】小信的特工行动

经验分享区
1

原题意大致为给出n给数，让你对这n个数进行选择并相加使得最后答案等于s，以二进制数的形式（选了输出1，不选输出0）输出。
很容易想到 dfs，但 dfs 的时间复杂度为O(2^n)，所以我们考虑折中搜索。
我们可以将原数组 b 分成两个部分，分别 dfs，这样复杂度就变为了 O(2^(n/2))，第一次搜索的结果用哈希表保存所有结果，第二次搜索的时候检查哈希表内是否有满足条件的数。
由于要对2^64取模，所以使用 unsigned long long

code

ull n,b[114],s,vis[114];
unordered_map<ull,string> mp;
string res;
void dfs(int x,ull sum){
	if(x==n/2) {
        mp[sum]=res.substr(0,n/2);
        return;
    }
    res[x]='0';
    dfs(x+1,sum);
    res[x]='1';
    dfs(x+1,sum+b[x]);
}
void dfs2(int x,ull sum){
    if (x==n){
        if(mp.count(s-sum))cout<<mp[s-sum]+res.substr(n/2,n-n/2),exit(0);
        return;
    }
    res[x]='0';
    dfs2(x+1,sum);
    res[x]='1';
    dfs2(x+1,sum+b[x]);
}