图片说明
图片说明

  • 题意：
  • 给你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;
}

```