用了大概一个半月的时间吧,当然中间有大概一个礼拜空着来着
这是第二次做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]
不知道我解释清楚了没,其实解释了一遍,自己也清楚了很多。