[CF165E] Compatible Numbers

题面

给定数组 \(a[1..n]\) , 对其中的每一个数 \(a[i]\) , 找到并输出数组中与之相容的数 \(a[j]\) , 即满足 \(a[i] \& a[j] = 0\) , 无解则输出 \(-1\).

分析

首先思考 \(a[i]\) 对应的解集是怎样的

• 对 \(a[i]\) 取反, 即将 1 变成 0, 0 变成 1, 取反后的结果必然与 \(a[i]\) 相容
• 取反之后的数, 将其中任意的 1 变成 0, 也会与 \(a[i]\) 相容. 比如 \(1011010_{2}\) 取反得到 \(0100101_{2}\) , 则 \(0000000_{2}, 0100100_{2}\) 都是符合题意的解. (如果 0 和 1 表示集合中的元素是否存在的话, 可以记为 \(0100100_{2} \subseteq 0100101_{2}\))
• 我们只需要找到数组 \(a\) 中属于解集的数

新建数组 \(res[1..N]\) , 并且 \(res[t]\) 满足 \(res[t] \subseteq t\) 和 \(res[t] \in a\) . 可以借鉴高维前缀和的思想来求 \(res\) 数组.

for (int i = 0; i < K; ++i) {
  for (int mask = 0; mask < (1 << K); ++mask) {
    // mask: ...1... -> ...0...
    if (mask & (1 << i) && res[mask ^ (1 << i)] != -1) {
      res[mask] = res[mask ^ (1 << i)];
    }
  }
}

代码

#include <cstring>
#include <iostream>
const int N = 1e6 + 5;
const int K = 22;
int a[N];
int res[(1 << K) + 5];

int main() {
  int n;
  std::cin >> n;
  std::memset(res, -1, sizeof(res));
  for (int i = 1; i <= n; ++i) {
    std::cin >> a[i];
    res[a[i]] = a[i]; 
  }

  for (int i = 0; i < K; ++i) {
    for (int mask = 0; mask < (1 << K); ++mask) {
      if (mask & (1 << i) && res[mask ^ (1 << i)] != -1) {
        res[mask] = res[mask ^ (1 << i)];
      }
    }
  }

  for (int i = 1; i <= n; ++i) {
    std::cout << res[((1 << K) - 1) ^ a[i]] << " ";
  }
  return 0;
}