轉(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叉樹(shù)，只知道先根序遍歷和后根序遍歷序列是不能得到確切的樹(shù)的結(jié)構(gòu)的，但是可能的樹(shù)的結(jié)構(gòu)有多少種？
 
  遞歸地推：
  如果根有n棵子樹(shù)，則共有C（m,n)種選擇；
  然后再乘以每棵子樹(shù)可能的結(jié)構(gòu)數(shù)目：乘法原理。

  根據(jù)先根序遍歷和后根序遍歷序列可以劃分子樹(shù)和得到當(dāng)前結(jié)點(diǎn)有多少子樹(shù)，這個(gè)不難想。




July_3
POJ Picnic Planning

http://acm.pku.edu.cn/JudgeOnline/problem?id=1639

  度限制最小生成樹(shù)。

  lrj《算法藝術(shù)與程序設(shè)計(jì)競(jìng)賽》上有比較清楚解法，我看懂后照著敲了一個(gè)，結(jié)果花了一個(gè)下午才寫(xiě)出來(lái)，整整300＋行（我寫(xiě)代碼向來(lái)冗余,待整理），好在做出來(lái)了。

  我的解法思路（大致照l(shuí)rj的解法）：
 1 先Prim+heap求最小生成樹(shù)塊；
 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或上邊的情況不能使生成樹(shù)總長(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)程寫(xiě)的——這個(gè)題目是求歐拉回路而且多兩項(xiàng)要求：一是起點(diǎn)必須是第一條路徑的較小標(biāo)號(hào)點(diǎn)，二是求出來(lái)的回路序列要是最小（每條路徑有一個(gè)標(biāo)號(hào)）。
  原來(lái)在USACO寫(xiě)過(guò)一個(gè)求歐拉回路要求訪問(wèn)點(diǎn)序列最小的的歐拉路，當(dāng)時(shí)用矩陣實(shí)現(xiàn)，這樣歐拉路／歐拉回路基本會(huì)寫(xiě)了——不過(guò)如果要非遞歸實(shí)現(xiàn)的話……

  這個(gè)題目寫(xiě)了半個(gè)上午——畢竟要求序列最小這一點(diǎn)換了好幾種想法……


July_12
炮兵陣地

source Noi2001 day2
http://acm.pku.edu.cn/JudgeOnline/problem?id=1185

  這個(gè)題基本算我寫(xiě)的第一個(gè)狀態(tài)壓縮DP的題目。

   原來(lái)的時(shí)候把狀態(tài)壓縮DP想得很高深，一直不敢動(dòng)，今天下定決心通過(guò)以前看過(guò)的一些思想的總結(jié)來(lái)寫(xiě)這一類(lèi)題目，寫(xiě)完這個(gè)題后初步感覺(jué)狀態(tài)壓縮DP的主要特點(diǎn)就是狀態(tài)壓縮（廢話！但理解這句話用了這么幾個(gè)月）：除了對(duì)狀態(tài)的表示要壓縮起來(lái)表示之外與普通DP沒(méi)什么兩樣。

 這個(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)漢密爾頓路（非回路）。由于昨天開(kāi)始做了幾個(gè)狀態(tài)壓縮的題目后，對(duì)這類(lèi)題有點(diǎn)理解，加上這個(gè)題目基本上是赤裸裸的狀態(tài)轉(zhuǎn)移，很快寫(xiě)過(guò)。
  Wa了一次：由于開(kāi)始求的是最長(zhǎng)公共子序列長(zhǎng)度（其實(shí)是最大對(duì)應(yīng)相同的字母數(shù)）。


July_14

POJ 3164 Command Network


  這個(gè)題目就是經(jīng)典的最小樹(shù)形圖。
 
  前幾天看到這個(gè)問(wèn)題的朱劉算法好像很容易理解、很清晰，加上今天做題不順就寫(xiě)了。
 
TJU 2248 也是求最小樹(shù)形圖，先做的這個(gè)（這個(gè)赤裸裸！）
http://acm.tju.edu.cn/toj/showp2248.html

  寫(xiě)了一個(gè)下午，原因是頭腦不清晰，代碼風(fēng)格也不好，寫(xiě)來(lái)寫(xiě)去開(kāi)始一直TLE，后來(lái)找了hdu的一個(gè)人的標(biāo)程，發(fā)覺(jué)自己的思路沒(méi)錯(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


  我做得最暴力的線段樹(shù)了！本來(lái)想試試結(jié)果過(guò)了。標(biāo)準(zhǔn)解法是RMQ的st算法。

  其實(shí)感覺(jué)這兩個(gè)東西還是很相像的，覺(jué)得如果不是卡內(nèi)存時(shí)間過(guò)緊的話，一般的RMQ（就是我目前能作的白癡RMQ）都可以用線段樹(shù)干掉。

  太暴力了，線段樹(shù)上直接維護(hù)了最左邊和最右邊的值和出現(xiàn)次數(shù)和本區(qū)間的最大重復(fù)值的次數(shù)——5個(gè)數(shù)值！！！然后用RMQ的方法合并，就跟我們正常思維一樣，新合并區(qū)間的最大數(shù)值出現(xiàn)次數(shù)會(huì)是左右節(jié)點(diǎn)和中間數(shù)值的重復(fù)次數(shù)中最大的一個(gè)，思路清晰就好寫(xiě)了。


POJ3321 Apple_tree
http://acm.pku.edu.cn/JudgeOnline/problem?id=3321

  第一次做樹(shù)狀數(shù)組的題目，不過(guò)值得學(xué)習(xí)的卻是樹(shù)遍歷的特點(diǎn)。

  這個(gè)題目開(kāi)始以為用線段樹(shù)做（其實(shí)是可以的！） 由于想了很久也沒(méi)有想到怎么來(lái)將樹(shù)的結(jié)構(gòu)排序，就看了Discuss，發(fā)現(xiàn)樹(shù)狀數(shù)組也可以——想到從沒(méi)寫(xiě)過(guò)，然后就去找文章看……

  題目關(guān)鍵不在數(shù)據(jù)結(jié)構(gòu)（用的是標(biāo)準(zhǔn)的樹(shù)狀數(shù)組或線段樹(shù)），關(guān)于排序的思想很重要：先根序遍歷，對(duì)每個(gè)節(jié)點(diǎn)記錄其序號(hào)和其子樹(shù)的最大序號(hào)（也就是標(biāo)記一棵樹(shù)遍歷的第一個(gè)和最后一個(gè)節(jié)點(diǎn)的遍歷序號(hào)st、ed）。
  統(tǒng)計(jì)一個(gè)節(jié)點(diǎn)為根的樹(shù)中數(shù)目時(shí)，直接計(jì)算1到st－1、ed的數(shù)組和然后相減即可。


POJ1204 Word Puzzles

  這個(gè)題目其實(shí)還是個(gè)簡(jiǎn)單題——直接寫(xiě)個(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和類(lèi)型（短/長(zhǎng)）。

 維護(hù)一個(gè)集合為未選柵欄
 中間的遞推比較麻煩：若類(lèi)型為短，從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)寫(xiě)過(guò)BFS版本，今天寫(xiě)了個(gè)雙向BFS——畢竟聽(tīng)說(shuō)過(guò)這個(gè)名詞以來(lái)還沒(méi)寫(xiě)過(guò)。

其實(shí)雙向BFS真的很簡(jiǎn)單：就是BFS的時(shí)候同時(shí)從目標(biāo)和初始狀態(tài)做BFS，關(guān)鍵的地方在于判斷當(dāng)前搜索出來(lái)的狀態(tài)是否在另外一棵搜索樹(shù)中出現(xiàn)（這里借用 Hash判斷，對(duì)每個(gè)狀態(tài)hash時(shí)記錄其在隊(duì)列中位置，利用位置關(guān)系判斷——比如我開(kāi)一個(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ù)狀數(shù)組題。

  前邊做過(guò)一個(gè)一維的樹(shù)狀數(shù)組題目，就想當(dāng)然地?cái)U(kuò)展到二維了，結(jié)果郁悶地WA了幾次。

  找來(lái)解題報(bào)告看，發(fā)現(xiàn)二維的樹(shù)狀數(shù)組麻煩多了，要控制的東西還不少：不過(guò)目前還是不很明白……

  照著別人程序?qū)懥藗€(gè)，AC了，

 
June_2
http://acm.pku.edu.cn/JudgeOnline/problem?id=3026

Borg Maze

最小生成樹(shù)。

這個(gè)題目本來(lái)是簡(jiǎn)單題，結(jié)果由于疏忽，寫(xiě)了兩個(gè)多小時(shí)……

犯了一個(gè)弱智錯(cuò)誤：數(shù)組開(kāi)小了，不過(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í)沒(méi)做出來(lái)，不過(guò)后來(lái)模仿別人程序把POJ1011過(guò)了，不過(guò)WOJ1212卻是TLE。

最近幾天看了下《算法藝術(shù)與程序設(shè)計(jì)競(jìng)賽》上的減枝方法，總算弄清楚了，今天早上寫(xiě)了一下……

大體框架為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è)從搜索樹(shù)上理解就好了——畫(huà)出一棵搜索樹(shù)，會(huì)發(fā)現(xiàn)這些blocks為根的子樹(shù)完全相同）；

這樣就可以過(guò)了，WOJ1212 15+s, POJ1011 0MS.

trick：由于woj1212只卡時(shí)間，我用了一個(gè)錯(cuò)誤的減枝（很弱智，也就不說(shuō)了）得到了5MS的程序（當(dāng)然在POJ1011上WA了）。建議做這題要把兩個(gè)地方的題目都AC了。

要好好地理解這個(gè)題目的方法——我學(xué)到的最重要的是從狀態(tài)搜索樹(shù)的特點(diǎn)上剪枝。







June_5
HUST1019 A dangerous trip

http://acm.hust.edu.cn/thx/problem.php?id=1019

這個(gè)基本代表了一類(lèi)題目了——與校賽的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)

別的沒(méi)什么好說(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è)地方還沒(méi)懂——我建圖后枚舉用bellman—ford后如果滿足約束就返回true錯(cuò)了，改為馮威的論文上的!=4的約束條件就AC了——有什么trick？
 
  總結(jié)一下差分約束問(wèn)題：先對(duì)題目建立模型，然后抽出不等式，再整理成差分約束標(biāo)準(zhǔn)形，最后bellman－ford檢查約束條件。  差分約束簡(jiǎn)單類(lèi)題目就這么搞了，難的變化大，目前搞不定，需要多見(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天沒(méi)寫(xiě)題了），看到這個(gè)題目后沒(méi)有想法，oldmaner也認(rèn)為只能窮舉，然后我寫(xiě)了上去居然WA了（沒(méi)有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)——開(kā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ò)沒(méi)有過(guò)～～這個(gè)題目不一樣的地方是有些點(diǎn)之間不只一條邊；
今天想到hash判重（這么簡(jiǎn)單的思想原來(lái)怎么就沒(méi)想到呢？）
MLE兩次，hash數(shù)組開(kāi)大了
這之后WA了一次——如果沒(méi)有橋后輸出空行，我的程序?yàn)榱丝刂屏硗庖稽c(diǎn)（末尾沒(méi)有多余空格）而輸出了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ù)做，開(kāi)始TLE，后來(lái)優(yōu)化了一下就過(guò)了：
對(duì)于"/*"找其配對(duì)的"*/"，如果沒(méi)找到以后就不用再找了。


教訓(xùn)：當(dāng)時(shí)wa的原因是程序程序?qū)懙锰珌y（自己思路不是很清晰）——寫(xiě)代碼前想清楚，代碼前先上注釋










May_28

POJ3159

http://acm.pku.edu.cn/JudgeOnline/problem?id=3159

這個(gè)題目是很久以前據(jù)開(kāi)始做了，第一次用O（n^2）的算法自然TLE，后來(lái)學(xué)了加堆優(yōu)化的Dijstra還是沒(méi)有過(guò)，都把堆的各種操作優(yōu)化了，位運(yùn)算也上了，交了好多次。
昨天上數(shù)據(jù)結(jié)構(gòu)的時(shí)候看到用數(shù)組模擬指針，突然想到會(huì)不會(huì)是用new或malloc太慢，用靜態(tài)指針？今天寫(xiě)了個(gè)數(shù)組模擬指針，果然過(guò)了，1032ms，還是有點(diǎn)慢——那些100＋ms的是怎么弄的，下次請(qǐng)教下～～
May_29

POJ1144

這個(gè)題目就是求無(wú)向圖的關(guān)節(jié)點(diǎn)（或割點(diǎn)），前幾天就寫(xiě)好了算法，不過(guò)WA了，然后這幾天就一直懷疑
自己的算法寫(xiě)錯(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ì)）。

上一周開(kāi)始思考這個(gè)題目，做了幾個(gè)割點(diǎn)和割邊的題目后開(kāi)始做這個(gè)題目：

用了求割邊然后縮點(diǎn)的方法，

結(jié)果為（葉子節(jié)點(diǎn)數(shù)＋1）／2。

開(kāi)始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é)果自己代碼能力挫＋比賽中還有另一題卡

著，沒(méi)有做出來(lái)（這樣是可以的，NUDT的Alpc55就這么過(guò)了，代碼能力牛!)。

  后來(lái)晚上想到二分一個(gè)len，然后把距離大于len的邊全部賦值為0（其實(shí)就是作

Dijstra的時(shí)候判斷），小于的賦值為1，求最短路是否與k的關(guān)系。

  圖模型的轉(zhuǎn)換博大精深……




July_23

POJ2866 樹(shù)形DP

這個(gè)題思路沒(méi)什么好說(shuō)的，關(guān)鍵地方在于看到題目提到幾何坐標(biāo)時(shí)不要怕：這個(gè)題目

我開(kāi)始時(shí)有點(diǎn)怕，不過(guò)看完之后一下就想到思路了——如果開(kāi)始怕幾何那么這個(gè)題目

就會(huì)很晚出了。





July_23

POJ2547 No Tipping


集合DP。

比賽時(shí)候沒(méi)做出來(lái)——當(dāng)時(shí)我們估計(jì)了搜索的時(shí)間復(fù)雜度明顯不行，然后還是寫(xiě)了！


其實(shí)看到數(shù)據(jù)<=20應(yīng)該就要敏感點(diǎn)地知道要集合DP了，想到這里就好辦了。

沒(méi)有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)，然后再以沒(méi)有訪問(wèn)過(guò)的點(diǎn)開(kāi)始

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！可見(jiàn)我

的模型還不夠好……   待改進(jìn).


通過(guò)這個(gè)題的經(jīng)驗(yàn)，又把原來(lái)卡的3013也過(guò)了。

通過(guò)好幾個(gè)題：3013 3159 2169
發(fā)現(xiàn)如果遇到圖論題，還是不要用new malloc的好，數(shù)組模擬指針還是快很多——

雖然沒(méi)那么方便。





July_24

POJ1885
   線段樹(shù)模型

   今天跟alpc在TOJ做比賽的題目，好題一道。

   題目的模型是現(xiàn)椴樹(shù)，讀入單詞為插入節(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ù)蒙騙了，沒(méi)有想到什么好方法，直到

比賽還剩下20多分鐘才想到離散話，加上代碼速度慢了點(diǎn)，沒(méi)有寫(xiě)出來(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

  很好的線段樹(shù)題目——一個(gè)比賽時(shí)留下的怨念：當(dāng)時(shí)大家都沒(méi)想法，我試著敲這

個(gè)題目，結(jié)果TLE了。
 
 這個(gè)題目我的想法是對(duì)的：直接維護(hù)線段樹(shù)（區(qū)間樹(shù)）的查找、刪除、添加操作。
 由于查找的是大于指定長(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í)寫(xiě)對(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ò)了，然后今天就

開(kāi)始寫(xiě)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ǔ)。


這類(lèi)題目都做出套路了：遞歸。
    加深對(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