BZOJ 4260 Codechef REBXOR

发布于 2017-06-29  152 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4260

题意:找出两段不相交的区间,满足区间连续异或值的和最大


如果只找一段区间的话显然维护前缀异或值在 trie 上贪心即可,然而两段区间怎么搞呢?考虑枚举第一个区间的右端点实际上将原序列分为了两份,可以对两份分别贪心,两份分别最大值的和即为当前答案,依次更新即可... 实际实现先加个 0,正反扫两遍即可

 


一个非常弱的准退役OIER