题目描述

样例

input: 2 2 3 7 4 9 output: yes no

分析

看到位运算，想到状压。 对于一个集合中的数，1的数量比它少(指2进制)的数肯定是包含在内的。 所以只要将每个元素进行扩展，然后询问的时候只要查一下桶就可以$O(n)$解决了。 扩展的时候用记忆化解决就可以了。具体看注释吧。

代码

#include<bits/stdc++.h> #define ll long long using namespace std; const int MAXN=1e6+10; int t[MAXN],dp[MAXN],maxn=0; void dfs(int x){//表示对于x，进行扩展 if(x==0) return;//如果没有1了，那就不能扩展 if(t[x]==1) return;//如果x已经被放进桶里了，那么之前肯定已经对于x扩展过了 //所以不用继续扩展 t[x]=1;//扔进桶里 for(int i=0;i<20;i++){//枚举位数 if((x>>i)&1){//如果第i位是1，那么可以将这一位的1改成0，然后扩展 dfs(x^(1<<i));//将第i位改成0，递归 } } } int main() { int n,m,x; scanf("%d%d",&n,&m); memset(t,0,sizeof(t)); for(int i=1;i<=n;i++) scanf("%d",&x),dfs(x);//每个元素都扩展一遍 while(m--){ scanf("%d",&x); if(t[x]) puts("yes"); else puts("no"); } }

END

google=咕噜咕噜