[USACO]6.1.3 cow xor(二进制+Trie)

时间:2022-09-13 07:06:59

题意:给你一个序列(n<=100000),求出一个连续的子序列[i,j]使得ai xor ai+1 xor…… xor aj最大,求出这个最大值(其中每个数<=2^21)

分析:题目和求一段子序列的和或者积很像,只是运算法则改变,所以可以往求子段和、积的方法上面考虑

首先如果设sum[i]=a1 xor a2 xor a3……xor ai,则子序列[i,j]的xor值可以表达为sum[j] xor sum[i-1],这样是O(n^2)的是不行的

有以往的处理经验我们知道,后面那个j一定要枚举的,关键在于如何快速在j前面找到一个i-1使得xor结果最大

而xor最大的含义就是说高位上要尽可能的不相同,于是我们不妨把它们都转成二进制并以最高位开始加入一个0、1组成的Trie树

于是我们的得到一个贪心算法,对每次的j先在Trie中尽可能大找,如当sum[j]=100101时候,我们先找第一层的0(因为要不同才好),然后找第二层的1,……以此类推,不过要注意如果我们希望找的那个不同的在Trie不存在,即以前没有出现过,那么就老老实实的按另一个走吧。最后查询完后可以作为以j为右边的序列的最优值,更新ans,并把sum[j]插入Trie。

复杂度是O(nlogn),完美解决