用了大概一個半月的時間吧，當然中間有大概一個禮拜空著來著

這是第二次做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我估計我這輩子都不會忘記了。

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

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

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

這個題目是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]

不知道我解釋清楚了沒，其實解釋了一遍，自己也清楚了很多。

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

感想及題解待會兒再發：）

這道題用了離散化的方法

其實最樸素的方法就是在一個20000*20000的矩陣上面把所有的點描出來，然后把這些點的周長算出來，不過算周長這一步也是很麻煩的。

因為畢竟還有可能出現“空心”的情況

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

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

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

先把橫邊全部選出來，放在一個數組里面，然后排序，從下到上。

一個矩形的兩條邊要分成始邊和終邊，排序的時候，如果縱坐標相同，那么應該把始邊放在終邊。

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

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

于是，當一條邊上的點的leve是1的時候，那么就說明這條邊肯定是始邊邊緣，所以要ans++

另一種情況，當一條邊上的點的level是0的時候，那么說明這個點是終邊邊緣，所以ans++

這樣掃完橫邊再掃豎邊。

最后的ans就是周長了。

不過這個算法的時間效率并不是非常的好，因為數據比較弱（可能是這樣）

如果真的是有5000個矩形，沒個矩形都是20000×20000的，那么可能會超時

雖然從5.1開始，大部分題目都要借助于NoCow和網上的解題報告，但是還是學到了不少的東西。

原來認為只要熟練的掌握各種算法，那就可以隨便去切題，現在發現其實不是這樣。

有很多題目，都需要進行一些轉化，也可以說是建模，才能套用現成的算法

而有一些題目，根本就沒有現成的算法，只能你自己去想

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

還有一些比如說剪枝，雖然搜索誰都會，Brute Force誰都會寫，但是剪枝卻不是誰都能寫的出來的

這就需要一些數學功底

現在發現這個東西必須要長年累月的積累才能夠達到駕輕就熟的境界。

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

這道題目我自己看出來是最小割的問題，而之前的題目有一道是最小割的

但是有一個不同，這道題是點的最小割，而不是常規的邊的最小割

所以這就比較麻煩，需要我們把點轉化成邊

這就讓我想起了之前的那個Fence Loops

我就是把所有的邊表示的圖轉化成了點表示的圖，我實在是不想再寫那么惡心的算法了。

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

具體方法就是，把一個點變成兩個點，然后在兩個點之間加一條邊，并且這條邊的權值是1

這樣的話，如果割這條邊，就相當于去掉了這個點。

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

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

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

就這樣把所有的最小割找出來，然后就可以了

貌似數據很弱，不像上次的那個Pollute那道題目，還要考慮邊的編號的問題的。

一個搜索的題目，不過肯定是要剪枝的

最簡單的兩個剪枝我想到了

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

他們的一個全排列就對應著一種組合，所以最后的答案乘以N-1的階乘就可以

第二個：
這個其實是看來的，就是每次只要所搜完N-1行就可以了。因為剩下的一行必然存在一個解。其實這個不難理解的，最后一行的排列順序只跟前面的每一列缺少的那個數有關。

而且也只能取缺少的那個數，所以也就是唯一的。

第三個：
要用到置換群，我沒看懂

盡管之前N次看組合數學里面都說到置換群，但是我還是似懂非懂，問了數學小王子，他也不是非常懂。然后以為這個東西沒用，就忽略了。沒想到還真的有用。

今天終于第一次寫了強連通分量的題目

雖然以前老早就知道有這么個東西，對這個東西也有概念，但是確實從來沒有寫過判別的算法

原來如此簡單，但是確實也很巧妙。

在算法導論上面看到的K算法，方法就是做兩遍DFS，因為強連通分量有一個性質，就是如果把所有的邊反向，那么它仍然是一個強連通分量。

但是今天我用的是Tarjan算法，據說效率比K算法高很多，事實上也應該是這樣，因為Tarjan算法只做了一次DFS

其實思想也很簡單，就是一直DFS（u），向下向下向下，如果突然發現有一個點可以回到u了，那么這個肯定是一個強連通分量。

哈哈，是不是很通俗。

嚴格的定義過程大家可以看這里http://www.cmykrgb123.cn/blog/scc-tarjan/

我也是參考了這個才做出來的Tarjan算法，Wiki上的那個過于龐大了，雖然封裝的非常好

說說本題，其實就是找強連通分量，然后把每個強連通分量當成一個“超點”來考慮

如果這個“超點”的入度為零，那么它就必然是一個源頭，統計這樣的“超點”的個數，就是第一問的答案。

第二問，如果有一個“超點”入度不是0，但是出度是0，那就說明這個“超點”可以給其他“超點”作貢獻。

我們就找這樣的點對，把入度是0和出度是0的點連起來。

這樣匹配過后，剩下的要么全是入度是0的，要么全是出度是0的，這些就沒辦法了，隨便從一個連通分量連接過來一條邊就可以了。

所以第二問的答案就是所有的“超點”中，入度是0和出度是0的點大的那個數。

應該算是一個比較基本的DP吧，狀態轉移方程也不難想，但是我最開始寫成了N^3的了

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

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

然后對于i，j，我們需要觀察i - 1，j - 1，因為是square，所以只跟這個有關

如果在第i行，第j列上面，從當前位置開始，連續map[i-1][j-1]個位置，沒有#的話，那么map[i][j] = map[i-1][j-1]+1

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

這個地方完全沒必要用循環一個一個去判斷，因為其實你已經有結果了，這個結果就是map[i-1][j]和map[i][j-1]里面小的那個

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

因為這時候實際上你已經確定了，#只有可能出現在第i行，第j列上，因為map[i-1][j-1]不是#就保證了這一點

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

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

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

只需要檢查這兩個就可以

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

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

否則，我們的square最大也就只能是map[i-1][j-1]+1，因為map[i-1][j-1]已經是以i-1,j-1為右下角最大的square了

于是狀態轉移方程就是

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

     摘要: 絕對，非常考耐心，細心的一道題目，這道題目充分的說明我是考慮問題不全面的人 所以現在看來TopCoder的測試數據還都算是比較弱的，真的沒有極其變態的，而且TopCoder的題目其實沒有超級復雜的，或許是因為我從來沒做過第三題吧。 回正題。 這道題目其實一看就知道怎么做，但是就一個字煩 首先你要用FloodFill把所有的Cluster標注出來，這個不難，而且速度很快，時間...  閱讀全文

發個網絡流的標準代碼，用的是BFS

外面自己套一個類就行了

capacity自己初始化放進去就可以了

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

原來這道題目這么簡單，記得當年高中的時候做USACO的時候，好像最后就是卡在這道題目上面，然后就是NOIP了

然后我就傷心的告別了NOIP投向了好好學習的懷抱。

今天拿過來看還是沒什么思路，然后就去搜了一下解題報告。

其實這個題目無論如何也是要DFS的，因為人家要你輸出全部的答案。這樣就不用怕了，最多就是剪剪枝。

但是最開始沒有想到這一點。

問題就在這個剪枝上，和怎么判斷合理的解上面。

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

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

這樣就能用一張表來確定上下關系，Above[i][j]，表示第i個字符在第j個字符上層

然后就是根據這張表來做一個DFS，這樣就可以了。

看了leokan的解題報告，說還要floyd一下。

這樣做的目的無非也就是想確定兩兩之間的上下層關系罷了。

但是似乎沒這個必要，直接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.