C-Eighty seven(背包+bitset)

浅学了一下bitset，感觉挺妙的，可以进行背包问题的优化

Mr. Fib is a mathematics teacher of a primary school. In the next lesson, he is planning to teach children how to add numbers up. Before the class, he will prepare NN cards with numbers. The number on the ii-th card is a_iai​. In class, each turn he will remove no more than 33 cards and let students choose any ten cards, the sum of the numbers on which is 8787. After each turn the removed cards will be put back to their position. Now, he wants to know if there is at least one solution of each turn. Can you help him?

Input

The first line of input contains an integer t~(t \le 5)t (t≤5), the number of test cases. tt test cases follow.
For each test case, the first line consists an integer N(N \leq 50)N(N≤50).
The second line contains NN non-negative integers a_1, a_2, ... , a_Na1​,a2​,...,aN​. The ii-th number represents the number on the ii-th card. The third line consists an integer Q(Q \leq 100000)Q(Q≤100000). Each line of the next QQ lines contains three integers i,j,ki,j,k, representing Mr.Fib will remove the ii-th, jj-th, and kk-th cards in this turn. A question may degenerate while i=ji=j, i=ki=k or j=kj=k.

Output

For each turn of each case, output 'Yes' if there exists at least one solution, otherwise output 'No'.

题意：给你n个数字，每次拿走里面1到3个数，问你剩下的数里面是否能选出10个数之和为87

思路：因为n只有50，所以可以进行n^3复杂度（约等于，可以优化，不优化会t掉）的预处理，然后01背包的思路，bitset优化，因为是二进制位所以可以很有效的减少时间复杂度

#include <bits/stdc++.h>
#include <bitset>
using namespace std;
const int N=55;
int a[N];
bitset<90> s[11];
int ff[N][N][N];
int n,m;
int solve(int x,int y ,int z)
{
    for(int i=0;i<=10;i++) s[i].reset();//将s[i]每一位全部变成0
    s[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        if(i==x||i==y||i==z||a[i]>87) continue;
        for(int j=10;j>0;j--)
        {
            s[j]|=(s[j-1]<<a[i]);//异或相当于加上a[i]
        }
    }
    if(s[10][87]!=0)
    return 1;
    else
    return 0;
}
int main()
{
    int t;
    int x,y,z;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int x=1;x<=n;x++)
            for(int y=x;y<=n;y++)
               for(int z=y;z<=n;z++)
               {
                  int f=solve(x,y,z);
                  if(f==1) ff[x][y][z]=1;
                  else ff[x][y][z]=0;
               }
                  
        
        scanf("%d",&m);
        while(m--)
        {
            int b[10];
            scanf("%d %d %d",&b[1],&b[2],&b[3]);
            sort(b+1,b+4);//必须排序
            if(ff[b[1]][b[2]][b[3]]==1)
            printf("Yes\n");
            else
            printf("No\n");
        }
    }
    return 0;
}