这个题目是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]
不知道我解释清楚了没,其实解释了一遍,自己也清楚了很多。