浙大 acm oj 解題報告

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

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

線段樹 :ZJU1659 難度:中等偏難。求面積并。
表達式計算:ZJU1958 難度:中等
去括號 :ZJU2021 難度:中等

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

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

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


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