每日一题 小M和天平 题解

提供一种新做法，理论复杂度更快，我们用bitset加速维护
发现一共只有三种可能，放左边放右边和不放
我们初始设定一个sum以防负数，然后左右移位就可以了
代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define DB double
#define M 20200
int n,a[M],Q;
bitset<M>B,tmp;

int main(){
    while(scanf("%d",&n)!=EOF){
        int all=0; 
        for(int i=1;i<=n;i++) scanf("%d",&a[i]),all+=a[i];
        B.reset(),B[all]=true;
        for(int i=1;i<=n;i++) tmp=B,B|=(B<<a[i]),B|=(B>>a[i]);
        scanf("%d",&Q);
        while(Q--){
            int x; scanf("%d",&x);
            if(x>all) puts("NO");
            else puts((B[all+x]||B[all-x])?"YES":"NO");
        }
    }return 0;
}