[note]一类位运算求最值问题
给定一些数,让你从中选出两个数a,b,每次询问下列中的一个
1.a and b的最大值
2.a xor b的最大值
3.a or b的最大值
神仙们都是FWT,小蒟蒻只好orz
首先三种问题的思路都是从高位往低位贪心
- 对于xor,直接枚举每个数Trie树上贪心
- 对于and,如果可选集合中有大于等于两个数当前位为1,那么答案这一位也是1,并把这一位为0的数删去
- 对于or,先维护一个高维前缀和,枚举每一个数,如果某一位为0,我们就贪心的看能不能补上1,
相当于询问是否存在某个数满足前面的要求并且这一位为1,
如果这一位是1,显然我们在这位放0限制作用更小.
复杂度都是\(nlog\)值域
不过预处理高位前缀和似乎是\(log\)值域×值域
#include<bits/stdc++.h>
using namespace std;
const int _=1e5+5;
int re(){
int x=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*w;
}
int T,n,c,ans,tot;
int a[_],ch[2][_*20];
bool ban[_],vis[1<<21];
void solve_and(){
memset(ban,0,sizeof(ban));
for(int i=20;~i;i--){
int cnt=0;
for(int j=1;j<=n;j++)
if(!ban[j]&&a[j]>>i&1)cnt++;
if(cnt<2)continue;ans|=1<<i;
for(int j=1;j<=n;j++)
if(a[j]>>i&1^1)ban[j]=1;
}
}
void insert(int x){
int u=0;
for(int i=20;~i;i--){
int k=x>>i&1;
if(!ch[k][u])ch[k][u]=++tot;
u=ch[k][u];
}
}
int query(int x){
int res=0,u=0;
for(int i=20;~i;i--){
int k=x>>i&1^1;
if(!ch[k][u])u=ch[k^1][u];
else u=ch[k][u],res|=1<<i;
}
return res;
}
void solve_xor(){
tot=0;
memset(ch,0,sizeof(ch));
for(int i=1;i<=n;i++)insert(a[i]);
for(int i=1;i<=n;i++)ans=max(ans,query(a[i]));
}
void solve_or(){
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)vis[a[i]]=1;
for(int i=1<<20;~i;i--)
for(int j=0;j<=20;j++)
if(vis[i]&&i>>j&1)vis[i^(1<<j)]=1;
for(int i=1;i<=n;i++){
int res=0,sum=0;
for(int j=20;~j;j--){
sum|=1<<j;
if(a[i]>>j&1)continue;
if(vis[res|(1<<j)])res|=1<<j;
else sum^=1<<j;
}
ans=max(ans,sum);
}
}
int main(){
freopen("maximum.in","r",stdin);
freopen("maximum.out","w",stdout);
T=re();
while(T--){
n=re(),c=re();ans=0;
for(int i=1;i<=n;i++)a[i]=re();
if(c==1)solve_and();
if(c==2)solve_xor();
if(c==3)solve_or();
printf("%d\n",ans);
}
return 0;
}