526互联

Compatible Numbers

发布时间 2023-08-07 18:35:26作者: yabnto

Compatible Numbers

思路

对于一个数 \(x\)，如果想要构造一个数 \(y\) 使得 \(x \& y = 0\) 那么显然对于 \(x\) 的每一位：

  1. 如果当前位是 0，那么 \(y\) 这一位可以填 \(1,0\)
  2. 如果当前位是 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;
}