USACO/cowxor

 这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。
 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。
 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。

这是USACO Chapter 6 .1中的OI题目Cow XOR的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。

问题分析

位运算。恕本人不是特别熟悉这东西，可能说的不是太清楚。 首先，根据题目规模，O(n^2)的算法肯定是不行的。这就引导我们考虑O(nlogn)或者O(n)的算法。O(nlogn)的算法肯定要用到二分，可是本人暂时还没想出来。 下面来说O(n)的算法。 首先，如果把最大的数转换成二进制，也不过21位，而二进制的操作比起十进制来要简单的多，而且存在很多特殊性，可以有很多十进制没有的优化。这就是采用位运算的原因。 维护tot[i]表示前i个牛的异或值，则任意一段(i,j)的异或值为tot[i-1] xor tot[j]。那么对于i以前的序列的最大值应为max(tot[j-1] xor tot[i])(j<=i)。但我们不用枚举j，而是用位运算来直接得到最优解。 另外再维护一个s，s[i]=k表示离当前位最近的k-1，使得tot[k-1]的某个前缀为i。对于tot[i]，从大到小枚举每一位j。令q等于tot[i,j]的异或，则若q曾经出现过，那么解的第j位可以为1，否则只能为0。重复上述过程就可以得到当前最优解t。 然后用tot[i]的所有前缀更新s。 最后的最优解就是答案。

某菜鸟:楼上大牛的解法本菜鸟实在有点不明白..转贴一篇brian007牛写的trie的解法，自我感觉应该更加容易理解，希望对大家有所帮助:D http://blog.csdn.net/biran007/archive/2009/02/19/3911430.aspx

其实，就是构建一棵查找树。 我们首先处理出前i个数字的异或值，记为a[i].那么，问题就转化成了在a数组中求两个数，使其异或值最大。 怎么办呢？注意到n^2的算法是会超时的！ 我们发现，n^2慢在了对于第i个数字寻找另一个使其异或值最大的过程是O(N)的，太慢了。 我们可以构建一棵二叉树，对于i这个元素表示以i的二进制为前缀的某个数是否存在。 注意，我们规定任意一个二进制数都是21位的(因为数字最多21位） 那么，000 （举例）就是000 1的前缀。 所以，i的两个孩子就是k位数i的k+1位为0或1. 首先，我们可以用nm(m是转为二进制最大的位数)的构建出这棵树（这里不能先构建吧，MS要每异或一下插一个进去）。 然后对于每个a[i]中的数，对其去一个反后去树中查找这个数字。如果这个数字第1位为1，第二位为0.若树有第一位为1的，那么进入1这个节点后查找“10”，否则进入0后查找“00” 这样，整个复杂度就是nlogn了

                                                                                 by zrp
                                                                                 Orz zrp！！！

---

zrp: this is called 0-1 trie tree.

一定要注意，要先生成一个由0构成的树，以判“全相同”情况。 还有，注意题中要求“最短的解”。

                                                                       by zrp's friend——此者

---

详细题解

首先，xor运算有如下的性质：假设 a xor b = c a，b，c之间任意两个做xor得到第三个，并且与顺序无关。 于是，我首先算出x[i]代表第一个连续xor到第i个的值。特别的，x[1]=a[1],x[0]=0;(a[]是哪个输入中的附加值) 然后，假设一个函数f[i,j]表示的是第i个开始，xor到第j个的值。 容易知道，x[i-1] xor f[i,j] =x[j] 所以，f[i,j]=x[j] xor x[i-1],(1<=i,j<=n) 现在，这个问题转化成了在x[0]...x[n]这n+1个数中找到两个数，他们的xor最大的问题。 发现盲目枚举会超时，数据很大。

在考虑一下xor的运算规则，从高位开始，逐步向低位每位xor，那么，对任何一个x[i],要想对应的找到一个x[j]使得xor值比较大，首先要得到的值较高位比较大。。。

我们可以把所有的数用一颗数组实现的满二叉树储存起来，深度为0..21，共有2^22-1个节点，每个节点的数据有一个bool值。节点表示这样的意义，第i层开始，每向下走一层，往左表示第二进制21-i位为0，往右表示为1，于是节点上的bool值表示为从顶点开始，走到这个点的路径所代表的前缀是否存在。 现在，对每一个x[i]寻找x[j]的过程就是尽量往和x[i]的二进制位相反的方向走的过程。

如果相反的前缀存在，就往与x[i]相反方向走，反之，走另外一边；直到走到最下边为止。这样，我们可以找到最大的那个xor值还有x[i]相互xor最大的那个x[j]的值。(比较烦的是找到这个符合题目要求的j)

然后，我们来找j。设置一个数组invers[k]表示x[i]的值为k的i的值； 则有invers[x[i]]=i,我们还约定，如果x[i]=x[j],那么，invers[x[i]]=max(i,j); 设ans[i]是和x[i]经过xor得到最大的值的那个数； maxans=max{ansd[i]}； start 待求开始的位置； end 待求的结尾的位置；

扫描i：
if(ans[i] xor x[i]==maxans){
 如果invers[a[i]]在i后面，并且，invers[a[i]]不end后面
    更新最优值{
	start = (i+1);
	end = invers[a[i]];
	} 
}

就可以了。。。。//我的代码在最后c++那个

                                                                       by talenth1

---

参考代码

C

C++

Pascal