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