题解 CF165E 【Compatible Numbers】

__Watcher · 2020-02-13 12:12:49 · 题解

这题是一道高位前缀和的模板题

题目大意：对于每一个 a_i，询问是否有 a_j 使得 a_i\ \&\ a_j=0。若有，输出任意一个 a_j，否则输出 -1。

分析：

对于每一对 a_i\ \&\ a_j=0，若 a_i 与 a_j 的二进制表示中有同一位均为 1，那么 a_i\ \&\ a_j 的这一位也会为 1。因此可以发现，a_j 是 a_i 按位取反后的子集。

实现：

预处理出数组 a 的高维前缀和，每一次询问时先取反，再看取反后子集是否为空。高维前缀和只需存储子集中的任意一个数即可。

代码：

#include<bits/stdc++.h>
using namespace std;
int n, a[1000005], f[1<<22];
int main() {
    cin>>n;
    for(int i=1;i<=n;i++) {
        scanf("%d", &a[i]);
        f[a[i]]=a[i];
    }
    for(int i=0;i<=21;i++) {
        for(int j=0;j<(1<<22);j++) {
            if((j&(1<<i))&&f[j^(1<<i)]) f[j]=f[j^(1<<i)];
        }
    }//高维前缀和
    for(int i=1;i<=n;i++) {
        int b=((1<<22)-1)^a[i];//取反操作
        printf("%d ", f[b]?f[b]:-1);
    }
}