2020牛客NOIP赛前集训营-提高组（第二场）B包含

题目

传送门

题目描述

我们定义$A$“包含”$B$的概念是$A\&B=B$，其中$\&$是位运算中的“按位与”。

现在给出一个集合$Q$，这个集合$n$个正整数，$m$次询问。每次询问给出一个数字$x$，请回答集合$Q$中是否有一个数字包含$x$。

输入描述

第一行输入两个正整数$n$，$m$，意义如题面所示。接下来一行输入$n$个正整数，描述集合$Q$中的数字，其中第$i$个数字为$a_i$。然后有$m$行，每行给出一个正整数$x$，代表询问。

输出描述

对于每一个询问，输出$yes$或$no$表示答案。

分析

这题比较水，暴力也能过，这里不再赘述 讲讲正经思路：采取$dp$

我们可以用$dp$进行预处理，$dp[i]$代表对于询问的数字为$i$时的答案。($1$代表包含，$0$代表不包含)

首先，不难得出$A\&A=A$，因此对于输入的所有数字$a[i]$可得 $dp[a[i]]=1$ 然后我们倒着枚举值域，对于任意一个数字$x$，如果$dp[x]=1$，那么去除其中任意一位二进制上的$1$，对应的$dp$值仍为$1$ 用$O(nlogn)$的时间进行预处理，之后就可以$O(1)$回答每次查询了

代码

#include <bits/stdc++.h> using namespace std; const int maxn=1e6+666; int n,m,x,a[maxn],dp[maxn]; void Sc() { for(int j=0;j<20;j++) for(int i=maxn;i>=0;i--) if(dp[i]&&(i>>j&1)) dp[i-(1<<j)]=1; } int main() { scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",a+i),dp[a[i]]=1; Sc(); while(m--) { scanf("%d",&x); if(dp[x]) puts("yes"); else puts("no"); } }

----原创文章，仅供参考