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