CodeForces-282E(Sausage Maximization)

题意：给你一个 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);
}