From Google Earth
题意很简单，是说有一个排好序的升序正整数序列，现在给出总和s，让你从数列中挑出若干个数，使得它们相加后总和为s。
第一反应就是dfs，因为之前做过几乎一模一样的题，且这题数据范围很小，数列最长才36。但事实证明，dfs会T飞......无论怎么剪枝都没用。
正确解法是，将数列折半，对于前一半，状压枚举出每一种选取情况的总和，将它们存入一个map里面。对于后一半，依然是状压枚举每种选取情况的总和，记作\(s_i\)，在算出\(s_i\)后，二分lower_bound()在map中找\(s-s_i\)，如果找到了，就可以输出结果了，答案就是此时后半的选取情况以及\(s-s_i\)对应的前半选取情况。
代码如下：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define lowbit(x) (x&(-x))
#define IOS std::ios::sync_with_stdio(false)
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll s,arr[45];
int p,q,n;
map<ll,int> mp;
int to[(1<<18)+10];
void init()
{
int msk=2;
to[1]=0;
for(int i=1;i<=17;i++){
to[msk]=i;
msk<<=1;
}
}
void show(int mskp,int mskq)
{
for(int i=0;i<p;i++)
printf("%d",1&(mskp>>i));
for(int i=0;i<q;i++)
printf("%d",1&(mskq>>i));
printf("\n");
}
int main()
{
init();
scanf("%d %lld",&n,&s);
for(int i=0;i<n;i++)
scanf("%lld",&arr[i]);
p=(n>>1);
q=n-p;
for(int i=0;i<(1<<p);i++){
ll tmp=0;
for(int j=i;j;j-=(lowbit(j)))
tmp+=arr[to[lowbit(j)]];
/*
lowbit(x)返回x最右端的1所表示的数.
如,9 = 1001 ,则lowbit(9) = 1 = 1;
8 = 100 ,则lowbit(8) = 100 = 8.
*/
mp[tmp]=i;
}
bool flag=0;
for(int i=0;i<(1<<q);i++){
ll tmp=0;
for(int j=i;j;j-=lowbit(j))
tmp+=arr[to[lowbit(j)]+p];
auto it=mp.lower_bound(s-tmp);
if(it->first+tmp==s){
show(it->second,i);flag=1;
break;
}
}
if(!flag) printf("-1\n");
return 0;
}