我们定义A“包含”B的概念是A&B=B，其中 & 是位运算中的“按位与”。
现在给出一个集合Q，这个集合 n 个正整数，m 次询问。每次询问给出一个数字 x，请回答集合 Q 中是否有一个数字包含 x。
1 ≤ n ≤ 1 0 5 , 1 ≤ m ≤ 1 0 5 , 1 ≤ x , a i ≤ 1 0 6 1≤n≤10^5 ,1≤m≤10^5,1≤x,a_i≤10^6 1≤n≤105,1≤m≤105,1≤x,ai≤106
使用dp. 设能被包含的数的dp值为1,不能的为0. 所以可从大到小枚举,得 i f ( d p [ i ] & & ( i & ( 1 < < j ) ) ) d p [ i − ( 1 < < j ) ] = 1 ; if(dp[i]\ \&\&\ (i\ \&\ (1<<j))) \ dp[i-(1<<j)]=1; if(dp[i] && (i & (1<<j))) dp[i−(1<<j)]=1; 初始化即读入的 a i a_i ai的dp值为1.
#include<bits/stdc++.h> using namespace std; int dp[1000010]; int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ int x; scanf("%d",&x); dp[x]=1; } for(int i=1000000;i>=0;i--){ for(int j=0;j<20;j++){ if(dp[i]&&((1<<j)&i)) dp[i^(1<<j)]=1; } } while(m--){ int x; scanf("%d",&x); dp[x]?printf("yes\n"):printf("no\n"); } return 0; }