轉自：http://blog.csdn.net/littlekid/archive/2008/07/19/2677373.aspx
July_1
POJ1240 Pre-Post-erous!
http://acm.pku.edu.cn/JudgeOnline/problem?id=1240
對于一棵m叉樹，只知道先根序遍歷和后根序遍歷序列是不能得到確切的樹的結構的，但是可能的樹的結構有多少種？
遞歸地推：
如果根有n棵子樹，則共有C（m,n)種選擇；
然后再乘以每棵子樹可能的結構數目：乘法原理。
根據先根序遍歷和后根序遍歷序列可以劃分子樹和得到當前結點有多少子樹，這個不難想。
July_3
POJ Picnic Planning
http://acm.pku.edu.cn/JudgeOnline/problem?id=1639
度限制最小生成樹。
lrj《算法藝術與程序設計競賽》上有比較清楚解法，我看懂后照著敲了一個，結果花了一個下午才寫出來，整整300＋行（我寫代碼向來冗余,待整理），好在做出來了。
我的解法思路（大致照lrj的解法）：
1 先Prim+heap求最小生成樹塊；
2 然后添加0到各連通塊的最小邊；
3 然后通過h(t)求h(t+1)——關鍵部分：
枚舉2中未選的0的鄰邊，然后在形成的環中找最大邊刪除（這里跟lrj的不一樣，我作了一遍dfs找最大邊，最后刪邊也用dfs實現)。
終止條件為0的度數到達k或上邊的情況不能使生成樹總長減小。
這套方法太麻煩，由于題目數據范圍小，可以考慮換Kruscal實現。
July_4
POJ1041 John's trip
http://acm.pku.edu.cn/JudgeOnline/problem?id=1041
經典歐拉回路的題。
這個題目是為了攢一份歐拉回路標程寫的——這個題目是求歐拉回路而且多兩項要求：一是起點必須是第一條路徑的較小標號點，二是求出來的回路序列要是最小（每條路徑有一個標號）。
原來在USACO寫過一個求歐拉回路要求訪問點序列最小的的歐拉路，當時用矩陣實現，這樣歐拉路／歐拉回路基本會寫了——不過如果要非遞歸實現的話……
這個題目寫了半個上午——畢竟要求序列最小這一點換了好幾種想法……
July_12
炮兵陣地
source Noi2001 day2
http://acm.pku.edu.cn/JudgeOnline/problem?id=1185
這個題基本算我寫的第一個狀態壓縮DP的題目。
原來的時候把狀態壓縮DP想得很高深，一直不敢動，今天下定決心通過以前看過的一些思想的總結來寫這一類題目，寫完這個題后初步感覺狀態壓縮DP的主要特點就是狀態壓縮（廢話！但理解這句話用了這么幾個月）：除了對狀態的表示要壓縮起來表示之外與普通DP沒什么兩樣。
這個題目是個赤裸裸的狀態壓縮DP：直接按照題意狀態轉移就可以了——用二進制表示地形和當前行炮兵布局，一個狀態用兩層表示：上一行和當前行的炮兵布局。難想的一點是狀態怎么壓縮：其實可以用數組把一行的合法布局記錄下來，這樣100列也就60種狀態，記錄兩行狀態數不過3600，復雜度O（n*num^3)（num為狀態數）,最大100＊60＊60＊60＝216000，加上一些判斷其實很快的。
Wa了一次，忘記一直取最大值了。
Jul_13
POJ2817 WordStack
http://acm.pku.edu.cn/JudgeOnline/problem?id=2817
經典狀態壓縮DP。
求最長最長漢密爾頓路（非回路）。由于昨天開始做了幾個狀態壓縮的題目后，對這類題有點理解，加上這個題目基本上是赤裸裸的狀態轉移，很快寫過。
Wa了一次：由于開始求的是最長公共子序列長度（其實是最大對應相同的字母數）。
July_14
POJ 3164 Command Network
這個題目就是經典的最小樹形圖。
前幾天看到這個問題的朱劉算法好像很容易理解、很清晰，加上今天做題不順就寫了。
TJU 2248 也是求最小樹形圖，先做的這個（這個赤裸裸?。?br>http://acm.tju.edu.cn/toj/showp2248.html
寫了一個下午，原因是頭腦不清晰，代碼風格也不好，寫來寫去開始一直TLE，后來找了hdu的一個人的標程，發覺自己的思路沒錯，基本一樣……
查了好久，發現在找環后標記時標記了縮點為已經從圖中去除！
改了后WA，錯誤在于縮點時入邊出邊不分——對于入邊要減去dis[ pre[u] ][u]!
還有網上推薦的uva11185也過了
http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&page=show_problem&problem=2124
總結下做法：網上大家貼的算法都很清晰，有個圖更是明了，不過代碼還是長了點。。
wy的總結：
http://hi.baidu.com/wywcgs/blog/item/a1ce10f4a8fa366fdcc47462.html
算法圖解：
http://p.blog.csdn.net/images/p_blog_csdn_net/huangwei1024/tree_graph.JPG
July_15
POJ3368 Frequent values
我做得最暴力的線段樹了！本來想試試結果過了。標準解法是RMQ的st算法。
其實感覺這兩個東西還是很相像的，覺得如果不是卡內存時間過緊的話，一般的RMQ（就是我目前能作的白癡RMQ）都可以用線段樹干掉。
太暴力了，線段樹上直接維護了最左邊和最右邊的值和出現次數和本區間的最大重復值的次數——5個數值！??！然后用RMQ的方法合并，就跟我們正常思維一樣，新合并區間的最大數值出現次數會是左右節點和中間數值的重復次數中最大的一個，思路清晰就好寫了。
POJ3321 Apple_tree
http://acm.pku.edu.cn/JudgeOnline/problem?id=3321
第一次做樹狀數組的題目，不過值得學習的卻是樹遍歷的特點。
這個題目開始以為用線段樹做（其實是可以的?。?由于想了很久也沒有想到怎么來將樹的結構排序，就看了Discuss，發現樹狀數組也可以——想到從沒寫過，然后就去找文章看……
題目關鍵不在數據結構（用的是標準的樹狀數組或線段樹），關于排序的思想很重要：先根序遍歷，對每個節點記錄其序號和其子樹的最大序號（也就是標記一棵樹遍歷的第一個和最后一個節點的遍歷序號st、ed）。
統計一個節點為根的樹中數目時，直接計算1到st－1、ed的數組和然后相減即可。
POJ1204 Word Puzzles
這個題目其實還是個簡單題——直接寫個Trie就好了。不過我還是RE了不少次數：原因是忘記初始化指針指向NULL了！！??！弱智啊～～
不過做了這個題目我在POJ上的little id-->R2D2的題數就與littlekid這個帳號一樣了。將兩個號一合計：在POJ上也算AC了有283題了，＋U，fighting！
July_16
POJ1037
動態規劃＋遞推。
這個題目去年第一次看到就推出了那個算n個柵欄以第i短的為第一根下一根放短的or長的柵欄的方案數。
f[n][1][0] = 0; f[1][1][1] = 1;
f[n][i][0] = f[n-1][i-1][0]+f[n-1][i-1][1];
f[n][i][1] = f[n][n+1-i][0];
麻煩的是求具體方案。
求第一根柵欄還是很好求的——直接從f[n][1][0]、f[n][1][1]……一直減，找到i和類型（短/長）。
維護一個集合為未選柵欄
中間的遞推比較麻煩：若類型為短，從1減、否則從上次得到的i向上減。（－f[t_len{后邊長度}][i][type])。
找到位置i后輸出第i小的數。
總之這個題目很考遞推能力——推了幾個小時還是錯了一點，最后discuss里那個人的程序遞歸實現的還是幫了大忙！
這個題目思想很好，以后要回來溫習。
July_16
POJ 1077 Eight
經典搜索題。
這個題目可以用一般BFS，A＊，雙向BFS……等方法做。
原來寫過BFS版本，今天寫了個雙向BFS——畢竟聽說過這個名詞以來還沒寫過。
其實雙向BFS真的很簡單：就是BFS的時候同時從目標和初始狀態做BFS，關鍵的地方在于判斷當前搜索出來的狀態是否在另外一棵搜索樹中出現（這里借用 Hash判斷，對每個狀態hash時記錄其在隊列中位置，利用位置關系判斷——比如我開一個隊列，初始狀態從0向后[head1,tail1),目標狀態從最后向前(tail2,head2], 如果一個節點出現在另外一個區間，就找到解了)。
這樣0ms，普通600＋ms,真的很強大……
不過很費空間（本人不幸0ms用空間最多），下次學了A＊再做。
July_17
July_1195
POJ1195 Mobile phones
source IOI2001
經典二維樹狀數組題。
前邊做過一個一維的樹狀數組題目，就想當然地擴展到二維了，結果郁悶地WA了幾次。
找來解題報告看，發現二維的樹狀數組麻煩多了，要控制的東西還不少：不過目前還是不很明白……
照著別人程序寫了個，AC了，
June_2
http://acm.pku.edu.cn/JudgeOnline/problem?id=3026
Borg Maze
最小生成樹。
這個題目本來是簡單題，結果由于疏忽，寫了兩個多小時……
犯了一個弱智錯誤：數組開小了，不過由于G＋＋不報錯，得到詭異的錯誤……
讓我想起寒假時候HDU給我不報RE報TLE的事情了。
June_5
POJ1011／WOJ1212 Sticks
經典搜索題。
這個題目做了很久——去年暑假個人賽模擬賽第一次接觸，當時沒做出來，不過后來模仿別人程序把POJ1011過了，不過WOJ1212卻是TLE。
最近幾天看了下《算法藝術與程序設計競賽》上的減枝方法，總算弄清楚了，今天早上寫了一下……
大體框架為DFS，最重要的是減枝。
下面是我的一些減枝：
1、要得到的Sticks長度必定為總長度的約數——這個好想；
2、對blocks按長度由小到大排序（原來也排了，當時不知道為什么要排——為了減枝）；
3、搜索順序為：
用blocks去組成sticks，
減枝一：按照組成sticks的最長block排序（由大到小），這個可以證明的，而且剩下的blocks中最長block一定要選擇；
減枝二：組成每根sticks時按從大到小枚舉，如果可行則當前方案一定是最后方案(理解這個我用了比較久，其實就是如果有另外的另兩根短的blocks可替換的方案存在，那么長blocks放在后面也是對的，如果固定在前面，可減少不少）;
減枝三：對于長度相同的blocks，如果當前用其中一根組成當前sticks不能得到結果，那么當前的選擇要跳過所有的這些blocks（這個從搜索樹上理解就好了——畫出一棵搜索樹，會發現這些blocks為根的子樹完全相同）；
這樣就可以過了，WOJ1212 15+s, POJ1011 0MS.
trick：由于woj1212只卡時間，我用了一個錯誤的減枝（很弱智，也就不說了）得到了5MS的程序（當然在POJ1011上WA了）。建議做這題要把兩個地方的題目都AC了。
要好好地理解這個題目的方法——我學到的最重要的是從狀態搜索樹的特點上剪枝。
June_5
HUST1019 A dangerous trip
http://acm.hust.edu.cn/thx/problem.php?id=1019
這個基本代表了一類題目了——與校賽的Path（WOJ1352）的最短奇偶路徑相似。
方法很簡單：
對每個點保存兩個值，做兩遍最短路：
第一次普通最長路，
第二遍做最短路時，對所有邊枚舉其縮到一半的情況，具體就是：
Dist[p->v][1] = min(Dist[i][0]+p->len/2.0, Dist[i][1]+p->len)
別的沒什么好說的，這個題目是簡單題。
June_9
Cashier Employment
http://acm.pku.edu.cn/JudgeOnline/problem?id=1275
差分約束問題。
這種題目難的地方就是建圖，這個題目特殊的地方是得到最后的不等式中第23小時不好處理，那么就枚舉啦（數據范圍不大，二分也是可以的）。
不過有個地方還沒懂——我建圖后枚舉用bellman—ford后如果滿足約束就返回true錯了，改為馮威的論文上的!=4的約束條件就AC了——有什么trick？
總結一下差分約束問題：先對題目建立模型，然后抽出不等式，再整理成差分約束標準形，最后bellman－ford檢查約束條件。 差分約束簡單類題目就這么搞了，難的變化大，目前搞不定，需要多見識積累經驗……
June_29
Reset Sequence
POJ Monthly June 2008
http://acm.pku.edu.cn/JudgeOnline/problem?id=3609
題目意思是有n種狀態和m種命令（2<=n<=8, 1<=m<=16)，然后給出一個n＊m的矩陣，表示在狀態i下面接受到命令j則改變到狀態a[i][j]。目標是求一最短序列滿足：在任何初始狀態下，通過執行這一命令序列后都到達狀態0。
今天狀態不好（畢竟近20天沒寫題了），看到這個題目后沒有想法，oldmaner也認為只能窮舉，然后我寫了上去居然WA了（沒有TLE），就在考慮是否漏了情況，未果。
后來改模型，居然推出一個狀態DP的模型，還好很快由此想到了圖論——這個題目是個簡單題。
解法：由于n很小，所以可以對在執行了一系列命令后的狀態用一個頂點表示（就是一個2進制數標號，對應位為1表示當前的狀態——開始時處于1111狀態，最后處于0111狀態）。
后面就很簡單的建圖：如果從某一狀態u可以通過命令j轉換到狀態v，則在u和v間連一條邊（“權”為1，標志為j）。
最后就是跑一個最短路。
May_26
ZJU2588
http://acm.zju.edu.cn/show_problem.php?pid=2588
這個題目做了比較長的時間，
為了它先學習了一下無向圖的橋，不過沒有過～～這個題目不一樣的地方是有些點之間不只一條邊；
今天想到hash判重（這么簡單的思想原來怎么就沒想到呢？）
MLE兩次，hash數組開大了
這之后WA了一次——如果沒有橋后輸出空行，我的程序為了控制另外一點（末尾沒有多余空格）而輸出了0
程序目前時間不夠快……
72 2008-05-26 15:22:34 00:01.45 23752K C++ littlekid
Delete the comments
http://acm.fzu.edu.cn/problem.php?pid=1604
簡單題，直接模擬做
比賽當時wa了，第二天繼續做，開始TLE，后來優化了一下就過了：
對于"/*"找其配對的"*/"，如果沒找到以后就不用再找了。
教訓：當時wa的原因是程序程序寫得太亂（自己思路不是很清晰）——寫代碼前想清楚，代碼前先上注釋
May_28
POJ3159
http://acm.pku.edu.cn/JudgeOnline/problem?id=3159
這個題目是很久以前據開始做了，第一次用O（n^2）的算法自然TLE，后來學了加堆優化的Dijstra還是沒有過，都把堆的各種操作優化了，位運算也上了，交了好多次。
昨天上數據結構的時候看到用數組模擬指針，突然想到會不會是用new或malloc太慢，用靜態指針？今天寫了個數組模擬指針，果然過了，1032ms，還是有點慢——那些100＋ms的是怎么弄的，下次請教下～～
May_29
POJ1144
這個題目就是求無向圖的關節點（或割點），前幾天就寫好了算法，不過WA了，然后這幾天就一直懷疑
自己的算法寫錯了，不斷找bug，不過找不到～
后來看到Discuss里的數據果然過不了，——
今天上網查了別人的算法，人家非常暴力的算法都過了……不過最后終于發現自己的錯誤——讀入處理錯了，看錯題了，又一次死在讀入處理上——不過這次不是不會處理，而是看錯題了
（第一個數代表后面數相連頂點，我弱智地處理了，具體就不說了）
下次不能犯這么弱智的錯誤
May_31
POJ3352 Road Construction
http://acm.pku.edu.cn/JudgeOnline/problem?id=3352
這個題目第一次看到是在去年暑假組隊賽——當時一直想著怎么DFS硬搞（當時除了硬搞什么都不會）。
上一周開始思考這個題目，做了幾個割點和割邊的題目后開始做這個題目：
用了求割邊然后縮點的方法，
結果為（葉子節點數＋1）／2。
開始wa了——只是記錄葉子節點，忘記考慮根也可能算一個特殊的葉子節點。
記得今年中南賽A題也是忘記考慮根節點情況郁悶了！
POJ3649
模擬題。
這個題加深了我對于模擬題的理解。
關鍵在于讀懂題意，思路清晰。
這個題目的關鍵在于理解題，然后計算移動：先計算每個圖形的最左最右位置，再把
每一格把所有的圖形按規則計算向左移動的格數，然后再根據移動的最左坐標建立新
圖像，最后根據規則去掉不輸出的前導后續空白輸出,一直在做算術。
July_22
POJ3662
這個題目很好。
題目意思是對于一個圖求一條從源點到終點的路徑滿足：第k＋1長的邊最短。
當時想了半天也只想到優先隊列廣搜，結果自己代碼能力挫＋比賽中還有另一題卡
著，沒有做出來（這樣是可以的，NUDT的Alpc55就這么過了，代碼能力牛!)。
后來晚上想到二分一個len，然后把距離大于len的邊全部賦值為0（其實就是作
Dijstra的時候判斷），小于的賦值為1，求最短路是否與k的關系。
圖模型的轉換博大精深……
July_23
POJ2866 樹形DP
這個題思路沒什么好說的，關鍵地方在于看到題目提到幾何坐標時不要怕：這個題目
我開始時有點怕，不過看完之后一下就想到思路了——如果開始怕幾何那么這個題目
就會很晚出了。
July_23
POJ2547 No Tipping
集合DP。
比賽時候沒做出來——當時我們估計了搜索的時間復雜度明顯不行，然后還是寫了！
其實看到數據<=20應該就要敏感點地知道要集合DP了，想到這里就好辦了。
沒有trick的題目：不過對數據的敏感和集合DP的思想意識要加強。
July_23
POJ1103 Maze
在TOJ跟ALPC做比賽的題目，當時想出來的——這個題目關鍵在于建圖，而建
圖的關鍵在于標號：按照題意劃分區域，‘／’和‘\'分別代表不同的涉及的四個區
域的不同連接關系。
最后可以證明除了邊界區域，一個區域與正好兩個區域相連通，故建圖后先從邊
界區域出發dfs將所有能到達的區域標記出為訪問，然后再以沒有訪問過的點開始
dfs走圈計數。
還不錯的一道題。
July_23
POJ2169
圖模型轉換＋最短路
題目的模型轉化思想很經典：原來給的就是一個圖，但是要選擇兩個相鄰（有邊直接
相連）的頂點——一個狀態，從一個狀態可以依照條件通過一定步數轉移到另一個合
法狀態，
求從一個初始狀態到終結狀態的最少步數。
轉化思想：建立一個新圖，將原圖的一條邊轉化為新圖中的一個頂點，對于原圖中每
個合法的轉移建立一條有向邊，然后在新圖中求s－t最短路。
trick：這個題比賽時我們雖然想到解法，但代碼能力問題加卡其他題，并未做出此
題。
賽后在TOJ將它AC后到POJ提交發現TLE，然后在ZOJ發現MLE。
后來發現我用了new，POJ又把卡new了，然后改成數組就過了。
至于ZOJ，目前還是MLE，我用了40000K左右內存，它自由32767k！可見我
的模型還不夠好…… 待改進.
通過這個題的經驗，又把原來卡的3013也過了。
通過好幾個題：3013 3159 2169
發現如果遇到圖論題，還是不要用new malloc的好，數組模擬指針還是快很多——
雖然沒那么方便。
July_24
POJ1885
線段樹模型
今天跟alpc在TOJ做比賽的題目，好題一道。
題目的模型是現椴樹，讀入單詞為插入節點，遇到數字后在前邊找節點，再將前
邊的單詞復制過來到最后一個位置（當前，而且不必真的復制，直接保存一個link
就可以了），并標記找到原單詞從列表中去除。
這個題有個trick：輸入的文件中最多10000個單詞，但是數字卻非常多，最后得
到的結果單詞數比10000大很多……
July_24 Software Company
二分＋DP。
先二分一個時間上界T，然后DP看是否可以在T時間內做完所有子工程。
狀態表示及轉移：
f[k＋1][t][i]表示前k個人都用了時間T工作，第k＋1個人工作t時間時完成i個A公
司的項目時最多能完成B
公司項目數目。
f[k+1][0][i] = f[k][T][i];
f[k][t][i] = max(f[k][t-1][i], f[k][ t-cost[k][A] ][i-1],
f[k][ t-cost[k][B] ][i]+1);
dp好想，二分的思想很重要。
July_25
POJ3666
DP＋離散化
做得很不爽的一道題——我太sb了，居然被數據蒙騙了，沒有想到什么好方法，直到
比賽還剩下20多分鐘才想到離散話，加上代碼速度慢了點，沒有寫出來。
對題意的挖掘最重要的一點在于：
一個點的最后高度Bi必定是A數組中的某個高度——可以證明：一個點要么保持原
有高度，要么向上或向下到最接近他的高度。
離散化后就是O(n^2)的DP，加點優化（記錄一下前一個點的高度小于（大于）某個
高度的最小值）就好了。
Jul_27
POJ3667 Hotel
很好的線段樹題目——一個比賽時留下的怨念：當時大家都沒想法，我試著敲這
個題目，結果TLE了。
這個題目我的想法是對的：直接維護線段樹（區間樹）的查找、刪除、添加操作。
由于查找的是大于指定長度k的最左空白的連續區間，故節點有lmax,rmax,cmax三
個值，還有必要的區間長度、范圍的信息（這個一個可以推另一個）。
TLE的原因很弱智：對于一個區間整體的覆蓋或刪除不必先下到子區間，等要改變
子區間時才將區間信息往下傳；合并子區間也是麻煩的（不過當時寫對了），細細推
敲就可以了。
區間合并和信息下傳的思想！
July_29
Sudoku數獨
exact cover problem（覆蓋模型）
POJ3076 POJ2676 POJ3074
前段看了Knuth的Dancing Links的論文大致了解了一下阿，昨天看了下mmd的集
訓論文，試著把Hust OJ上的1017那個extra Cover problem給過了，然后今天就
開始寫mmd推薦的sudoku。
數獨轉化為extra cover的模型（以9＊9為例）：
行代表每個格子要填的數的可能：9＊9＊9
列代表限制條件： 81＋9＊9＋9＊9＋9＊9
//限制1：一個格子一個數
//限制2：一列數不重復
//限制3：一行數不重復
//限制４:一個3＊3的塊數不重復
Jul_30
POJ 2252
一階方程求解
重點在于對表達式求值
由于一定不高于一階，可以用復數的表示方法存儲。
這類題目都做出套路了：遞歸。
加深對“編譯原理”的理解。
July_30
POJ2677 Tour
經典DP CLRS上的題目 模擬兩個人走來解
狀態設計：f[i][j]（j<i)
f[i][j] = min(f[i-1][k]+dis[k][i]) k=1,2,...,i-2 j=i-1
f[i][j] = f[i-1][j]+dis[i-1][i] j<i-1