题目链接

Statement

Solution

看到数据范围$a_i\le 10^6$，首先想到$DP$若考虑11011，它包含随便一位1变0的数因此我们从大到小枚举每个插入的数，将它随便一位^成0状态转移式为$d{p}_j={\sum }_{i=j}^{10^6}d{p}_{i}j\subseteq i$然而有一个问题例如枚举到7时枚举了3和5，但枚举5时也算了3，出现了重复因此我们应该优先枚举位，再枚举数 #include <cstdio> const int N=1e6; int n,m,dp[N+10]; int main() { int x; scanf("%d%d",&n,&m); while(n--) scanf("%d",&x),dp[x]=1; for(int i=0;i<20;i++) for(int j=N;j;j--) if(dp[j]&&(j>>i&1)) dp[j^(1<<i)]+=dp[j]; while(m--) scanf("%d",&x),puts(dp[x]?"yes":"no"); }