传送题目
看了半个多小时的题解才搞明白，一下题解为自己的心得
参考博客（这两个讲的很详细）：
参考一
参考二
题意：有一个长度有n的整数序列，你要在这个序列中选择一个前缀和后缀，前后缀不想交，前后缀任何一方都可以为空，问你前缀异或值与后缀异或值的异或最大是多少？
比如 一组数 1 2 3 4 5 6 你可以选择前缀为1 2，前缀异或和为3 选择后缀为4 5 6，后缀异或和为7
（前缀异或和）与（后缀异或和）异或值为4，但此时4并不是最大情况，求出最大情况
思路：
首先讲个小例题：
给一个数 a，还有一堆数，怎么在这一堆数中找出一个数 b，a 和 b 的异或值最大？
最暴力的方法无疑是（老办法） 枚举，枚举每一个b，但这样肯定不行~~（不然我写这个博客干什么）~~ ，想想计算机的本质是啥？对，二进制。我们把a与这堆数转化成二进制，把后面这堆数装进一个字典树，当然要从最高位装，比如这堆数是123456，如图
回到这个题：
首先这些n个数组成一个区间w，w的全部异或结果是定值K,所以问题可以改成在区间w中取连续一段区间m，m的异或结果为X，m的前部分就成为区间w的前缀，后半部分就是区间w的后缀。
我们知道相同的数异或为零，那么X与K异或，重复的那部分区间异或后为零，就相当于是我们题目所求的
，所以就是求什么情况下X xor K最大。
发现现在的情况和一开始讲的例题很像了吧，我们假设有个Y，Y与K的每一个二进制相异，我们就要让X尽可能接近Y。
怎么实现呢？也是建一个字典树，将f[i]放进去（f[i]=a[1] ^ a[2] ^ a[3] ^ …^ a[i]）,那么f[i]^f[j]=a[i+1] ^ a[i+2] ^ … ^aj可以表示i+1到j这段区间的异或值。
我们枚举区间m的结尾，每次用一个f[i]去匹配一个f[k]，使得f[k]^f[i]的值在高位上尽可能去接近Y，这样就相当于选出区间[k+1,i]de异或值作为X，每次在[1,i]区间内匹配出来一个最佳区间后，不断更新答案。
看懂了吗？这些神奇的操作，巧妙利用字典树（工具人石锤）来匹配。
(太晚了就不重新打代码了，借用下参考一的代码)
//范围是10的12次方，我们就将每个数固定为40位
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define rep(i,j,k) for(int i = j; i <= k; i++ )
#define Rrep(i,j,k) for(int i = j; i >= k; i-- )
#define Clean(x,y) memset(x,y,sizeof(x))
int n;
LL a[100009];
LL temp;
LL ans;
LL p[45];
int aim[45];
int Next[1000000][2];
int len;
void init()
{
Clean(Next,0);
len = 0;
}
void insert(LL t)
{
int now = 0;
int k;
Rrep(i,39,0)
{
if ( p[i] & t ) k = 1;
else k = 0;
if ( !Next[now][k] ) Next[now][k] = ++len;
now = Next[now][k];
}
}
LL query(LL t)
{
int now = 0;
LL ans = 0;
int k;
Rrep(i,39,0)
{
if ( p[i] & t ) k = 1;
else k = 0;
if ( ( aim[i] && Next[now][1-k] ) || ( !aim[i] && Next[now][k] ) )
{
ans+=p[i];
now = aim[i]==1?Next[now][1-k]:Next[now][k];
}
else now = aim[i]==0?Next[now][1-k]:Next[now][k];
}
return ans;
}
int main()
{
p[0] = 1;
rep(i,1,40) p[i] = p[i-1]<<1;
while(scanf("%d",&n)==1)
{
a[0] = 0;
ans = 0;
rep(i,1,n)
{
scanf("%I64d",&temp);
a[i] = temp ^ a[i-1];
}
ans = max(ans,a[n]);
rep(i,0,39)
if ( a[n] & p[i] ) aim[i] = 0; //计算Y
else aim[i] = 1;
init();
insert(a[0]);
rep(i,1,n)
{
insert(a[i]);
ans = max(ans,query(a[i]));
}
cout<<ans<<endl;
}
return 0;
}
京公网安备 11010502036488号