校园微网站建设方案ppt,广告优化师工作内容,一些做的好的网站,口碑好的丹徒网站建设传送题目 看了半个多小时的题解才搞明白#xff0c;一下题解为自己的心得 参考博客#xff08;这两个讲的很详细#xff09;#xff1a; 参考一 参考二 题意#xff1a;有一个长度有n的整数序列#xff0c;你要在这个序列中选择一个前缀和后缀#xff0c;前后缀不想交一下题解为自己的心得 参考博客这两个讲的很详细 参考一 参考二 题意有一个长度有n的整数序列你要在这个序列中选择一个前缀和后缀前后缀不想交前后缀任何一方都可以为空问你前缀异或值与后缀异或值的异或最大是多少 比如 一组数 1 2 3 4 5 6 你可以选择前缀为1 2前缀异或和为3 选择后缀为4 5 6后缀异或和为7 前缀异或和与后缀异或和异或值为4但此时4并不是最大情况求出最大情况 思路 首先讲个小例题 给一个数 a还有一堆数怎么在这一堆数中找出一个数 ba 和 b 的异或值最大 最暴力的方法无疑是老办法 枚举枚举每一个b但这样肯定不行~~不然我写这个博客干什么~~ 想想计算机的本质是啥对二进制。我们把a与这堆数转化成二进制把后面这堆数装进一个字典树当然要从最高位装比如这堆数是123456如图根据异或规则不同为一所以我们要使a与b异或最大就要让b尽可能与a不同a已经给定b已经形成字典树我们就从字典树root开始尽量找出于a当前位置不同的数直到找到最低位为止那么这样找到的b满足条件。
回到这个题 首先这些n个数组成一个区间ww的全部异或结果是定值K,所以问题可以改成在区间w中取连续一段区间mm的异或结果为Xm的前部分就成为区间w的前缀后半部分就是区间w的后缀。 我们知道相同的数异或为零那么X与K异或重复的那部分区间异或后为零就相当于是我们题目所求的 所以就是求什么情况下X xor K最大。 发现现在的情况和一开始讲的例题很像了吧我们假设有个YY与K的每一个二进制相异我们就要让X尽可能接近Y。 怎么实现呢也是建一个字典树将f[i]放进去f[i]a[1] ^ a[2] ^ a[3] ^ …^ a[i],那么f[i]^f[j]a[i1] ^ a[i2] ^ … ^aj可以表示i1到j这段区间的异或值。 我们枚举区间m的结尾每次用一个f[i]去匹配一个f[k]使得f[k]^f[i]的值在高位上尽可能去接近Y这样就相当于选出区间[k1,i]de异或值作为X每次在[1,i]区间内匹配出来一个最佳区间后不断更新答案。 看懂了吗这些神奇的操作巧妙利用字典树工具人石锤来匹配。 (太晚了就不重新打代码了借用下参考一的代码)
//范围是10的12次方我们就将每个数固定为40位
#includebits/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] ) ){ansp[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; //计算Yelse aim[i] 1;init();insert(a[0]); rep(i,1,n){insert(a[i]);ans max(ans,query(a[i]));}coutansendl;}return 0;
}
