CF165Etj

FiraCode · 2022-07-30 11:27:43 · 题解

题解思路：

他让我们找到一个 a_i \& a_j = 0。 那么对于 a_i = 1 那么 a_j = 0。 若 a_i = 0 那么 a_j = 0 或者 a_j = 1。 那么 a_j 必须是 ~a_i 的子集，其中 ~ 表示取反。 那么我们就是要求 a_j \& i = a_j 并且 j 最小。 那么我们令 f_{a_j} = j。 然后我们找到一个 g_i = \min_{i \& j = j}\{f_j\}。 那么这个就很像字集和问题，只要把字集和换成求最小值就可以了。

AC CODE：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (1 << 22) + 10;
const int M = 22;
int n;
int f[N], a[N];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < (1 << M); ++i)
        f[i] = n + 1;
    for (int i = 1; i <= n; ++i) {
        int x;
        scanf("%d", &x);
        a[i] = x;
        f[x] = min(f[x], i);
    }
    for (int i = 0; i < M; ++i)
        for (int j = 0; j < (1 << M); ++j) {
            if (j & (1 << i))
                f[j] = min(f[j], f[j - (1 << i)]);
        }
    for (int i = 1; i <= n; ++i) {
        int x = (1 << M) - 1 - a[i];
        printf("%d%c", (f[x] > n) ? -1 : a[f[x]], " \n"[i == n]);
    }
    return 0;
}