浙大 acm oj 解題報(bào)告

 搞編程的都知道的浙江大學(xué)ACM題庫(kù)．本書是收集了所有經(jīng)典的ZJU題解集，集合并附有原題目和詳細(xì)的注釋，最終的代碼．
動(dòng)態(tài)規(guī)劃:
暴力DP :ZJU1039 難度:中等偏難
暴力DP :ZJU1227 難度:比較難
經(jīng)典問題 :ZJU1149 難度:如果不會(huì)用剩余類,感覺比較難�？梢钥疾轵_分技巧(就是那種砍到多少多少以下)
經(jīng)典問題 :ZJU1366 難度:同上。但這題用搜索用得好的話可以瞬過(guò)。
狀態(tài)表示 :ZJU2059 難度:中等偏難。這個(gè)題考狀態(tài)表示的
狀態(tài)表示 :ZJU1757 難度:中等偏難。一類NP問題的動(dòng)規(guī)解法。
經(jīng)典問題 :ZJU2096 難度:中等偏難。狗狗的題目。
經(jīng)典問題 :ZJU1717 難度:中等偏易。就是走格子的復(fù)雜一點(diǎn)版
經(jīng)典問題 :ZJU1986 難度:中等。傳說(shuō)中的最長(zhǎng)不XX子序列。聽說(shuō)這個(gè)題不用O(nlogn)的過(guò)不了？我是O(nlogn)的。
非純動(dòng)規(guī) :ZJU1953 難度:中等。傳說(shuō)中的最長(zhǎng)公共子序列。不過(guò)這個(gè)題只是用到這個(gè),后面還要用構(gòu)造法。

數(shù)據(jù)結(jié)構(gòu):
線段樹 :ZJU1128 難度:中等偏難。求面積并,掃描線法+線段樹。以前的國(guó)家隊(duì)論文有過(guò)的題。

線段樹 :ZJU1659 難度:中等偏難。求面積并。
表達(dá)式計(jì)算:ZJU1958 難度:中等
去括號(hào) :ZJU2021 難度:中等

搜索題,BFS/DFS:
BFS :ZJU1063 難度:中等偏易
BFS + DFS :ZJU1085 難度:中等偏易
經(jīng)典的BFS :ZJU1136 難度:中等偏難
分類搜索 :ZJU1732 難度:中等偏難。這個(gè)題目的意思比較難理解
搜索策略 :ZJU1411 難度:中等。搜索策略不對(duì)的話鐵定TLE�？梢杂梦徊僮鲀�(yōu)化。

無(wú)數(shù)人WA :ZJU1101 難度:中等。就是枚舉順序那里死活有人錯(cuò)。
ID-DFS :ZJU1204 難度:中等。我當(dāng)時(shí)做的時(shí)候錯(cuò)得莫名其妙的。
估界+搜索 :ZJU1269 難度:中等。我覺得想不出估界就沒法做。
簡(jiǎn)單搜索題:ZJU1403 難度:簡(jiǎn)單
建圖+搜索 :ZJU1424 難度:中等偏易。金牌之路上面有的。
奇偶+搜索 :ZJU1457 難度:簡(jiǎn)單。不加奇偶性判斷就TLE,加了基本上都能對(duì)。
常規(guī)搜索 :ZJU1639 難度:中等偏易。無(wú)非就是可性行剪枝加最優(yōu)解剪枝
簡(jiǎn)單搜索 :ZJU1861 難度:簡(jiǎn)單
樹的最長(zhǎng)路:ZJU2013 難度:有點(diǎn)難。沒聽說(shuō)過(guò)方法的硬想比較困難。

圖論題:
純最短路徑:太多了,ZJU1082比較好。
純最小生成樹:太多了,ZJU1203一個(gè)就夠了。
EULER路徑 :ZJU1919 難度:中等偏難。
極大極小路徑問題:ZJU1542 難度:中等。
極小極大路徑問題:ZJU1942 難度:中等偏易。
這兩個(gè)題的解法太多了。FLOYD可以,DIJKSTRA可以,最小生成樹可以,二分答案+判定也可以。不錯(cuò)的題目。


貪心思想:
會(huì)議安排 :ZJU1076 難度:簡(jiǎn)單
區(qū)間覆蓋 :ZJU1360 難度:中等
經(jīng)典過(guò)河 :ZJU1877 難度:中等。沒做過(guò)估計(jì)就做不出來(lái)的。
經(jīng)典貪心 :ZJU1756 難度:中等偏易。貪心應(yīng)該是O(N^2),這道題其實(shí)是:用不下降子序列去覆蓋一個(gè)序列,求最少要多少個(gè)不下降子序列。有O(nlogn)的動(dòng)態(tài)規(guī)劃。國(guó)家隊(duì)論文有講。
二分+貪心 :ZJU2002 難度:中等偏難。如果用動(dòng)態(tài)規(guī)劃肯定超時(shí),順便考考二分也不錯(cuò)的。而且這個(gè)搭配經(jīng)常出現(xiàn)。