本文主要是介绍#10051. 「一本通 2.3 例 3」Nikitosh 和异或 字典树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
给定一个含 个元素的数组 ,下标从 开始。请找出下面式子的最大值:,其中, 表示 和 的按位异或。
输入格式
输入数据的第一行包含一个整数 ,表示数组中的元素个数。
第二行包含 个整数 。
输出格式
输出一行包含给定表达式可能的最大值。
样例
样例输入
5
1 2 3 1 2
样例输出
6
题目是 求两端不相邻的异或区间最大的和
求区间异或值,其实是两端点的异或前缀和
x⊕x=0
所以 从l到r的异或相当于(从1到l)和(1到r)的异或
然后我们可以定义一个sum数组来储存前缀的异或和,区间[l,r]的值为sum[r]⊕sum[l-1],把sum中的值看成一些数,就相当于The XOR Largest Pair这道题
再定义一个ans数组,我们用lans表示从左往右到第i位时的区间最大异或和。
lans[i]=max(lans[i+1],query(sum[i])
rans表示从右往左到第i位时的区间最大异或和。
rans[i]=max(rans[i-1],query(sum[i])
ans=max{ans,lans[i]+rans[i+1]}
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
const int maxn = 400005;
int tree[maxn*32][2], tot;
void join(int x)
{int u=0,i;for(i=31;i>=0;i--){int c=(x>>i)&1;if(!tree[u][c])tree[u][c]=++tot;u=tree[u][c];}
}
int query(int x)
{int u=0,ans=0,i,c,o;for(i=31;i>=0;i--){c=(x>>i)&1;o=c^1;if(!tree[u][o]){ans<<=1;u=tree[u][c];}elseans=(ans<<1|1),u=tree[u][o];}return ans;
}
void init()
{memset(tree,0,sizeof(tree));tot = 0;
}
int a[maxn],lsum[maxn],rsum[maxn];
int lans[maxn],rans[maxn];
int main()
{int n;scanf("%d",&n);for(int i =1; i<=n; i++){scanf("%d",&a[i]);lsum[i] = lsum[i-1]^a[i];}for(int i = n; i>=1; i--) rsum[i] = rsum[i+1]^a[i];for(int i = n; i>=0; i--){lans[i] = max(query(lsum[i]),lans[i+1]);join(lsum[i]);}init();for(int i = 1; i<=n+1; i++){rans[i] = max(query(rsum[i]),rans[i-1]);join(rsum[i]);}ll ans = 0;for(int i = 0; i<=n; i++){ans = max(ans,(ll)lans[i] + rans[i+1]);}printf("%lld\n",ans);return 0;
}
这篇关于#10051. 「一本通 2.3 例 3」Nikitosh 和异或 字典树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!