当前位置: 首页 > 工具软件 > Sausage > 使用案例 >

CodeForces-282E(Sausage Maximization)

吕胤
2023-12-01

题意:给你一个 n 个整数的数组,你可以把它分成三段 ( 任意一段可以为空,满足 l+mid+r=n 就行 ),求一种划分方法,使得 l ,r 内的所有值异或和最大

 

分析: n<=1e5,枚举两个中间划分点肯定会T,我们知道异或值即二进制的同一位上不同则为 1,相同则为 0 ,则为了异或和最大,对于一个确定的值,我们要找与它异或和最大的值,就可以从二进制最高位开始,每一位找与它不同的数,找到了就选,找不到那只能选择一样的,这样选择出的结果肯定是最优的,由此,我们可以用前缀异或和做01字典树,然后枚举后缀异或和,并通过字典树找到和它异或和最大的前缀异或和(反过来也可以)

 

代码:

#include<cstdio>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;

typedef long long ll;
const int N = 1e5+10;

ll n;
ll nxt[N*50][2],cnt;
ll pre[N],suf[N];
ll s[N];

void insert(ll v)
{
	int p=0;
	for(int i=63;i>=0;i--)
	{
		int id=((v>>i)&1);
		if(!nxt[p][id]) nxt[p][id]=++cnt; 
		p=nxt[p][id];
	}
} 

ll find(ll v)
{
	int p=0;
	ll ans=0;
	for(int i=63;i>=0;i--)
	{
		int id=((v>>i)&1);
		if(nxt[p][id^1])  //这一位上不同的值是否存在
		{
			p=nxt[p][id^1];
			id^=1;
		}
		else p=nxt[p][id];
		ans+=((1ll*id)<<i);
    }
	return ans^v;
}

int main()
{
	scanf("%I64d",&n);
	cnt=0;
	memset(nxt,0,sizeof(nxt));
	pre[0]=0,suf[n+1]=0;
	for(int i=1;i<=n;i++) scanf("%I64d",&s[i]);
	for(int i=1;i<=n;i++) pre[i]=pre[i-1]^s[i];
	for(int i=n;i>=1;i--) suf[i]=suf[i+1]^s[i];
	ll ans=0,tmp=0;
	for(int i=0;i<=n;i++)
    {
    	insert(pre[i]);
    	tmp=find(suf[i+1]);
    	ans=max(ans,tmp);
	}
	printf("%I64d\n",ans);
} 

 

 类似资料:

相关阅读

相关文章

相关问答