這個題目是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]

不知道我解釋清楚了沒,其實解釋了一遍,自己也清楚了很多。