D 折半查找

Link: https://ac.nowcoder.com/acm/contest/41761/D

AC：

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 100;
int n,s;
int a[N];
bool flag = false;
unordered_map<int, int> mp;

void pr(int t){
	int ans[N], cnt = 0;
	while(t > 1){
		ans[cnt++] = t & 1;
		t >>= 1;
	}
	while(cnt--){
		printf("%d", ans[cnt]);
	}
}

void dfs1(int now, int ed, int vu, int sta){
	if(now == ed){
		mp[vu] = sta;
		return;
	}
	dfs1(now + 1, ed, vu, (sta << 1));
	if(vu + a[now] <= s) dfs1(now + 1, ed, vu + a[now], (sta << 1) + 1);
}

void dfs2(int now, int ed, int vu, int sta){
	if(flag) return;
	if(now == ed){
		if(mp[s - vu] != 0){
			int t = mp[s - vu];
			pr(t);
			pr(sta);
			flag = 1;
		}
		return;
	}
	dfs2(now + 1, ed, vu, (sta << 1));
	if(vu + a[now] <= s) dfs2(now + 1, ed, vu + a[now], (sta << 1) + 1);
}

signed main(){
	cin>>n>>s;
	for(int i = 1; i <= n; i++){
		cin>>a[i];
	}
	dfs1(1, n / 2 + 1, 0, 1);
	dfs2(n / 2 + 1, n + 1, 0, 1);
}