1、Good is good, but better carries it.精益求精，善益求善。ACM大量習題題庫及建議培養計劃/別人總結的，確實很多，但有信心就能學完！一.基本算法:(1)枚舉.(poj1753,poj2965)(2)貪心.(poj1328,poj2109,poj2586)(3)遞歸和分治法.(4)遞推.(5)構造法.(poj3295)(6)模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)二.圖算法:(1)圖的深度優先遍歷和廣度優先遍歷.(2)最短路徑算法.(dijkstra,bellman-ford,floyd,heap+dijkstr

2、a)(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)(3)最小生成樹算法.(prim,kruskal)(poj1789,poj2485,poj1258,poj3026)(4)拓撲排序.(poj1094)(5)二分圖的最大匹配(匈牙利算法).(poj3041,poj3020)(6)最大流的增廣路算法(KM算法).(poj1459,poj3436)三.數據結構.(1)串.(poj1035,poj3080,poj1936)(2)排序(快排、歸并排(與逆序數有關)、堆排).(poj2388,poj2299)(3)簡單并查集的應用.(4)哈希表和二分查找

3、等高效查找法.(數的Hash,串的Hash)(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)(5)哈夫曼樹.(poj3253)(6)堆.(7)trie樹(靜態建樹、動態建樹).(poj2513)四.簡單搜索(1)深度優先搜索.(poj2488,poj3083,poj3009,poj1321,poj2251)(2)廣度優先搜索.(poj3278,poj1426,poj3126,poj3087.poj3414)(3)簡單搜索技巧和剪枝.(poj2531,poj1416,poj2676,1129)五.動態規劃(1)背包問題.(poj1837,poj1

4、276)(2)型如下表的簡單DP(可參考lrj的書page149):1.Ej=optD+w(i,j)(poj3267,poj1836,poj1260,poj2533)2.Ei,j=optDi-1,j+xi,Di,j-1+yj,Di-1j-1+zij(最長公共子序列)(poj3176,poj1080,poj1159)3.Ci,j=wi,j+optCi,k-1+Ck,j.(最優二分檢索樹問題)六.數學(1)組合數學:1.加法原理和乘法原理.2.排列組合.3.遞推關系.(POJ3252,poj1850,poj1019,poj1942)(2)數論.1.素數與整除問題2.進制位.3.同余模運算.(poj

5、2635,poj3292,poj1845,poj2115)(3)計算方法.1.二分法求解單調函數相關知識.(poj3273,poj3258,poj1905,poj3122)七.計算幾何學.(1)幾何公式.(2)叉積和點積的運用(如線段相交的判定,點到線段的距離等).(poj2031,poj1039)(3)多邊型的簡單算法(求面積)和相關判定(點在多邊型內,多邊型是否相交)(poj1408,poj1584)(4)凸包.(poj2187,poj1113)中級:一.基本算法:(1)C+的標準模版庫的應用.(poj3096,poj3007)(2)較為復雜的模擬題的訓練.(poj3393,poj1472

6、,poj3371,poj1027,poj2706)二.圖算法:(1)差分約束系統的建立和求解.(poj1201,poj2983)(2)最小費用最大流.(poj2516,poj2516,poj2195)(3)雙連通分量.(poj2942)(4)強連通分支及其縮點.(poj2186)(5)圖的割邊和割點.(poj3352)(6)最小割模型、網絡流規約.(poj3308)三.數據結構.(1)線段樹.(poj2528,poj2828,poj2777,poj2886,poj2750)(2)靜態二叉檢索樹.(poj2482,poj2352)(3)樹狀樹組.(poj1195,poj3321)(4)RMQ.(

7、poj3264,poj3368)(5)并查集的高級應用.(poj1703,2492)(6)KMP算法.(poj1961,poj2406)四.搜索(1)最優化剪枝和可行性剪枝.(2)搜索的技巧和優化.(poj3411,poj1724)(3)記憶化搜索.(poj3373,poj1691)五.動態規劃(1)較為復雜的動態規劃(如動態規劃解特別的施行商問題等).(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)(2)記錄狀態的動態規劃.(POJ3254,poj2411,poj1185)(3)樹型動態規劃.(poj2057,poj1947,

8、poj2486,poj3140)六.數學(1)組合數學:1.容斥原理.2.抽屜原理.3.置換群與Polya定理.(poj1286,poj2409,poj3270,poj1026)4.遞推關系和母函數.(2)數學.1.高斯消元法.(poj2947,poj1487,poj2065,poj1166,poj1222)2.概率問題.(poj3071,poj3440)3.GCD、擴展的歐幾里德(中國剩余定理)(poj3101)(3)計算方法.1.0/1分數規劃.(poj2976)2.三分法求解單峰(單谷)的極值.3.矩陣法.(poj3150,poj3422,poj3070)4.迭代逼近.(poj3301)

9、(4)隨機化算法.(poj3318,poj2454)(5)雜題.(poj1870,poj3296,poj3286,poj1095)七.計算幾何學.(1)坐標離散化.(2)掃描線算法.(例如求矩形的面積和周長并,常和線段樹或堆一起使用)(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)(3)多邊形的內核(半平面交).(poj3130,poj3335)(4)幾何工具的綜合應用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)高級:一.基本算法要求:(1)代碼快速寫成,精簡但不失風格.(poj2525,

10、poj1684,poj1421,poj1048,poj2050,poj3306)(2)保證正確性和高效性.poj3434二.圖算法:(1)度限制最小生成樹和第K最短路.(poj1639)(2)最短路,最小生成樹,二分圖,最大流問題的相關理論(主要是模型建立和求解).(poj3155,poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446(3)最優比率生成樹.(poj2728)(4)最小樹形圖.(poj3164)(5)次小生成樹.(6)無向圖、有向圖的最小環三.數據結構.(1)trie圖的建立和應用.(poj2778)(2)LCA和RMQ問

11、題(LCA(最近公共祖先問題).有離線算法(并查集+dfs)和在線算法(RMQ+dfs).(poj1330)(3)雙端隊列和它的應用(維護一個單調的隊列,常常在動態規劃中起到優化狀態轉移的目的).(poj2823)(4)左偏樹.(可合并堆).(5)后綴樹.(非常有用的數據結構,也是賽區考題的熱點).(poj3415,poj3294)四.搜索(1)較麻煩的搜索題目訓練.(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)(2)廣搜的狀態優化:利用M進制數存儲狀態、轉化為串用hash表判重、按位壓縮存儲狀態、雙向廣搜、A*算法.(poj1768,poj

12、1184,poj1872,poj1324,poj2046,poj1482)(3)深搜的優化:盡量用位運算、一定要加剪枝、函數參數盡可能少、層數不易過大、可以考慮雙向搜索或者是輪換搜索、IDA*算法.(poj3131,poj2870,poj2286)五.動態規劃(1)需要用數據結構優化的動態規劃.(poj2754,poj3378,poj3017)(2)四邊形不等式理論.(3)較難的狀態DP(poj3133)六.數學(1)組合數學.1.MoBius反演.(poj2888,poj2154)2.偏序關系理論.(2)博奕論.1.極大極小過程.(poj3317,poj1085)2.Nim問題.七.計算幾何

13、學.(1)半平面求交.(poj3384,poj2540)(2)可視圖的建立.(poj2966)(3)點集最小圓覆蓋.(4)對踵點.(poj2079)八.綜合題.(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)Dp狀態設計與方程總結1.不完全狀態記錄青蛙過河問題利用區間dp2.背包類問題0-1背包，經典問題無限背包，經典問題判定性背包問題帶附屬關系的背包問題+-1背包問題雙背包求最優值構造三角形問題帶上下界限制的背包問題(012背包)3.線性的動態規劃問題積木游戲問題決斗（判定性問題）圓的最大多邊形

14、問題統計單詞個數問題棋盤分割日程安排問題最小逼近問題(求出兩數之比最接近某數/兩數之和等于某數等等)方塊消除游戲(某區間可以連續消去求最大效益)資源分配問題數字三角形問題漂亮的打印郵局問題與構造答案最高積木問題兩段連續和最大2次冪和問題N個數的最大M段子段和交叉最大數問題4.判定性問題的dp(如判定整除、判定可達性等)模K問題的dp特殊的模K問題，求最大(最小)模K的數變換數問題5.單調性優化的動態規劃1-SUM問題2-SUM問題序列劃分問題(單調隊列優化)6.剖分問題(多邊形剖分/石子合并/圓的剖分/乘積最大)凸多邊形的三角剖分問題乘積最大問題多邊形游戲(多邊形邊上是操作符,頂點有權值)石子

15、合并(N3/N2/NLogN各種優化)7.貪心的動態規劃最優裝載問題部分背包問題乘船問題貪心策略雙機調度問題Johnson算法8.狀態dp牛仔射擊問題(博弈類)哈密頓路徑的狀態dp兩支點天平平衡問題一個有向圖的最接近二部圖9.樹型dp完美服務器問題(每個節點有3種狀態)小胖守皇宮問題網絡收費問題樹中漫游問題樹上的博弈樹的最大獨立集問題樹的最大平衡值問題構造樹的最小環第一階段：練經典常用算法，下面的每個算法給我打上十到二十遍，同時自己精簡代碼，因為太常用，所以要練到寫時不用想，10-15分鐘內打完，甚至關掉顯示器都可以把程序打出來.1.最短路(Floyd、Dijstra,BellmanFord)

16、2.最小生成樹(先寫個prim,kruscal要用并查集，不好寫)3.大數（高精度）加減乘除4.二分查找.(代碼可在五行以內)5.叉乘、判線段相交、然后寫個凸包.6.BFS、DFS,同時熟練hash表(要熟，要靈活,代碼要簡)7.數學上的有：輾轉相除（兩行內），線段交點、多角形面積公式.8.調用系統的qsort,技巧很多，慢慢掌握.9.任意進制間的轉換第二階段：練習復雜一點，但也較常用的算法。如：1.二分圖匹配（匈牙利），最小路徑覆蓋2.網絡流，最小費用流。3.線段樹.4.并查集。5.熟悉動態規劃的各個典型：LCS、最長遞增子串、三角剖分、記憶化dp6.博弈類算法。博弈樹，二進制法等。7.最大

17、團，最大獨立集。8.判斷點在多邊形內。9.差分約束系統.10.雙向廣度搜索、A*算法，最小耗散優先.相關的知識圖論路徑問題0/1邊權最短路徑BFS非負邊權最短路徑（Dijkstra）可以用Dijkstra解決問題的特征負邊權最短路徑Bellman-FordBellman-Ford的Yen-氏優化差分約束系統Floyd廣義路徑問題傳遞閉包極小極大距離/極大極小距離EulerPath/Tour圈套圈算法混合圖的EulerPath/TourHamiltonPath/Tour特殊圖的HamiltonPath/Tour構造生成樹問題最小生成樹第k小生成樹最優比率生成樹0/1分數規劃度限制生成樹連通性問題

18、強大的DFS算法無向圖連通性割點割邊二連通分支有向圖連通性強連通分支2-SAT最小點基有向無環圖拓撲排序有向無環圖與動態規劃的關系二分圖匹配問題一般圖問題與二分圖問題的轉換思路最大匹配有向圖的最小路徑覆蓋0/1矩陣的最小覆蓋完備匹配最優匹配穩定婚姻網絡流問題網絡流模型的簡單特征和與線性規劃的關系最大流最小割定理最大流問題有上下界的最大流問題循環流最小費用最大流/最大費用最大流弦圖的性質和判定組合數學解決組合數學問題時常用的思想逼近遞推/動態規劃概率問題Polya定理計算幾何/解析幾何計算幾何的核心：叉積/面積解析幾何的主力：復數基本形點直線，線段多邊形凸多邊形/凸包凸包算法的引進，卷包裹法Graham掃描法水平序的引進，共線凸包的補丁完美凸包算法相關判定兩直線相交兩線段相交點在任意多邊形內的判定點在凸多邊形內的判定經典問題最小外接圓近似O(n)的最小外接圓算法點集直徑旋轉卡殼，對踵點多邊形的三角剖分數學/數論最大公約數Euclid算法擴展的Euclid算法同余方程/二元一次不定方程同余方程組線性方程組高斯消元法解mod2域上的線性方程組整系數方程組的精確解法矩陣行列式的計算利用矩陣乘法快速計算遞推關系分數分數樹連分數逼近數論計算求N的約數個數求phi(N)求約數和快速數論變換素數問題概率判素算法概率因子分解