牛客多校第九场 D

• 题意：
• 给你n个数，和一个数s
• 问你用哪几个数相加可以构成s，如果存在，只有唯一解，如果不存在输出-1
• 题解：
• 折半搜索，额，第一次见
• 赶紧记下来吧，模板
• 代码：

  #include <bits/stdc++.h>
  using namespace std;
  #define ll long long
  set<ll> s;
  map<ll,int> mp;
  ll a[40],sum;
  int n;
  int main()
  {
    cin>>n;
    int p=n/2;
    int q=n-p;
    cin>>sum;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<(1<<p);i++)
    {
        ll cnt = 0;
        for(int j=0;j<p;j++)
            if(i&(1<<j))
                cnt += a[j];
        s.insert(cnt);
        mp[cnt] = i;
    }
    for(int i=0;i<(1<<q);i++)
    {
        ll cnt = 0;
        for(int j=0;j<q;j++)
            if(i&(1<<j))
                cnt += a[j+p];
        if(s.find(sum - cnt) != s.end()){
            int x = mp[sum-cnt];
            for(int j=0;j<p;j++)
                printf("%d",(bool)(x&(1<<j)));
            for(int j=0;j<q;j++)
                printf("%d",(bool)(i&(1<<j)));
            cout<<endl;
            return 0;
        }
    }
    return 0;
  }
  

```