题目描述
给你n个数
然后对于每一个数 \(a_i\) ,判断是否存在一个 \(a_j\) ，使得 \(a_i \& a_j = 0\)
输入格式
第一行一个数 \(n\)
然后 \(n\) 个整数，表示 \(a_i\)
输出格式
一行，n个整数，表示答案
如果存在，输出1
否则，输出0
样例
【样例输入】
6 1 2 3 5 7 9
【样例输出】
1 1 0 1 0 1
基本思想
一开始我的想法是使用 \(trie\) 树储存所有 01串，然后使用 \(DFS\) 逐个查找。貌似使用了 \(trie\) 树会是查询更高效，实则我们想避开所有 1 ，会使 \(DFS\) 查询变成事实上的穷举。 \(trie\) 树的插入步骤的时间复杂度是 \(O(nL)\) ，但是查询操作仅仅对于每个数而言会有 \(O(2^L)\) ，这与暴力配对没有实质区别。
那么我们考虑是否可以将每个 01串可以符合的预期串预处理出来，也就是处理出它的补集，意即 0010--> 1101，1101 & 0010=0，但是我们在 1101 中删去几个 1 仍然是符合条件的，这就是我们预处理的方向。乍一看这个复杂度还是挺高的，但问题是题目要求我们判断存在，我们预处理出来之后查询是 \(O(1)\) 的，更何况我们从 \(2^{20}\) 向下遍历，我们在补集中删去 1 只会使数变小，得到的新数会向后加入进行再次处理，意思就是说我们不需要考虑枚举要删去多少个 1 ，而只需要考虑删去那个 1 即可。
Code
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int M=1<<20;
int n,m,a[N];
bool ok[M+10];
int main(){ios::sync_with_stdio(false);cin>>n;m=M-1;for(int i=1;i<=n;i++){cin>>a[i];ok[a[i]^m]=true;}for(int i=m;i>=0;i--)if(ok[i]){for(int j=0;j<=20;j++)if(i&(1<<j))ok[i^(1<<j)]=true;//去除1只会变小，会加到后面进行再次处理 }for(int i=1;i<=n;i++){cout<<ok[a[i]]<<" ";}return 0;
}