轉(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


  對于一棵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ì)競賽》上有比較清楚解法，我看懂后照著敲了一個(gè)，結(jié)果花了一個(gè)下午才寫出來，整整300＋行（我寫代碼向來冗余,待整理），好在做出來了。

  我的解法思路（大致照lrj的解法）：
 1 先Prim+heap求最小生成樹塊；
 2 然后添加0到各連通塊的最小邊；
 3 然后通過h(t)求h(t+1)——關(guān)鍵部分：
    枚舉2中未選的0的鄰邊，然后在形成的環(huán)中找最大邊刪除（這里跟lrj的不一樣，我作了一遍dfs找最大邊，最后刪邊也用dfs實(shí)現(xiàn))。
   終止條件為0的度數(shù)到達(dá)k或上邊的情況不能使生成樹總長減小。


  這套方法太麻煩，由于題目數(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)號點(diǎn)，二是求出來的回路序列要是最小（每條路徑有一個(gè)標(biāo)號）。
  原來在USACO寫過一個(gè)求歐拉回路要求訪問點(diǎn)序列最小的的歐拉路，當(dāng)時(shí)用矩陣實(shí)現(xiàn)，這樣歐拉路／歐拉回路基本會寫了——不過如果要非遞歸實(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的題目。

   原來的時(shí)候把狀態(tài)壓縮DP想得很高深，一直不敢動，今天下定決心通過以前看過的一些思想的總結(jié)來寫這一類題目，寫完這個(gè)題后初步感覺狀態(tài)壓縮DP的主要特點(diǎn)就是狀態(tài)壓縮（廢話！但理解這句話用了這么幾個(gè)月）：除了對狀態(tà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ù)組把一行的合法布局記錄下來，這樣100列也就60種狀態(tài)，記錄兩行狀態(tài)數(shù)不過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。
 
  求最長最長漢密爾頓路（非回路）。由于昨天開始做了幾個(gè)狀態(tài)壓縮的題目后，對這類題有點(diǎn)理解，加上這個(gè)題目基本上是赤裸裸的狀態(tài)轉(zhuǎn)移，很快寫過。
  Wa了一次：由于開始求的是最長公共子序列長度（其實(shí)是最大對應(yīng)相同的字母數(shù)）。


July_14

POJ 3164 Command Network


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

  寫了一個(gè)下午，原因是頭腦不清晰，代碼風(fēng)格也不好，寫來寫去開始一直TLE，后來找了hdu的一個(gè)人的標(biāo)程，發(fā)覺自己的思路沒錯，基本一樣……
 查了好久，發(fā)現(xiàn)在找環(huán)后標(biāo)記時(shí)標(biāo)記了縮點(diǎn)為已經(jīng)從圖中去除！

  改了后WA，錯誤在于縮點(diǎn)時(shí)入邊出邊不分——對于入邊要減去dis[ pre[u] ][u]!

  還有網(wǎng)上推薦的uva11185也過了
http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&page=show_problem&problem=2124


  總結(jié)下做法：網(wǎng)上大家貼的算法都很清晰，有個(gè)圖更是明了，不過代碼還是長了點(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


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

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

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


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

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

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

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


POJ1204 Word Puzzles

  這個(gè)題目其實(shí)還是個(gè)簡單題——直接寫個(gè)Trie就好了。不過我還是RE了不少次數(shù)：原因是忘記初始化指針指向NULL了！！！！弱智啊～～
 
 
  不過做了這個(gè)題目我在POJ上的little id-->R2D2的題數(shù)就與littlekid這個(gè)帳號一樣了。將兩個(gè)號一合計(jì)：在POJ上也算AC了有283題了，＋U，fighting！




July_16

POJ1037

動態(tài)規(guī)劃＋遞推。

  這個(gè)題目去年第一次看到就推出了那個(gè)算n個(gè)柵欄以第i短的為第一根下一根放短的or長的柵欄的方案數(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和類型（短/長）。

 維護(hù)一個(gè)集合為未選柵欄
 中間的遞推比較麻煩：若類型為短，從1減、否則從上次得到的i向上減。（－f[t_len{后邊長度}][i][type])。
 找到位置i后輸出第i小的數(shù)。

 總之這個(gè)題目很考遞推能力——推了幾個(gè)小時(shí)還是錯了一點(diǎn)，最后discuss里那個(gè)人的程序遞歸實(shí)現(xiàn)的還是幫了大忙！

 這個(gè)題目思想很好，以后要回來溫習(xí)。


July_16

POJ 1077 Eight

經(jīng)典搜索題。

這個(gè)題目可以用一般BFS，A＊，雙向BFS……等方法做。

原來寫過BFS版本，今天寫了個(gè)雙向BFS——畢竟聽說過這個(gè)名詞以來還沒寫過。

其實(shí)雙向BFS真的很簡單：就是BFS的時(shí)候同時(shí)從目標(biāo)和初始狀態(tài)做BFS，關(guān)鍵的地方在于判斷當(dāng)前搜索出來的狀態(tài)是否在另外一棵搜索樹中出現(xiàn)（這里借用 Hash判斷，對每個(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)大……

不過很費(fèi)空間（本人不幸0ms用空間最多），下次學(xué)了A＊再做。



July_17

July_1195

POJ1195 Mobile phones

source IOI2001

  經(jīng)典二維樹狀數(shù)組題。

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

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

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

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

Borg Maze

最小生成樹。

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

犯了一個(gè)弱智錯誤：數(shù)組開小了，不過由于G＋＋不報(bào)錯，得到詭異的錯誤……

讓我想起寒假時(shí)候HDU給我不報(bào)RE報(bào)TLE的事情了。









June_5
POJ1011／WOJ1212 Sticks

經(jīng)典搜索題。
這個(gè)題目做了很久——去年暑假個(gè)人賽模擬賽第一次接觸，當(dāng)時(shí)沒做出來，不過后來模仿別人程序把POJ1011過了，不過WOJ1212卻是TLE。

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

大體框架為DFS，最重要的是減枝。
下面是我的一些減枝：
1、要得到的Sticks長度必定為總長度的約數(shù)——這個(gè)好想；
2、對blocks按長度由小到大排序（原來也排了，當(dāng)時(shí)不知道為什么要排——為了減枝）；
3、搜索順序?yàn)椋?br>用blocks去組成sticks，
減枝一：按照組成sticks的最長block排序（由大到小），這個(gè)可以證明的，而且剩下的blocks中最長block一定要選擇；
減枝二：組成每根sticks時(shí)按從大到小枚舉，如果可行則當(dāng)前方案一定是最后方案(理解這個(gè)我用了比較久，其實(shí)就是如果有另外的另兩根短的blocks可替換的方案存在，那么長blocks放在后面也是對的，如果固定在前面，可減少不少）;
減枝三：對于長度相同的blocks，如果當(dāng)前用其中一根組成當(dāng)前sticks不能得到結(jié)果，那么當(dāng)前的選擇要跳過所有的這些blocks（這個(gè)從搜索樹上理解就好了——畫出一棵搜索樹，會發(fā)現(xiàn)這些blocks為根的子樹完全相同）；

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

trick：由于woj1212只卡時(shí)間，我用了一個(gè)錯誤的減枝（很弱智，也就不說了）得到了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）的最短奇偶路徑相似。

方法很簡單：
對每個(gè)點(diǎn)保存兩個(gè)值，做兩遍最短路：
第一次普通最長路，
第二遍做最短路時(shí)，對所有邊枚舉其縮到一半的情況，具體就是：
Dist[p->v][1] = min(Dist[i][0]+p->len/2.0, Dist[i][1]+p->len)

別的沒什么好說的，這個(gè)題目是簡單題。








June_9

Cashier Employment

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

  差分約束問題。
  這種題目難的地方就是建圖，這個(gè)題目特殊的地方是得到最后的不等式中第23小時(shí)不好處理，那么就枚舉啦（數(shù)據(jù)范圍不大，二分也是可以的）。
  不過有個(gè)地方還沒懂——我建圖后枚舉用bellman—ford后如果滿足約束就返回true錯了，改為馮威的論文上的!=4的約束條件就AC了——有什么trick？
 
  總結(jié)一下差分約束問題：先對題目建立模型，然后抽出不等式，再整理成差分約束標(biāo)準(zhǔn)形，最后bellman－ford檢查約束條件。  差分約束簡單類題目就這么搞了，難的變化大，目前搞不定，需要多見識積累經(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)下，通過執(zhí)行這一命令序列后都到達(dá)狀態(tài)0。

 今天狀態(tài)不好（畢竟近20天沒寫題了），看到這個(gè)題目后沒有想法，oldmaner也認(rèn)為只能窮舉，然后我寫了上去居然WA了（沒有TLE），就在考慮是否漏了情況，未果。
 后來改模型，居然推出一個(gè)狀態(tài)DP的模型，還好很快由此想到了圖論——這個(gè)題目是個(gè)簡單題。


  解法：由于n很小，所以可以對在執(zhí)行了一系列命令后的狀態(tài)用一個(gè)頂點(diǎn)表示（就是一個(gè)2進(jìn)制數(shù)標(biāo)號，對應(yīng)位為1表示當(dāng)前的狀態(tài)——開始時(shí)處于1111狀態(tài)，最后處于0111狀態(tài)）。
  后面就很簡單的建圖：如果從某一狀態(tài)u可以通過命令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è)題目做了比較長的時(shí)間，
為了它先學(xué)習(xí)了一下無向圖的橋，不過沒有過～～這個(gè)題目不一樣的地方是有些點(diǎn)之間不只一條邊；
今天想到hash判重（這么簡單的思想原來怎么就沒想到呢？）
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

簡單題，直接模擬做

比賽當(dāng)時(shí)wa了，第二天繼續(xù)做，開始TLE，后來優(yōu)化了一下就過了：
對于"/*"找其配對的"*/"，如果沒找到以后就不用再找了。


教訓(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，后來學(xué)了加堆優(yōu)化的Dijstra還是沒有過，都把堆的各種操作優(yōu)化了，位運(yùn)算也上了，交了好多次。
昨天上數(shù)據(jù)結(jié)構(gòu)的時(shí)候看到用數(shù)組模擬指針，突然想到會不會是用new或malloc太慢，用靜態(tài)指針？今天寫了個(gè)數(shù)組模擬指針，果然過了，1032ms，還是有點(diǎn)慢——那些100＋ms的是怎么弄的，下次請教下～～
May_29

POJ1144

這個(gè)題目就是求無向圖的關(guān)節(jié)點(diǎn)（或割點(diǎn)），前幾天就寫好了算法，不過WA了，然后這幾天就一直懷疑
自己的算法寫錯了，不斷找bug，不過找不到～

后來看到Discuss里的數(shù)據(jù)果然過不了，——

今天上網(wǎng)查了別人的算法，人家非常暴力的算法都過了……不過最后終于發(fā)現(xiàn)自己的錯誤——讀入處理錯了，看錯題了，又一次死在讀入處理上——不過這次不是不會處理，而是看錯題了
（第一個(gè)數(shù)代表后面數(shù)相連頂點(diǎn)，我弱智地處理了，具體就不說了）


下次不能犯這么弱智的錯誤








May_31

POJ3352 Road Construction

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

這個(gè)題目第一次看到是在去年暑假組隊(duì)賽——當(dāng)時(shí)一直想著怎么DFS硬搞（當(dāng)時(shí)除了硬搞什么都不會）。

上一周開始思考這個(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è)題加深了我對于模擬題的理解。

關(guān)鍵在于讀懂題意，思路清晰。

這個(gè)題目的關(guān)鍵在于理解題，然后計(jì)算移動：先計(jì)算每個(gè)圖形的最左最右位置，再把

每一格把所有的圖形按規(guī)則計(jì)算向左移動的格數(shù)，然后再根據(jù)移動的最左坐標(biāo)建立新

圖像，最后根據(jù)規(guī)則去掉不輸出的前導(dǎo)后續(xù)空白輸出,一直在做算術(shù)。







July_22

POJ3662

  這個(gè)題目很好。

  題目意思是對于一個(gè)圖求一條從源點(diǎn)到終點(diǎn)的路徑滿足：第k＋1長的邊最短。

  當(dāng)時(shí)想了半天也只想到優(yōu)先隊(duì)列廣搜，結(jié)果自己代碼能力挫＋比賽中還有另一題卡

著，沒有做出來（這樣是可以的，NUDT的Alpc55就這么過了，代碼能力牛!)。

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

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

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




July_23

POJ2866 樹形DP

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

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

就會很晚出了。





July_23

POJ2547 No Tipping


集合DP。

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


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

沒有trick的題目：不過對數(shù)據(jù)的敏感和集合DP的思想意識要加強(qiáng)。








July_23

POJ1103 Maze
 
     在TOJ跟ALPC做比賽的題目，當(dāng)時(shí)想出來的——這個(gè)題目關(guān)鍵在于建圖，而建

圖的關(guān)鍵在于標(biāo)號：按照題意劃分區(qū)域，‘／’和‘\'分別代表不同的涉及的四個(gè)區(qū)

域的不同連接關(guān)系。

   最后可以證明除了邊界區(qū)域，一個(gè)區(qū)域與正好兩個(gè)區(qū)域相連通，故建圖后先從邊

界區(qū)域出發(fā)dfs將所有能到達(dá)的區(qū)域標(biāo)記出為訪問，然后再以沒有訪問過的點(diǎn)開始

dfs走圈計(jì)數(shù)。

  還不錯的一道題。








July_23

POJ2169
圖模型轉(zhuǎn)換＋最短路

題目的模型轉(zhuǎn)化思想很經(jīng)典：原來給的就是一個(gè)圖，但是要選擇兩個(gè)相鄰（有邊直接

相連）的頂點(diǎn)——一個(gè)狀態(tài)，從一個(gè)狀態(tài)可以依照條件通過一定步數(shù)轉(zhuǎn)移到另一個(gè)合

法狀態(tài)，
求從一個(gè)初始狀態(tài)到終結(jié)狀態(tài)的最少步數(shù)。

轉(zhuǎn)化思想：建立一個(gè)新圖，將原圖的一條邊轉(zhuǎn)化為新圖中的一個(gè)頂點(diǎn)，對于原圖中每

個(gè)合法的轉(zhuǎn)移建立一條有向邊，然后在新圖中求s－t最短路。

trick：這個(gè)題比賽時(shí)我們雖然想到解法，但代碼能力問題加卡其他題，并未做出此

題。
          賽后在TOJ將它AC后到POJ提交發(fā)現(xiàn)TLE，然后在ZOJ發(fā)現(xiàn)MLE。
    后來發(fā)現(xiàn)我用了new，POJ又把卡new了，然后改成數(shù)組就過了。
    至于ZOJ，目前還是MLE，我用了40000K左右內(nèi)存，它自由32767k！可見我

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


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

通過好幾個(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ù)制過來到最后一個(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)，沒有寫出來。


對題意的挖掘最重要的一點(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è)題目我的想法是對的：直接維護(hù)線段樹（區(qū)間樹）的查找、刪除、添加操作。
 由于查找的是大于指定長度k的最左空白的連續(xù)區(qū)間，故節(jié)點(diǎn)有l(wèi)max,rmax,cmax三

個(gè)值，還有必要的區(qū)間長度、范圍的信息（這個(gè)一個(gè)可以推另一個(gè)）。

 TLE的原因很弱智：對于一個(gè)區(qū)間整體的覆蓋或刪除不必先下到子區(qū)間，等要改變

子區(qū)間時(shí)才將區(qū)間信息往下傳；合并子區(qū)間也是麻煩的（不過當(dāng)時(shí)寫對了），細(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給過了，然后今天就

開始寫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)在于對表達(dá)式求值

由于一定不高于一階，可以用復(fù)數(shù)的表示方法存儲。


這類題目都做出套路了：遞歸。
    加深對“編譯原理”的理解。



July_30

POJ2677 Tour

經(jīng)典DP CLRS上的題目 模擬兩個(gè)人走來解

狀態(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