Compatible Numbers
思路
对于一个数 \(x\)，如果想要构造一个数 \(y\) 使得 \(x \& y = 0\) 那么显然对于 \(x\) 的每一位：
- 如果当前位是 0，那么 \(y\) 这一位可以填 \(1,0\)
- 如果当前位是 1，那么 \(y\) 这一位可以填 \(0\)
那么对于用这种方式构造出来的数的一些位是可以互换的，而互换后的数显然也是满足要求的，所以问题就变成了，\(a_1,a_2,a_3,\cdots\cdots,a_n\)，通过一些位的互换是否可以换成用上面的方法构造出来的数。
对于两个用上面的方法构造出来的数，如果较小的那个能够用互换来换成，那么较大的那个肯定也可以换出来（只要将一些本来是 0 的位置换成 1 即可，不会有后效性），那么我们就可以判断说通过上面大方法构造出来的数的最大值，是否可以被 \(a_1, a_2, a_3, \cdots\cdots,a_n\) 中的任意一个数通过一些位的互换换出，那么要构造出最大值其实就是按位取反。
然后对于每一个数，我们把它看成二进制，搜索每一位是否换，然后换后得出的新数标记是否存在，最后对每个数按位取反后判是否曾经换出来了即可。
然后搜索部分是可以用 dp 来实现的，所以将搜索换成 dp 即可。
code
点击查看代码
#include <iostream>
using namespace std;
const int MaxN = 1e6 + 10, MaxM = 9e6 + 10;
int dp[MaxM], a[MaxN], n;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i], dp[a[i]] = a[i];
}
for (int i = 0; i < MaxM; i++) {
if (dp[i]) {
for (int j = 0; (1 << j) < MaxM; j++) {
if (!(i & (1 << j)) && (i | (1 << j)) < MaxM) {
dp[(i | (1 << j))] = max(dp[(i | (1 << j))], dp[i]);
}
}
}
}
for (int i = 1; i <= n; i++) {
cout << (dp[(1 << 22) - 1 - a[i]] ? dp[(1 << 22) - 1 - a[i]] : -1) << " ";
}
return 0;
}