用了大概一個半月的時間吧，當然中間有大概一個禮拜空著來著
這是第二次做USACO了，第一次是高中的時候，那個時候的題目跟現(xiàn)在的都不太一樣，主要是順序，而且那個時候是用PASCAL寫的
但是高中的時候沒有做完，卡在了Section 5之前，其實是因為很多東西不會，數(shù)學其實也不夠好，至于理解的能力，不知道現(xiàn)在是不是也有所提高了
其實這次做的并不是非常順利，我不是牛人，不可能一天掃10幾道題目那種，然后每到題目半個小時就搞定
前面3個Section的題目還都不算是很難，都是訓練型的，都是教你算法怎么用，從Section 4開始就有比較難的題目了，尤其是DP
DP從高中開始我就沒有感覺，那時候就有人跟我說，只能多做題目，也許我現(xiàn)在做的還不夠多吧，總感覺DP是很有用很有用的東西，所以一直想學好
不管怎么樣，USACO總算是磕磕碰碰的做完了，應該在NoCow和Google的幫助下終于做完了
后面大部分題目我都看了解題報告，有些算法想得出，但是不知道該怎么應用到題目之上
現(xiàn)在發(fā)現(xiàn)這點才是最重要的，算法模塊誰不會寫啊，都可以提前寫好一個放在那里，但是問題是怎么把這個算法應用到題目上
可能這就是所謂的建模吧，把題目變形一下，然后跟我們已知的算法聯(lián)系起來
還有另外一種情況，這個題目的算法不是已知的任何算法，要自己去想的，這才是真正考驗一個人算法素養(yǎng)的時候
就像TCO里面的題目，其實很多都是這樣的，很少會給你一道題目讓你直接去套一個算法的
可能原來我在這方面的理解就有偏差，我總認為，你把所有的常見算法都練熟了，所有的題目都可以橫掃
但是問題就是，你能不能看得出來哪道題目用哪種算法
而且，就像DP這種題目，就算你看出來了，狀態(tài)轉(zhuǎn)移方程你也未必寫的出來
總之還是學到了很多，雖然磕磕碰碰，但是做完了100道題還是會有收獲的
不知道下一個目標是什么SGU呢，還是TCO
其實之所以喜歡USACO的一個原因就是他會告訴你測試數(shù)據(jù)，你可以很方便的Debug
像OJ這種，不告訴你測試數(shù)據(jù)的，如果遇到了WA，你就要想破腦袋去想你的程序哪里錯了
而往往一個人自己看自己的程序的時候，是很難發(fā)現(xiàn)錯誤的，這就會讓人很郁悶，真的是非常郁悶
更何況，有些OJ真的是很賤的，用一些超級惡心的數(shù)據(jù)來鉆你的空子。
不知道這樣對不對，也許是考驗你的細心程度吧
SGU or TCO 呢？
| TEXT
Convex Hulls |
突包 |
| PROB Fencing the Cows |
突包問題，直接忽略，差不多所有的計算幾何我都跳過了 |
| PROB Starry Night |
超級麻煩題，用Flood Fill把所有的pattern全認出來，然后判斷重復，不重復就添加新的 |
| PROB Musical Themes |
DP題，技巧在于如果兩個序列是theme，那么相鄰的兩個number差相等 |
| PROB Snail Trail |
DFS，沒啥技巧 |
| PROB Electric Fences |
剛開始以為是Divide&Conquer，后來發(fā)現(xiàn)跟那道題不一樣，直接搜索就可以 |
| PROB Wisconsin Squares |
搜索題，Testcase只有sample那一組 |
| TEXT
Heuristics & Approximate Searches |
啟發(fā)式搜索，沒看 |
| PROB Milk Measuring |
一道我看Analysis看了兩天的DP，其實還是沒有深刻理解 |
| PROB Window Area |
可以用矩形切割過 |
| PROB Network of Schools |
強連通分量題 |
| PROB Big Barn |
最大子正方形，簡單的DP |
| PROB All Latin Squares |
搜索+剪枝 |
| PROB Canada Tour |
詭異的DP算法，Analysis的那個DP倒是還可以接受，不過Nocow上的似乎需要證明，但是又沒有 |
| PROB Character Recognition |
這道題目都能用DP，不得不感嘆DP的偉大 |
| PROB Betsy's Tour |
又是搜索+剪枝 |
| PROB TeleCowmunication |
先把點轉(zhuǎn)化成邊，然后求最小割 |
| PROB Picture |
離散化 |
| PROB Hidden Passwords |
搜索+KMP優(yōu)化 |
| PROB Two Five |
算是道難題吧，Analysis都看了好久，DP真是無所不能 |
第六個Section的就不寫了，兩個DP+一個牛叉的位運算
那個Cow XOR我估計我這輩子都不會忘記了。
這個題目是USACO最后的一道題目，我在網(wǎng)上找了N多的題解，不是完全一樣的，就是說的不知道是什么東西的
不知道為啥，是不是所有搞OI的人在寫題解的時候都喜歡用“提示”的辦法，不直接把問題說清楚，而是隱隱約約的公訴你該怎么做，然后你讓你自己去想。
于是導致我到現(xiàn)在都沒有弄明白這道題目是怎么回事，盡管他們的做法有N多種，但是歸根到底都是在搞一個叫做前綴的東西。
下面這個是我在TopCoder上面找到的一個牛人的解釋，算是英語寫的比較好的，很通俗易懂的
上面這篇文章我想我就不用再翻譯了，說的比較清楚，但是他也沒有給出具體的算法，不過思路已經(jīng)很清楚了
其實有了第一條性質(zhì)之后，最樸素的辦法就是枚舉i和j，所以個2次循環(huán)，但是這樣顯然是要TLE的
在沒有更好的算法的前提下，這道題目的算法就是空間換時間，在我看來就是這樣的。
在看了N多代碼之后，我覺得還是USACO的Analysis的代碼看上去比較美，不知道為啥，那些用Hash和Trie的我都沒看懂，可能是我比較菜吧
下面我嘗試著把USACO的代碼解釋一下，看看能不能說清楚，很遺憾，由于這道題目的巨型的輸入數(shù)據(jù)，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位結(jié)束的所有的xor都求出來保存在了數(shù)組xor里面，我想這個就是為了方便后面用到xor的那個性質(zhì)。
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.
我們要根據(jù)后面的循環(huán)來看這個prev數(shù)組的含義
外側(cè)的循環(huán)的作用是每次處理一位，由于題目中已經(jīng)說明了，最多只有21位，所以循環(huán)21次就可以了。
我們來看內(nèi)側(cè)的循環(huán)
18～31行，對所有的奶牛編號循環(huán)一遍，得到的結(jié)果就是：
對于當前的xor number，對于這個xor number的前21 - wyk位，與他相同的那個xor number的位置，并且，這個位置要盡量的靠后。
如果沒有相同的，那么這個位置就是-1
這樣，經(jīng)過每次循環(huán)之后，prev里面就是與當前的xor number前k位相同的那個數(shù)的位置，一次一次循環(huán)，直到最后。
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]卻必須變化，因為當前的這一位，已經(jīng)不是剛才比較的那一位了，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]位置的值肯定
是已經(jīng)處理過的了。那么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，他們的每一位都不相同，這樣就能保證異或結(jié)果是最大的。
接下來看38～45的這段代碼，因為我們是從高位到低位來處理的，這樣的話，如果能保證高位是1，那么比你所有的低位都是1都管用：）
于是，既然我們找到了高位是1的情況，那么我們就要記錄下結(jié)果 res
然后，剩下的那個循環(huán)就是更新best[a]
在所有的xor
number中，如果當前位跟best[a]的當前位是相等的，那么就更新best[a]，將其更新為prev[best[a]][1]，就是除了當前位
不相等，其余位不變的那個xor number，這樣就保證了從高位開始，每一位都能夠盡量取到1，因為只要高位盡量是1，我們的結(jié)果就能盡量的大。
其實prev這個數(shù)組里面真正有用的是prev[q][1]
不知道我解釋清楚了沒，其實解釋了一遍，自己也清楚了很多。