本文主要是介绍BZOJ4260 Codechef REBXOR【01字典树】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
4260: Codechef REBXOR
https://www.lydsy.com/JudgeOnline/problem.php?id=4260
时间限制: 10 Sec 内存限制: 256 MB
题目描述
输入
输入数据的第一行包含一个整数N，表示数组中的元素个数。
第二行包含N个整数A1,A2,…,AN。
输出
输出一行包含给定表达式可能的最大值。
样例输入
5
1 2 3 1 2样例输出
6提示
满足条件的(l1,r1,l2,r2)有：(1,2,3,3)，(1,2,4,5)，(3,3,4,5)。
对于100%的数据，2 ≤ N ≤ 4*10^5，0 ≤ Ai ≤ 10^9。
思路
先说明几个数组的作用
a[]存放原数组
pre[]存放异或前缀
suf[]存放异或后缀
dp[i]存放前i个数中任意区间异或的最大值
求两个不相交的区间，两区间异或后的和最大，设第二个区间的左端点为m，则第一个区间在[1,m-1)内，第二个区间的左端点为m，右端点在[m,n]内，其中n表示数的个数，我们枚举m，即m取值为[2,n]， 在m确定的情况下求最大的值，当两个数分别取最大时，它们的和最大，此时dp[]就排上用处了，在m确定的情况下，第一个区间的最大异或值为dp[m-1]（即前m-1个数中任意区间异或的最大值）。
如何求以元素a[i]为结束元素的区间的异或最大值？由于异或操作有这么个性质
异或前缀： pre[i]^pre[j]=a[i+1]^a[i+2]^...^a[j] (i<j)
异或后缀：suf[i]^suf[j]=a[i]^a[i+1]^...^a[j-1] (i<j)
我们求以元素a[i]为结束元素的区间的异或最大值，使用异或前缀pre[]，我们将per[0],pre[1],..,pre[i-1]插入到01字典树中，然后查找与a[i]以后后值最大的数即可。同理可使用异或后缀suf[] 求以元素a[i]为开始元素的区间的异或最大值。
通过上面的分析，这道问题就好解决了，先用pre[]和01字典树求出dp[]，然后枚举第二个区间的左端点m，求第二个区间的异或最大值就是求以a[m]为开始元素的区间的异或最大值，使用01字典树即可。
C++代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>using namespace std;const int N=400500;int a[N],trie[32*N][2],dp[N],pre[N],suf[N];
int tot;//插入操作
void insert(int x)
{int rt=0;for(int i=31;i>=0;i--){int c=(x>>i)&1;if(!trie[rt][c]) trie[rt][c]=++tot;rt=trie[rt][c];}
}//查询操作
int query(int x)
{int rt=0,m=0;for(int i=31;i>=0;i--){int c=(x>>i)&1;if(trie[rt][c^1]){m=((c^1)<<i)|m;rt=trie[rt][c^1];}else{m=(c<<i)|m;rt=trie[rt][c];}}return m^x;
}int main()
{int n;while(~scanf("%d",&n)){memset(dp,0,sizeof(dp));memset(pre,0,sizeof(pre));memset(suf,0,sizeof(suf));memset(trie,0,sizeof(trie));tot=0;for(int i=1;i<=n;i++) scanf("%d",&a[i]);//输入原数组 for(int i=1;i<=n;i++) pre[i]=a[i]^pre[i-1];//求前缀 for(int i=n;i>=1;i--) suf[i]=a[i]^suf[i+1];//求后缀//插入pre[0]即0，通过pre[]和01字典树求dp[] insert(0);for(int i=1;i<=n;i++){dp[i]=max(query(pre[i]),dp[i-1]);insert(pre[i]);} int ans=0;//初始化01字典树 tot=0;memset(trie,0,sizeof(trie));insert(0);for(int i=n;i>=1;i--){ans=max(ans,dp[i-1]+query(suf[i]));insert(suf[i]);}printf("%d\n",ans);}return 0;
}
这篇关于BZOJ4260 Codechef REBXOR【01字典树】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
