本文共 827 字，大约阅读时间需要 2 分钟。

题意

给出$n$个数$a_i$,为每个$a_i$找到一个$a_j$使得$a_i\&a_j==0$,若不存在输出$-1$

其中$n,a_i$均小于$4\ast 10^6$

SOSDP

因为$sosdp$求的是$f[mask]=\sum _{i\&mask=i}{a}_i$

现在只需要把定义换一下,$f[mask]$装的是某个是$mask$子集的数字

那么对每个$a_i$来说,需要找到某个$a_j$和$a_i$完全没有交集

转化一下,就是$a_j$是$a_i$补集的子集

所以答案为$f[\sim a_i]$

再说一下$f$数组的初始化

即当所有二进制都和$mask$相同时的答案,$f[mask]=mask$

前提是$mask$这个数字存在,否则仍然无法作为答案

#include 
   
    using namespace std;const int mx = 1<<22;int n,a[mx],f[mx];int main(){
   	scanf("%d",&n);	for(int i=1;i<=n;i++)	scanf("%d",&a[i] ),f[a[i]] = a[i];	for(int i=0;i<22;i++) 	for(int j=0;j
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/112526912 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！