Description
给定数列 \(a[]\),对每个 \(a[i]\) 找到任意一个 \(a[j]\) 使得 \(a[i] \& a[j]=0\),无解则 \(-1\)。
Solution
考虑将数装入桶 \(b[]\) 中并计算高维前缀和,那么求 \(a[i]\) 对应的 \(a[j]\) 只需要查询 \(b[j \oplus mask]\) 即可,其中 \(mask=2^{22}-1\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = (1<<22)+5;
int a[N],b[N],n;
signed main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[a[i]]=a[i];
}
for(int i=0;i<1<<22;i++)
{
for(int j=0;j<22;j++)
{
b[i|(1<<j)]=max(b[i|(1<<j)],b[i]);
}
}
int mask=(1<<22)-1;
for(int i=1;i<=n;i++)
{
if(b[a[i]^mask])
{
cout<<b[a[i]^mask]<<" ";
}
else
{
cout<<-1<<" ";
}
}
}