[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;

}

巴特西

[note]一类位运算求最值问题

[note]一类位运算求最值问题

最新文章

热门文章