用了大概一个半月的时间吧，当然中间有大概一个礼拜空着来着
这是第二次做USACO了，第一次是高中的时候，那个时候的题目跟现在的都不太一样，主要是顺序，而且那个时候是用PASCAL写的
但是高中的时候没有做完，卡在了Section 5之前，其实是因为很多东西不会，数学其实也不够好，至于理解的能力，不知道现在是不是也有所提高了
其实这次做的并不是非常顺利，我不是牛人，不可能一天扫10几道题目那种，然后每到题目半个小时就搞定
前面3个Section的题目还都不算是很难，都是训练型的，都是教你算法怎么用，从Section 4开始就有比较难的题目了，尤其是DP
DP从高中开始我就没有感觉，那时候就有人跟我说，只能多做题目，也许我现在做的还不够多吧，总感觉DP是很有用很有用的东西，所以一直想学好
不管怎么样，USACO总算是磕磕碰碰的做完了，应该在NoCow和Google的帮助下终于做完了
后面大部分题目我都看了解题报告，有些算法想得出，但是不知道该怎么应用到题目之上
现在发现这点才是最重要的，算法模块谁不会写啊，都可以提前写好一个放在那里，但是问题是怎么把这个算法应用到题目上
可能这就是所谓的建模吧，把题目变形一下，然后跟我们已知的算法联系起来
还有另外一种情况，这个题目的算法不是已知的任何算法，要自己去想的，这才是真正考验一个人算法素养的时候
就像TCO里面的题目，其实很多都是这样的，很少会给你一道题目让你直接去套一个算法的
可能原来我在这方面的理解就有偏差，我总认为，你把所有的常见算法都练熟了，所有的题目都可以横扫
但是问题就是，你能不能看得出来哪道题目用哪种算法
而且，就像DP这种题目，就算你看出来了，状态转移方程你也未必写的出来
总之还是学到了很多，虽然磕磕碰碰，但是做完了100道题还是会有收获的
不知道下一个目标是什么SGU呢，还是TCO
其实之所以喜欢USACO的一个原因就是他会告诉你测试数据，你可以很方便的Debug
像OJ这种，不告诉你测试数据的，如果遇到了WA，你就要想破脑袋去想你的程序哪里错了
而往往一个人自己看自己的程序的时候，是很难发现错误的，这就会让人很郁闷，真的是非常郁闷
更何况，有些OJ真的是很贱的，用一些超级恶心的数据来钻你的空子。
不知道这样对不对，也许是考验你的细心程度吧
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，后来发现跟那道题不一样，直接搜索就可以 |
| PROB Wisconsin Squares |
搜索题，Testcase只有sample那一组 |
| TEXT
Heuristics & Approximate Searches |
启发式搜索，没看 |
| 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 |
先把点转化成边，然后求最小割 |
| PROB Picture |
离散化 |
| PROB Hidden Passwords |
搜索+KMP优化 |
| PROB Two Five |
算是道难题吧，Analysis都看了好久，DP真是无所不能 |
第六个Section的就不写了，两个DP+一个牛叉的位运算
那个Cow XOR我估计我这辈子都不会忘记了。
这个题目是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]
不知道我解释清楚了没，其实解释了一遍，自己也清楚了很多。