这个题目是USACO最后的一道题目,我在网上找了N多的题解,不是完全一样的,就是说的不知道是什么东西的

不知道为啥,是不是所有搞OI的人在写题解的时候都喜欢用“提示”的办法,不直接把问题说清楚,而是隐隐约约的公诉你该怎么做,然后你让你自己去想。

于是导致我到现在都没有弄明白这道题目是怎么回事,尽管他们的做法有N多种,但是归根到底都是在搞一个叫做前缀的东西。

下面这个是我在TopCoder上面找到的一个牛人的解释,算是英语写的比较好的,很通俗易懂的
上面这篇文章我想我就不用再翻译了,说的比较清楚,但是他也没有给出具体的算法,不过思路已经很清楚了

其实有了第一条性质之后,最朴素的办法就是枚举i和j,所以个2次循环,但是这样显然是要TLE的

在没有更好的算法的前提下,这道题目的算法就是空间换时间,在我看来就是这样的。

在看了N多代码之后,我觉得还是USACO的Analysis的代码看上去比较美,不知道为啥,那些用Hash和Trie的我都没看懂,可能是我比较菜吧

下面我尝试着把USACO的代码解释一下,看看能不能说清楚,很遗憾,由于这道题目的巨型的输入数据,java肯定是没办法过的
 
 1 int main() {
 2     freopen("cowxor.in", "r", stdin);
 3     freopen("cowxor.out", "w", stdout);
 4     scanf("%i", &n);
 5     xr[0] = 0;
 6     for (a = 0; a < n; a++ ) {
 7         scanf("%d", &x);
 8         xr[a+1] = xr[a] ^ x;
 9     }
10     for (a = 0; a <= n; a++ ) {
11         prev[a][0] = a-1;
12         prev[a][1] = -1;
13         best[a] = a-1;
14     }
15     wyk = 22;
16     res = 0;
17     while (wyk--) {
18         for (a = 1; a <= n; a++ )
19             if (prev[a][0] == -1)
20                 prev[a][1] = -1;
21             else {
22                 if (xr[a] >> wyk != xr[prev[a][0]] >> wyk) {
23                     tmp[0] = prev[prev[a][0]][1];
24                     tmp[1] = prev[a][0];
25                 } else {
26                     tmp[0] = prev[a][0];
27                     tmp[1] = prev[prev[a][0]][1];
28                 }
29                 prev[a][0] = tmp[0];
30                 prev[a][1] = tmp[1];
31             }
32         fnd = false;
33         for (a = 1; a <= n; a++ )
34             if (0 <= best[a])
35                 if ((xr[a] >> wyk) % 2 != (xr[best[a]] >> wyk) % 2 ||
36                                       0 <= prev[best[a]][1])
37                     fnd = true;
38         if (fnd) {
39             res |= 1 << wyk;
40             for (a = 1; a <= n; a++ )
41                 if (0 <= best[a] &&
42                               (xr[a] >> wyk) % 2 == (xr[best[a]] >> wyk) % 2)
43                     best[a] = prev[best[a]][1];
44         }
45     }
46     for (a = 0; best[a] == -1; a++ );
47     printf("%d %d %d"n", res, best[a]+1, a);
48     return 0;
49 }

首先,6~9行,程序把从1开始到i位结束的所有的xor都求出来保存在了数组xor里面,我想这个就是为了方便后面用到xor的那个性质。

10~14行是一个 初始化的过程,这个prev的定义应该可以从USACO的Analysis上面看到:

  xr[pop[q][0]]'s and xr[q]'s binary representations are the same on positions e, e+1, etc., and pop[q][0] is biggest possible with 0 ≤ pop[q][0] < q. If there's no such pop[q][0] possible, then pop[q][0] = -1.

xr[pop[q][1]]'s and xr[q]'s binary representations are the same on positions e+2, e+2, etc., different on position e, and pop[q][1] is biggest possible with 0 ≤ pop[q][1] < q. If there's no such pop[q][1] possible, then pop[q][1] = -1.


我们要根据后面的循环来看这个prev数组的含义

外侧的循环的作用是每次处理一位,由于题目中已经说明了,最多只有21位,所以循环21次就可以了。

我们来看内侧的循环

18~31行,对所有的奶牛编号循环一遍,得到的结果就是:
对于当前的xor number,对于这个xor number的前21 - wyk位,与他相同的那个xor number的位置,并且,这个位置要尽量的靠后。

如果没有相同的,那么这个位置就是-1

这样,经过每次循环之后,prev里面就是与当前的xor number前k位相同的那个数的位置,一次一次循环,直到最后。

prev[i][0]存的是当current bit也相同的时候的位置,prev[i][1]存的是currnet bit不相同时候的位置,为什么要这样呢?

这可能就需要解释一下
     if (xr[a] >> wyk != xr[prev[a][0]] >> wyk) {
                     tmp[0] = prev[prev[a][0]][1];
                     tmp[1] = prev[a][0];
     } else {
                     tmp[0] = prev[a][0];
                     tmp[1] = prev[prev[a][0]][1];
    }
如果当前比较的这一位相等,那么也就意味着prev[a][0]不用变,但是prev[i][1]却必须变化,因为当前的这一位,已经不是刚才比较的那一位了,prev[a][1]应该等于此时的prev[a][0]的prev[a][1],我想这个应该不难理解。

另一方面,如果当前比较的这一位不相等的时候,那么prev[a][1]就应该等于prev[a][0]了,因为之前的所有位都相等,之后当前这一位不相 等,这就是prev[a][1]的定义。那么prev[a][0]的值呢?我们需要注意的时候,当我们处理到a的时候,prev[a][0]位置的值肯定 是已经处理过的了。那么prev[a][prev[a][0]][1]里面存的就是与prev[a][0]在当前位不相等的那个xor number的位置,注意,bit只有0和1,prev[a][0]与当前的不相等,而prev[a][prev[a][0]][1]又与prev[a] [0]不相等,所以当前的prev[a][1]肯定与prev[a][prev[a][0]][1]是相等的。这就是 tmp[0] = prev[prev[a][0]][1];的含义。

我再来看32~37行,首先要知道best[q]的定义:

if X would be equal biggest possible xor, then xr[best[q]] xor xr[q]'s in equal X's binary representation on positions e, e+1, etc., and best[q] is biggest possible with 0 ≤ best[q] < q. If there's no such best[q] possible, then best[q] = -1.

想要得到尽量大的xor,那么就要尽量让每一位都不相同 (xr[a] >> wyk) % 2就是取当前的二进制的最后一位

这段代码的作用就是找,到当前位为止,是否有两个xor number,他们的每一位都不相同,这样就能保证异或结果是最大的。

接下来看38~45的这段代码,因为我们是从高位到低位来处理的,这样的话,如果能保证高位是1,那么比你所有的低位都是1都管用:)

于是,既然我们找到了高位是1的情况,那么我们就要记录下结果 res

然后,剩下的那个循环就是更新best[a]

在所有的xor number中,如果当前位跟best[a]的当前位是相等的,那么就更新best[a],将其更新为prev[best[a]][1],就是除了当前位 不相等,其余位不变的那个xor number,这样就保证了从高位开始,每一位都能够尽量取到1,因为只要高位尽量是1,我们的结果就能尽量的大。

其实prev这个数组里面真正有用的是prev[q][1]

不知道我解释清楚了没,其实解释了一遍,自己也清楚了很多。