ACM大量習(xí)題題庫及建議培養(yǎng)計劃教學(xué)文案

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

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

3、等高效查找法.(數(shù)的Hash,串的Hash)(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)(5)哈夫曼樹.(poj3253)(6)堆.(7)trie樹(靜態(tài)建樹、動態(tài)建樹).(poj2513)四.簡單搜索(1)深度優(yōu)先搜索.(poj2488,poj3083,poj3009,poj1321,poj2251)(2)廣度優(yōu)先搜索.(poj3278,poj1426,poj3126,poj3087.poj3414)(3)簡單搜索技巧和剪枝.(poj2531,poj1416,poj2676,1129)五.動態(tài)規(guī)劃(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.(最優(yōu)二分檢索樹問題)六.數(shù)學(xué)(1)組合數(shù)學(xué):1.加法原理和乘法原理.2.排列組合.3.遞推關(guān)系.(POJ3252,poj1850,poj1019,poj1942)(2)數(shù)論.1.素數(shù)與整除問題2.進(jìn)制位.3.同余模運(yùn)算.(poj

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

6、,poj3371,poj1027,poj2706)二.圖算法:(1)差分約束系統(tǒng)的建立和求解.(poj1201,poj2983)(2)最小費(fèi)用最大流.(poj2516,poj2516,poj2195)(3)雙連通分量.(poj2942)(4)強(qiáng)連通分支及其縮點(diǎn).(poj2186)(5)圖的割邊和割點(diǎn).(poj3352)(6)最小割模型、網(wǎng)絡(luò)流規(guī)約.(poj3308)三.數(shù)據(jù)結(jié)構(gòu).(1)線段樹.(poj2528,poj2828,poj2777,poj2886,poj2750)(2)靜態(tài)二叉檢索樹.(poj2482,poj2352)(3)樹狀樹組.(poj1195,poj3321)(4)RMQ.(

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

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

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

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

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

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

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

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

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

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

17、團(tuán)，最大獨(dú)立集。8.判斷點(diǎn)在多邊形內(nèi)。9.差分約束系統(tǒng).10.雙向廣度搜索、A*算法，最小耗散優(yōu)先.相關(guān)的知識圖論路徑問題0/1邊權(quán)最短路徑BFS非負(fù)邊權(quán)最短路徑（Dijkstra）可以用Dijkstra解決問題的特征負(fù)邊權(quán)最短路徑Bellman-FordBellman-Ford的Yen-氏優(yōu)化差分約束系統(tǒng)Floyd廣義路徑問題傳遞閉包極小極大距離/極大極小距離EulerPath/Tour圈套圈算法混合圖的EulerPath/TourHamiltonPath/Tour特殊圖的HamiltonPath/Tour構(gòu)造生成樹問題最小生成樹第k小生成樹最優(yōu)比率生成樹0/1分?jǐn)?shù)規(guī)劃度限制生成樹連通性問題

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