用了大概一個(gè)半月的時(shí)間吧，當(dāng)然中間有大概一個(gè)禮拜空著來(lái)著

這是第二次做USACO了，第一次是高中的時(shí)候，那個(gè)時(shí)候的題目跟現(xiàn)在的都不太一樣，主要是順序，而且那個(gè)時(shí)候是用PASCAL寫(xiě)的

但是高中的時(shí)候沒(méi)有做完，卡在了Section 5之前，其實(shí)是因?yàn)楹芏鄸|西不會(huì)，數(shù)學(xué)其實(shí)也不夠好，至于理解的能力，不知道現(xiàn)在是不是也有所提高了

其實(shí)這次做的并不是非常順利，我不是牛人，不可能一天掃10幾道題目那種，然后每到題目半個(gè)小時(shí)就搞定

前面3個(gè)Section的題目還都不算是很難，都是訓(xùn)練型的，都是教你算法怎么用，從Section 4開(kāi)始就有比較難的題目了，尤其是DP

DP從高中開(kāi)始我就沒(méi)有感覺(jué)，那時(shí)候就有人跟我說(shuō)，只能多做題目，也許我現(xiàn)在做的還不夠多吧，總感覺(jué)DP是很有用很有用的東西，所以一直想學(xué)好

不管怎么樣，USACO總算是磕磕碰碰的做完了，應(yīng)該在NoCow和Google的幫助下終于做完了

后面大部分題目我都看了解題報(bào)告，有些算法想得出，但是不知道該怎么應(yīng)用到題目之上

現(xiàn)在發(fā)現(xiàn)這點(diǎn)才是最重要的，算法模塊誰(shuí)不會(huì)寫(xiě)啊，都可以提前寫(xiě)好一個(gè)放在那里，但是問(wèn)題是怎么把這個(gè)算法應(yīng)用到題目上

可能這就是所謂的建模吧，把題目變形一下，然后跟我們已知的算法聯(lián)系起來(lái)

還有另外一種情況，這個(gè)題目的算法不是已知的任何算法，要自己去想的，這才是真正考驗(yàn)一個(gè)人算法素養(yǎng)的時(shí)候

就像TCO里面的題目，其實(shí)很多都是這樣的，很少會(huì)給你一道題目讓你直接去套一個(gè)算法的

可能原來(lái)我在這方面的理解就有偏差，我總認(rèn)為，你把所有的常見(jiàn)算法都練熟了，所有的題目都可以橫掃

但是問(wèn)題就是，你能不能看得出來(lái)哪道題目用哪種算法

而且，就像DP這種題目，就算你看出來(lái)了，狀態(tài)轉(zhuǎn)移方程你也未必寫(xiě)的出來(lái)

總之還是學(xué)到了很多，雖然磕磕碰碰，但是做完了100道題還是會(huì)有收獲的

不知道下一個(gè)目標(biāo)是什么SGU呢，還是TCO

其實(shí)之所以喜歡USACO的一個(gè)原因就是他會(huì)告訴你測(cè)試數(shù)據(jù)，你可以很方便的Debug

像OJ這種，不告訴你測(cè)試數(shù)據(jù)的，如果遇到了WA，你就要想破腦袋去想你的程序哪里錯(cuò)了

而往往一個(gè)人自己看自己的程序的時(shí)候，是很難發(fā)現(xiàn)錯(cuò)誤的，這就會(huì)讓人很郁悶，真的是非常郁悶

更何況，有些OJ真的是很賤的，用一些超級(jí)惡心的數(shù)據(jù)來(lái)鉆你的空子。

不知道這樣對(duì)不對(duì)，也許是考驗(yàn)?zāi)愕募?xì)心程度吧

SGU or TCO 呢？

TEXT Convex Hulls	突包
PROB Fencing the Cows	突包問(wèn)題，直接忽略，差不多所有的計(jì)算幾何我都跳過(guò)了
PROB Starry Night	超級(jí)麻煩題，用Flood Fill把所有的pattern全認(rèn)出來(lái)，然后判斷重復(fù)，不重復(fù)就添加新的
PROB Musical Themes	DP題，技巧在于如果兩個(gè)序列是theme，那么相鄰的兩個(gè)number差相等
PROB Snail Trail	DFS，沒(méi)啥技巧
PROB Electric Fences	剛開(kāi)始以為是Divide&Conquer，后來(lái)發(fā)現(xiàn)跟那道題不一樣，直接搜索就可以
PROB Wisconsin Squares	搜索題，Testcase只有sample那一組
TEXT Heuristics & Approximate Searches	啟發(fā)式搜索，沒(méi)看
PROB Milk Measuring	一道我看Analysis看了兩天的DP，其實(shí)還是沒(méi)有深刻理解
PROB Window Area	可以用矩形切割過(guò)
PROB Network of Schools	強(qiáng)連通分量題
PROB Big Barn	最大子正方形，簡(jiǎn)單的DP
PROB All Latin Squares	搜索+剪枝
PROB Canada Tour	詭異的DP算法，Analysis的那個(gè)DP倒是還可以接受，不過(guò)Nocow上的似乎需要證明，但是又沒(méi)有
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真是無(wú)所不能

第六個(gè)Section的就不寫(xiě)了，兩個(gè)DP+一個(gè)牛叉的位運(yùn)算

那個(gè)Cow XOR我估計(jì)我這輩子都不會(huì)忘記了。

TEXT Optimization Techniques	講怎么剪枝的
PROB Beef McNuggets	初看上去像是一道背包問(wèn)題，但是用背包肯定超時(shí)，后來(lái)看了解題報(bào)告，發(fā)現(xiàn)原來(lái)是數(shù)學(xué)題
PROB Fence Rails	高維背包問(wèn)題，只能搜索
PROB Fence Loops	其實(shí)是很簡(jiǎn)單的一道最短路問(wèn)題，惡心就惡心在圖的轉(zhuǎn)化
PROB Cryptcowgraphy	非常惡心的搜索+剪枝
TEXT "Network Flow" Algorithms	網(wǎng)絡(luò)流，我第一次會(huì)寫(xiě)網(wǎng)絡(luò)流就是看了這個(gè)算法
PROB Drainage Ditches	網(wǎng)絡(luò)流練習(xí)題
PROB The Perfect Stall	最大匹配，匈牙利算法
PROB Job Processing	第一問(wèn)是貪心，第二問(wèn)應(yīng)該也還是貪心，就是把第一問(wèn)最快做完的給第二問(wèn)最慢做完的
PROB Cowcycles	直接枚舉的好像
TEXT Big Numbers	高精度
PROB Buy Low, Buy Lower	經(jīng)典DP，最長(zhǎng)下降序列，可是問(wèn)題是要求出現(xiàn)了多少次，于是我看了解題報(bào)告
PROB The Primes	搜索+剪枝，要注意搜索的順序，先是第五行第五列，然后對(duì)角線，然后其他
PROB Street Race	關(guān)鍵路徑，去掉每一個(gè)節(jié)點(diǎn)，然后看看起點(diǎn)與終點(diǎn)是否連通，不聯(lián)通總說(shuō)明是關(guān)鍵節(jié)點(diǎn)
PROB Letter Game	枚舉，分兩塊，先找完整的單詞，然后找pair
PROB Shuttle Puzzle	剛開(kāi)始以為搜索，后來(lái)看了解題報(bào)告，發(fā)現(xiàn)原來(lái)有規(guī)律的，寒啊
PROB Pollutant Control	最小割問(wèn)題
PROB Frame Up	搜索題，用一張表來(lái)維護(hù)每個(gè)pattern的上下關(guān)系，可以大量剪枝

TEXT Minimal Spanning Trees	最小生成樹(shù)，經(jīng)典的算法
PROB Agri-Net	最小生成樹(shù)，USACO這點(diǎn)比較好，一般講完了一個(gè)算法，都會(huì)出一道練習(xí)題
PROB Score Inflation	背包問(wèn)題
PROB Humble Numbers	經(jīng)典題目，算法是用已有的丑數(shù)乘上集合里面的素?cái)?shù)去生成新的丑數(shù)
PROB Shaping Regions	記得高中的時(shí)候做過(guò)這道題目，當(dāng)初用的離散化的方法，不過(guò)現(xiàn)在USACO時(shí)限改成1秒了，那個(gè)方法可能不行了
PROB Contact	枚舉，輸出有點(diǎn)煩
PROB Stamps	一個(gè)背包問(wèn)題的變形
TEXT Knapsack Problems	怎么到現(xiàn)在才介紹背包問(wèn)題啊，前面都有好幾道了
PROB Factorials	高精度可以做，但是我是去接保留了最后的6位數(shù)，一直到最后。注意只保留一位數(shù)是不行的
PROB Stringsobits	直接生成的
PROB Spinning Wheels	又是一個(gè)我沒(méi)看懂題的題目，然后看了標(biāo)程，原來(lái)直接枚舉就行了，如此簡(jiǎn)單
PROB Feed Ratios	線性代數(shù)題目，直接把方程解出來(lái)就好了
PROB Magic Squares	比較惡心的DFS，主要是轉(zhuǎn)換那個(gè)狀態(tài)起來(lái)比較麻煩
PROB Sweet Butter	最短路的題目，枚舉每一個(gè)點(diǎn)作為集合點(diǎn)，然后求最短路
TEXT Eulerian Tours	歐拉回路，又是一個(gè)經(jīng)典的算法
PROB Riding The Fences	歐拉回路的題目
PROB Shopping Offers	DP問(wèn)題，狀態(tài)方程又不是我自己想的，555～
PROB Camelot	著名的亞瑟王問(wèn)題，我是看了解題報(bào)告才做出來(lái)的
PROB Home on the Range	DP問(wèn)題，找最大子正方形，后面還有一道是找最大子矩形的，難度大了很多
PROB A Game	動(dòng)態(tài)規(guī)劃，好不容易自己推出來(lái)的狀態(tài)轉(zhuǎn)移方程
TEXT Computational Geometry	計(jì)算幾何，沒(méi)看：（
PROB Closed Fences	計(jì)算幾何的題目，跳過(guò)了
PROB American Heritage	二叉樹(shù)遍歷順序題目，已知前序中序求后序
PROB Electric Fence	一個(gè)迭代求最優(yōu)值的題目，其實(shí)就是不斷縮小范圍的枚舉
PROB Raucous Rockers	DP，狀態(tài)方程又是看來(lái)的，似乎這才是比較有難度的DP，不像前面有些題，狀態(tài)方程簡(jiǎn)直顯而易見(jiàn)

TEXT Graph Theory	很有用的東西，建議仔細(xì)看看
TEXT Flood Fill Algorithms	其實(shí)就是DFS
PROB The Castle	Flood Fill，直接用上面那篇文章的算法就可以過(guò)
PROB Ordered Fractions	2次循環(huán)，求出所有的分?jǐn)?shù)，約分，去掉重復(fù)的，排序
PROB Sorting A Three-Valued Sequence	這題我是看的結(jié)題報(bào)告，其實(shí)就是分塊來(lái)交換 ，首先把所有的能一次交換完成的處理掉，然后處理需要兩次交換的
PROB Healthy Holsteins	忘記是貪心還是背包了……-_-!
PROB Hamming Codes	直接枚舉的
TEXT Data Structures	跳過(guò)
TEXT Dynamic Programming	動(dòng)態(tài)規(guī)劃啦，非常有必要好好看，不過(guò)這篇文章也只是對(duì)于初學(xué)者很有用
PROB Preface Numbering	羅馬數(shù)字問(wèn)題，把所有可能的組合先生成出來(lái)，4，9這種，然后就是求最小表示方法
PROB Subset Sums	背包問(wèn)題，這題我最開(kāi)始居然沒(méi)看出來(lái)……，以為是要深搜的，汗啊
PROB Runaround Numbers	直接模擬的，注意判斷是否是round number的條件
PROB Party Lamps	我當(dāng)初只注意到了每個(gè)操作做兩次就跟沒(méi)做一樣，所以一共也就有8種操作，后來(lái)看了解題報(bào)告，發(fā)現(xiàn)其實(shí)只要處理前6個(gè)燈就可以了
PROB The Longest Prefix	DP，我看得別人的解題報(bào)告，沒(méi)辦法DP是我的弱項(xiàng)
PROB Cow Pedigrees	DP，自己推了一個(gè)差不多的狀態(tài)方程，可惜錯(cuò)了……
PROB Zero Sum	直接模擬，把表達(dá)式生成出來(lái)，然后計(jì)算結(jié)果就行
PROB Money Systems	背包問(wèn)題
PROB Controlling Companies	看了別人的解題報(bào)告，這道題目用了一個(gè)變形的Floyd算法，很巧妙
TEXT Shortest Paths	經(jīng)典算法啦
PROB The Tamworth Two	模擬吧
PROB Overfencing	其實(shí)是比較惡心的一題，因?yàn)橐D(zhuǎn)化那個(gè)圖，剩下的就簡(jiǎn)單了，從兩個(gè)exit開(kāi)始BFS，然后找最大值
PROB Cow Tours	先Floyd，把圖劃分成兩塊，然后枚舉
PROB Bessie Come Home	直接Floyd就行
PROB Fractions to Decimals	判斷時(shí)候循環(huán)的條件就是看余數(shù)是否重復(fù)出現(xiàn)，當(dāng)然，在我看了Analysis之后，發(fā)現(xiàn)了更巧妙的辦法

這個(gè)題目是USACO最后的一道題目，我在網(wǎng)上找了N多的題解，不是完全一樣的，就是說(shuō)的不知道是什么東西的

不知道為啥，是不是所有搞OI的人在寫(xiě)題解的時(shí)候都喜歡用“提示”的辦法，不直接把問(wèn)題說(shuō)清楚，而是隱隱約約的公訴你該怎么做，然后你讓你自己去想。

于是導(dǎo)致我到現(xiàn)在都沒(méi)有弄明白這道題目是怎么回事，盡管他們的做法有N多種，但是歸根到底都是在搞一個(gè)叫做前綴的東西。

下面這個(gè)是我在TopCoder上面找到的一個(gè)牛人的解釋，算是英語(yǔ)寫(xiě)的比較好的，很通俗易懂的
上面這篇文章我想我就不用再翻譯了，說(shuō)的比較清楚，但是他也沒(méi)有給出具體的算法，不過(guò)思路已經(jīng)很清楚了

其實(shí)有了第一條性質(zhì)之后，最樸素的辦法就是枚舉i和j，所以個(gè)2次循環(huán)，但是這樣顯然是要TLE的

在沒(méi)有更好的算法的前提下，這道題目的算法就是空間換時(shí)間，在我看來(lái)就是這樣的。

在看了N多代碼之后，我覺(jué)得還是USACO的Analysis的代碼看上去比較美，不知道為啥，那些用Hash和Trie的我都沒(méi)看懂，可能是我比較菜吧

下面我嘗試著把USACO的代碼解釋一下，看看能不能說(shuō)清楚，很遺憾，由于這道題目的巨型的輸入數(shù)據(jù)，java肯定是沒(méi)辦法過(guò)的
 
 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開(kāi)始到i位結(jié)束的所有的xor都求出來(lái)保存在了數(shù)組xor里面，我想這個(gè)就是為了方便后面用到xor的那個(gè)性質(zhì)。

10～14行是一個(gè) 初始化的過(guò)程，這個(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)來(lái)看這個(gè)prev數(shù)組的含義

外側(cè)的循環(huán)的作用是每次處理一位，由于題目中已經(jīng)說(shuō)明了，最多只有21位，所以循環(huán)21次就可以了。

我們來(lái)看內(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è)位置要盡量的靠后。

如果沒(méi)有相同的，那么這個(gè)位置就是-1

這樣，經(jīng)過(guò)每次循環(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)處理過(guò)的了。那么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];的含義。

我再來(lái)看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é)果是最大的。

接下來(lái)看38～45的這段代碼，因?yàn)槲覀兪菑母呶坏降臀粊?lái)處理的，這樣的話，如果能保證高位是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，這樣就保證了從高位開(kāi)始，每一位都能夠盡量取到1，因?yàn)橹灰呶槐M量是1，我們的結(jié)果就能盡量的大。

其實(shí)prev這個(gè)數(shù)組里面真正有用的是prev[q][1]

不知道我解釋清楚了沒(méi)，其實(shí)解釋了一遍，自己也清楚了很多。

Section 1.0	TEXT Introduction	介紹啦，我是沒(méi)看
Section 1.1	TEXT Submitting Solutions	交你怎么提交程序的，可以看看
	PROB Your Ride Is Here	最直接的方法是直接乘，然后mod 47,不過(guò)可以利用余數(shù)定理，邊乘邊mod
	TEXT Contest Problem Types	跳過(guò)
	TEXT Ad Hoc Problems	跳過(guò)
	PROB Greedy Gift Givers	簡(jiǎn)單的模擬題，就是處理名字的時(shí)候有點(diǎn)煩
	PROB Friday the Thirteenth	數(shù)日期的題，我不知道一天天的模擬能不能過(guò)，我是只算了周五這一天的。
	PROB Broken Necklace	也是模擬題，不過(guò)很要細(xì)心，有很多特殊情況，比如全是w。
Section 1.2	TEXT Complete Search	跳過(guò)
	PROB Milking Cows	直接模擬應(yīng)該是過(guò)不了的，
	PROB Transformations	模擬題，直接把所有可能的pattern生成出來(lái)，然后比較就行
	PROB Name That Number	正確方法是把字典里面的所有word轉(zhuǎn)化成數(shù)字，然后比較就行。
	PROB Palindromic Squares	直接枚舉
	PROB Dual Palindromes	DFS，注意搜索的時(shí)候，只要搜索回文數(shù)前一半就行，后面的直接反向復(fù)制一下就好
Section 1.3	TEXT Greedy Algorithm	跳過(guò)
	PROB Mixing Milk	簡(jiǎn)單的貪心
	PROB Barn Repair	也是貪心法，把最大的縫隙就出來(lái)，然后去覆蓋
	TEXT Winning Solutions	跳過(guò)
	PROB Calf Flac	枚舉，從沒(méi)一點(diǎn)向兩邊枚舉
	PROB Prime Cryptarithm	直接枚舉，反正只有5個(gè)數(shù)
Section 1.4	TEXT More Search Techniques	跳過(guò)
	PROB Packing Rectangles	惡心題，我沒(méi)做：P
	PROB The Clocks	看了一個(gè)牛人的結(jié)題報(bào)告后過(guò)的，那位牛人總結(jié)了一個(gè)數(shù)組，就是如何讓表針轉(zhuǎn)一圈回到原來(lái)位置的操作組合
	PROB Arithmetic Progressions	搜索，硬搜的
	PROB Mother's Milk	BFS，把所有的情況都弄出來(lái)
Section 1.5	TEXT Introduction to Binary Numbers	跳過(guò)
	PROB Number Triangles	經(jīng)典DP
	PROB Prime Palindromes	搜索，生成回文數(shù)，檢查是否是素?cái)?shù)。需要一點(diǎn)點(diǎn)剪枝（長(zhǎng)度是偶數(shù)的回文數(shù)，除了11之外必然是合數(shù)，因它肯定是11的倍數(shù)）
	PROB SuperPrime Rib	直接枚舉
	PROB Checker Challenge	八皇后啊，用最經(jīng)典的算法就能過(guò)，不過(guò)如果想優(yōu)化的非常快，可能需要其他的辦法，也有很復(fù)雜的。

感想及題解待會(huì)兒再發(fā)：）

這道題用了離散化的方法

其實(shí)最樸素的方法就是在一個(gè)20000*20000的矩陣上面把所有的點(diǎn)描出來(lái)，然后把這些點(diǎn)的周長(zhǎng)算出來(lái)，不過(guò)算周長(zhǎng)這一步也是很麻煩的。

因?yàn)楫吘惯€有可能出現(xiàn)“空心”的情況

用離散化的方法就是想辦法只數(shù)每條線段，而不去管其他空白的地方是怎么樣的。

由于我們是需要算周長(zhǎng)的，所以只需要看矩形的四條邊就可以了。

然后，我們就是先看所有的橫邊，再看豎邊。

先把橫邊全部選出來(lái)，放在一個(gè)數(shù)組里面，然后排序，從下到上。

一個(gè)矩形的兩條邊要分成始邊和終邊，排序的時(shí)候，如果縱坐標(biāo)相同，那么應(yīng)該把始邊放在終邊。

如果遇到始邊，那么就把這條邊上面的所有點(diǎn)level[j]加一。

如果遇到終邊，就把那條邊上所有的點(diǎn)的level[j]減一

于是，當(dāng)一條邊上的點(diǎn)的leve是1的時(shí)候，那么就說(shuō)明這條邊肯定是始邊邊緣，所以要ans++

另一種情況，當(dāng)一條邊上的點(diǎn)的level是0的時(shí)候，那么說(shuō)明這個(gè)點(diǎn)是終邊邊緣，所以ans++

這樣掃完橫邊再掃豎邊。

最后的ans就是周長(zhǎng)了。

不過(guò)這個(gè)算法的時(shí)間效率并不是非常的好，因?yàn)閿?shù)據(jù)比較弱（可能是這樣）

如果真的是有5000個(gè)矩形，沒(méi)個(gè)矩形都是20000×20000的，那么可能會(huì)超時(shí)

雖然從5.1開(kāi)始，大部分題目都要借助于NoCow和網(wǎng)上的解題報(bào)告，但是還是學(xué)到了不少的東西。

原來(lái)認(rèn)為只要熟練的掌握各種算法，那就可以隨便去切題，現(xiàn)在發(fā)現(xiàn)其實(shí)不是這樣。

有很多題目，都需要進(jìn)行一些轉(zhuǎn)化，也可以說(shuō)是建模，才能套用現(xiàn)成的算法

而有一些題目，根本就沒(méi)有現(xiàn)成的算法，只能你自己去想

這種算法基本上是不屬于任何一類的

還有一些比如說(shuō)剪枝，雖然搜索誰(shuí)都會(huì)，Brute Force誰(shuí)都會(huì)寫(xiě)，但是剪枝卻不是誰(shuí)都能寫(xiě)的出來(lái)的

這就需要一些數(shù)學(xué)功底

現(xiàn)在發(fā)現(xiàn)這個(gè)東西必須要長(zhǎng)年累月的積累才能夠達(dá)到駕輕就熟的境界。

但是就算那樣，也不能保證所有的題目都會(huì)做。

這道題目我自己看出來(lái)是最小割的問(wèn)題，而之前的題目有一道是最小割的

但是有一個(gè)不同，這道題是點(diǎn)的最小割，而不是常規(guī)的邊的最小割

所以這就比較麻煩，需要我們把點(diǎn)轉(zhuǎn)化成邊

這就讓我想起了之前的那個(gè)Fence Loops

我就是把所有的邊表示的圖轉(zhuǎn)化成了點(diǎn)表示的圖，我實(shí)在是不想再寫(xiě)那么惡心的算法了。

然后我就去NoCow上面看了一下，果然是有很贊的方法。

具體方法就是，把一個(gè)點(diǎn)變成兩個(gè)點(diǎn)，然后在兩個(gè)點(diǎn)之間加一條邊，并且這條邊的權(quán)值是1

這樣的話，如果割這條邊，就相當(dāng)于去掉了這個(gè)點(diǎn)。

剩下的事情就是跟前面的那個(gè)Pollute Control差不多了

每次去掉一條邊，然后用MaxFlow求一下最大流，如果得出的最大流==最大流-邊的權(quán)值

那么就證明這條邊是最小割。

就這樣把所有的最小割找出來(lái)，然后就可以了

貌似數(shù)據(jù)很弱，不像上次的那個(gè)Pollute那道題目，還要考慮邊的編號(hào)的問(wèn)題的。

一個(gè)搜索的題目，不過(guò)肯定是要剪枝的

最簡(jiǎn)單的兩個(gè)剪枝我想到了

第一個(gè)：
首先，第一行已經(jīng)確定了，那么我們可以把第一列也確定，就按照升序，2，3，4，5……，這樣的話，沒(méi)生成這么一個(gè)square，我們就可以隨便的去交換除了第一行后面的幾行。

他們的一個(gè)全排列就對(duì)應(yīng)著一種組合，所以最后的答案乘以N-1的階乘就可以

第二個(gè)：
這個(gè)其實(shí)是看來(lái)的，就是每次只要所搜完N-1行就可以了。因?yàn)槭Ｏ碌囊恍斜厝淮嬖谝粋€(gè)解。其實(shí)這個(gè)不難理解的，最后一行的排列順序只跟前面的每一列缺少的那個(gè)數(shù)有關(guān)。

而且也只能取缺少的那個(gè)數(shù)，所以也就是唯一的。

第三個(gè)：
要用到置換群，我沒(méi)看懂

盡管之前N次看組合數(shù)學(xué)里面都說(shuō)到置換群，但是我還是似懂非懂，問(wèn)了數(shù)學(xué)小王子，他也不是非常懂。然后以為這個(gè)東西沒(méi)用，就忽略了。沒(méi)想到還真的有用。

今天終于第一次寫(xiě)了強(qiáng)連通分量的題目

雖然以前老早就知道有這么個(gè)東西，對(duì)這個(gè)東西也有概念，但是確實(shí)從來(lái)沒(méi)有寫(xiě)過(guò)判別的算法

原來(lái)如此簡(jiǎn)單，但是確實(shí)也很巧妙。

在算法導(dǎo)論上面看到的K算法，方法就是做兩遍DFS，因?yàn)閺?qiáng)連通分量有一個(gè)性質(zhì)，就是如果把所有的邊反向，那么它仍然是一個(gè)強(qiáng)連通分量。

但是今天我用的是Tarjan算法，據(jù)說(shuō)效率比K算法高很多，事實(shí)上也應(yīng)該是這樣，因?yàn)門arjan算法只做了一次DFS

其實(shí)思想也很簡(jiǎn)單，就是一直DFS（u），向下向下向下，如果突然發(fā)現(xiàn)有一個(gè)點(diǎn)可以回到u了，那么這個(gè)肯定是一個(gè)強(qiáng)連通分量。

哈哈，是不是很通俗。

嚴(yán)格的定義過(guò)程大家可以看這里http://www.cmykrgb123.cn/blog/scc-tarjan/

我也是參考了這個(gè)才做出來(lái)的Tarjan算法，Wiki上的那個(gè)過(guò)于龐大了，雖然封裝的非常好

說(shuō)說(shuō)本題，其實(shí)就是找強(qiáng)連通分量，然后把每個(gè)強(qiáng)連通分量當(dāng)成一個(gè)“超點(diǎn)”來(lái)考慮

如果這個(gè)“超點(diǎn)”的入度為零，那么它就必然是一個(gè)源頭，統(tǒng)計(jì)這樣的“超點(diǎn)”的個(gè)數(shù)，就是第一問(wèn)的答案。

第二問(wèn)，如果有一個(gè)“超點(diǎn)”入度不是0，但是出度是0，那就說(shuō)明這個(gè)“超點(diǎn)”可以給其他“超點(diǎn)”作貢獻(xiàn)。

我們就找這樣的點(diǎn)對(duì)，把入度是0和出度是0的點(diǎn)連起來(lái)。

這樣匹配過(guò)后，剩下的要么全是入度是0的，要么全是出度是0的，這些就沒(méi)辦法了，隨便從一個(gè)連通分量連接過(guò)來(lái)一條邊就可以了。

所以第二問(wèn)的答案就是所有的“超點(diǎn)”中，入度是0和出度是0的點(diǎn)大的那個(gè)數(shù)。

應(yīng)該算是一個(gè)比較基本的DP吧，狀態(tài)轉(zhuǎn)移方程也不難想，但是我最開(kāi)始寫(xiě)成了N^3的了

首先就是用Map[i][j]來(lái)表示以i，j為右下角的最大的square的大小

初始化就是第一行，第一列，如果不是#，那么肯定是1

然后對(duì)于i，j，我們需要觀察i - 1，j - 1，因?yàn)槭莝quare，所以只跟這個(gè)有關(guān)

如果在第i行，第j列上面，從當(dāng)前位置開(kāi)始，連續(xù)map[i-1][j-1]個(gè)位置，沒(méi)有#的話，那么map[i][j] = map[i-1][j-1]+1

我就是在判斷連續(xù)map[i-1][j-1]這個(gè)地方出了問(wèn)題，我又加了一層循環(huán)，所以就變成了N^3的了，然后果然TLE了

這個(gè)地方完全沒(méi)必要用循環(huán)一個(gè)一個(gè)去判斷，因?yàn)槠鋵?shí)你已經(jīng)有結(jié)果了，這個(gè)結(jié)果就是map[i-1][j]和map[i][j-1]里面小的那個(gè)

map[i-1][j]肯定就是從當(dāng)前位置開(kāi)始，在第j列上，向上最多可以走多少步不碰到#

因?yàn)檫@時(shí)候?qū)嶋H上你已經(jīng)確定了，#只有可能出現(xiàn)在第i行，第j列上，因?yàn)閙ap[i-1][j-1]不是#就保證了這一點(diǎn)

于是，找到兩個(gè)方向上走的比較近的那個(gè)數(shù)，如果這個(gè)數(shù)是小于map[i-1][j-1]的，那么map[i][j]就等于這個(gè)數(shù)

否則，map[i][j] = map[i-1][j-1]+1

這個(gè)地方的重點(diǎn)就是，如果map[i-1][j-1]不是#，那么就保證了#只能在第i行，第j列上面。

只需要檢查這兩個(gè)就可以

然后我們就可以來(lái)看map[i-1][j],map[i][j-1]，這兩個(gè)東西其實(shí)跟map[i-1][j-1]共享了上面的一塊。

如果在第i行，第j列上面出現(xiàn)了#，那么map[i-1][j],map[i][j-1]肯定比map[i-1][j-1]小

否則，我們的square最大也就只能是map[i-1][j-1]+1，因?yàn)閙ap[i-1][j-1]已經(jīng)是以i-1,j-1為右下角最大的square了

于是狀態(tài)轉(zhuǎn)移方程就是

map[i][j] = min (map[i-1][j],map[i][j-1],map[i-1][j-1]) + 1, map[i][j] != '#'

     摘要: 絕對(duì)，非常考耐心，細(xì)心的一道題目，這道題目充分的說(shuō)明我是考慮問(wèn)題不全面的人 所以現(xiàn)在看來(lái)TopCoder的測(cè)試數(shù)據(jù)還都算是比較弱的，真的沒(méi)有極其變態(tài)的，而且TopCoder的題目其實(shí)沒(méi)有超級(jí)復(fù)雜的，或許是因?yàn)槲覐膩?lái)沒(méi)做過(guò)第三題吧。 回正題。 這道題目其實(shí)一看就知道怎么做，但是就一個(gè)字煩 首先你要用FloodFill把所有的Cluster標(biāo)注出來(lái)，這個(gè)不難，而且速度很快，時(shí)間...  閱讀全文

發(fā)個(gè)網(wǎng)絡(luò)流的標(biāo)準(zhǔn)代碼，用的是BFS

外面自己套一個(gè)類就行了

capacity自己初始化放進(jìn)去就可以了

返回值在max_flow里面，有需要的話可以自己改成返回類型的

原來(lái)這道題目這么簡(jiǎn)單，記得當(dāng)年高中的時(shí)候做USACO的時(shí)候，好像最后就是卡在這道題目上面，然后就是NOIP了

然后我就傷心的告別了NOIP投向了好好學(xué)習(xí)的懷抱。

今天拿過(guò)來(lái)看還是沒(méi)什么思路，然后就去搜了一下解題報(bào)告。

其實(shí)這個(gè)題目無(wú)論如何也是要DFS的，因?yàn)槿思乙爿敵鋈康拇鸢?。這樣就不用怕了，最多就是剪剪枝。

但是最開(kāi)始沒(méi)有想到這一點(diǎn)。

問(wèn)題就在這個(gè)剪枝上，和怎么判斷合理的解上面。

方法就是，首先找到每一個(gè)Frame的四個(gè)角。

然后沿著這個(gè)Frame的每條邊走一下，如果有其他的字符，就是跟當(dāng)前Frame不同的字符，那么這個(gè)字符肯定是在當(dāng)前這個(gè)字符上層的。

這樣就能用一張表來(lái)確定上下關(guān)系，Above[i][j]，表示第i個(gè)字符在第j個(gè)字符上層

然后就是根據(jù)這張表來(lái)做一個(gè)DFS，這樣就可以了。

看了leokan的解題報(bào)告，說(shuō)還要floyd一下。

這樣做的目的無(wú)非也就是想確定兩兩之間的上下層關(guān)系罷了。

但是似乎沒(méi)這個(gè)必要，直接DFS就可以了。

Principles of Modeling

1. First, The choice of what models to create has a profound influence on how a problem is attacked and how a solution is shaped.
2. Second, Every model may be expressed at different levels of precision.
3. Third, The best models are connected to reality.
4. Fourth,No single model or view is sufficient. Every nontrivial system is best approached through a small set of nearly independent models with multiple viewpoints.

Three major elements:

1. the UML's basic building blocks
2. the rules that dictate how those building blocks may be put together
3. some common mechanisms that apply throughout the UML

The vocabulary of the UML encompasses three kinds of building blocks:

1. Things
2. Relationships
3. Diagrams

Three kinds of relationships that are most important: dependencies, generalizations, and associations.

1. Dependencies are using relationships. For example, pipes depend on the water heater to heat the water they carry.
2. Associations are structural relationships among instances. For example, rooms consist of walls and other things; walls themselves may have embedded doors and windows; pipes may pass through walls.
3. Generalizations connect generalized classes to more-specialized ones in what is known as subclass/superclass or child/parent relationships. For example, a picture window is a kind of window with very large, fixed panes; a patio window is a kind of window with panes that open side to side.

先自動(dòng)下載了新的控件

然后去用這個(gè)文件去注冊(cè)掉那個(gè)什么什么CAB

http://m.tkk7.com/Files/LittleDS/800A138F.rar

然后再去下載 xenroll.dll
去 cmd 運(yùn)行 regsvr32 xenroll.dll

然后就可以了，就可以導(dǎo)入數(shù)字證書(shū)了。