[BZOJ4260] Codechef REBXOR

本文主要是介绍[BZOJ4260] Codechef REBXOR，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

http://www.lydsy.com/JudgeOnline/problem.php?id=4260

题目大意

给定序列,求最大的$(x_{l1}~xor~x_{l1+1}~xor~...x_{r1})+(x_{l2}~xor~x_{l2+1}~xor~...x_{r2})$

题解

xor是支持交换律的,所以我们维护xor前缀和
$x_{l1}~xor~x_{l1+1}~xor~...x_{r1}=sum[r1] xor sum[l1-1]$
问题变为求$(sum[r1]~xor~sum[l1-1])+(sum[l2-1]~xor~sum[r2])$
$我们从前向后插入sum枚举i,得到dp[i]:[1,i]中最大抑或段$
$然后再从后向前把sum添加进新的Trie并枚举l2,第一个区间通过dp值O(1)查询,第二个区间把sum[l2-1]放到新的Trie上跑得到第二个区间的最大值,然后更新答案$
…..我是傻逼,,,,,2^28>10^9

constmaxn=400005;
varx,sum,dp:array[0..maxn]of longint;son:array[1..2,0..maxn*31,0..1]of longint;i,j,k:longint;n,a,tail,ans:longint;
function max(a,b:longint):longint;
beginif a<b then exit(b) else exit(a);
end;procedure init(kind,a:longint);
var i,tt,b:longint;
begintt:=0;for i:=30 downto 1 dobeginif (a and (1<<(i-1)))=0then b:=0 else b:=1;if son[kind,tt,b]=0then begin inc(tail); son[kind,tt,b]:=tail; end;tt:=son[kind,tt,b];end;
end;function f(kind,a:longint):longint;
var i,tt,b,c,anss:longint;
begintt:=0; anss:=0;for i:=30 downto 1 dobeginif (a and (1<<(i-1)))=0then b:=0 else b:=1;c:=b xor 1;if son[kind,tt,c]<>0then begin anss:=anss+(1<<(i-1)); tt:=son[kind,tt,c]; endelse begin tt:=son[kind,tt,b]; end;end;exit(anss);
end;beginreadln(n); sum[0]:=0;for i:=1 to n dobeginread(x[i]);sum[i]:=sum[i-1] xor x[i];end;tail:=0;for i:=1 to n dobegininit(1,sum[i-1]);dp[i]:=max(dp[i-1],f(1,sum[i]));end;tail:=0; ans:=0;for i:=n downto 1 dobegininit(2,sum[i]);a:=f(2,sum[i-1]);ans:=max(ans,dp[i-1]+a);end;writeln(ans);
end.

这篇关于[BZOJ4260] Codechef REBXOR的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---