传送门
题意：给出一个长度为n的数组a，m次查询，每次输入一个数x，问是否能从a中找出一个a[i]， 使得 x&a[i]=x。 分析：一开始是打算用字典树储存每一个a[i]对应二进制位数为1所在的位置，瞎搞了一下发现 好像想不通。然后就看到了一种很迷解法，先预处理出 标记每个 a[i]&tmp(tmp<a[i]). 这样就可以做到 O(m) 的查询了。 #include <map> #include <cmath> #include <stack> #include <queue> #include <string> #include <vector> #include<cstring> #include <stdio.h> #include <iostream> #include <algorithm> #define INF 0x3f3f3f3f using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn=1e6+5; int n,m; bool vis[maxn]; int main() { scanf("%d%d",&n,&m); for(int i=1,x;i<=n;i++){ scanf("%d",&x); if(vis[x]) continue; int tmp=x; while (tmp){ vis[tmp]=true; tmp=(tmp-1)&x; } } int x; while (m--){ scanf("%d",&x); if(vis[x]) printf("yes\n"); else printf("no\n"); } return 0; }