學(xué)習(xí)算法之路

1、第一階段練經(jīng)典常用算法，下面的每個(gè)算法給我打上十到二十遍，同時(shí)自己精簡(jiǎn)代碼， 因?yàn)樘Ｓ茫砸毜綄憰r(shí)不用想，10-15分鐘內(nèi)打完，甚至關(guān)掉顯示器都可以把程序打出來. 1.最短路(Floyd、Dijstra,BellmanFord) 2.最小生成樹(先寫個(gè)prim,kruscal要用并查集，不好寫) 3.大數(shù)（高精度）加減乘除 4.二分查找. (代碼可在五行以內(nèi)) 5.叉乘、判線段相交、然后寫個(gè)凸包. 6.BFS、DFS,同時(shí)熟練hash表(要熟，要靈活,代碼要簡(jiǎn)) 7.數(shù)學(xué)上的有：輾轉(zhuǎn)相除（兩行內(nèi)），線段交點(diǎn)、

2、多角形面積公式. 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. 熟悉動(dòng)態(tài)規(guī)劃的各個(gè)典型：LCS、最長(zhǎng)遞增子串、三角剖分、記憶化dp 6.博弈類算法。博弈樹，二進(jìn)制法等。 7.最大團(tuán)，最大獨(dú)立集。 8.判斷點(diǎn)在多邊形內(nèi)。 9. 差分約束系統(tǒng). 10. 雙向廣度搜索、A*算法，最小

3、耗散優(yōu)先. 初期: 一.基本算法:     (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,f

4、loyd,heap+dijkstra)         (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)     (3)最小生成樹算法(prim,kruskal)         (poj1789,poj2485,poj1258,poj3026)     (4)拓?fù)渑判?(poj1094) 

5、0;   (5)二分圖的最大匹配 (匈牙利算法) (poj3041,poj3020)     (6)最大流的增廣路算法(KM算法). (poj1459,poj3436) 三.數(shù)據(jù)結(jié)構(gòu).     (1)串 (poj1035,poj3080,poj1936)     (2)排序(快排、歸并排(與逆序數(shù)有關(guān))、堆排) (poj2388,poj2299)     (3)簡(jiǎn)單并查集的應(yīng)用.  &#

6、160;  (4)哈希表和二分查找等高效查找法(數(shù)的Hash,串的Hash)            (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)     (5)哈夫曼樹(poj3253)     (6)堆     (7)trie樹(靜態(tài)建樹、動(dòng)態(tài)建樹) (poj2513) 四.簡(jiǎn)單搜索 

7、;    (1)深度優(yōu)先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)     (2)廣度優(yōu)先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)     (3)簡(jiǎn)單搜索技巧和剪枝(poj2531,poj1416,poj2676,1129) 五.動(dòng)態(tài)規(guī)劃     (1)背包問題. (poj1837,poj1276)    

8、 (2)型如下表的簡(jiǎn)單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 (最長(zhǎng)公共子序列)            (poj3176,poj1080,poj1159)&

9、#160;      3.Ci,j=wi,j+optCi,k-1+Ck,j.(最優(yōu)二分檢索樹問題) 六.數(shù)學(xué)     (1)組合數(shù)學(xué):         1.加法原理和乘法原理.         2.排列組合.         3.遞推關(guān)系. 

10、0;         (POJ3252,poj1850,poj1019,poj1942)     (2)數(shù)論.         1.素?cái)?shù)與整除問題         2.進(jìn)制位.         3.同余模運(yùn)算.  

11、60;        (poj2635, poj3292,poj1845,poj2115)     (3)計(jì)算方法.         1.二分法求解單調(diào)函數(shù)相關(guān)知識(shí).(poj3273,poj3258,poj1905,poj3122) 七.計(jì)算幾何學(xué).     (1)幾何公式.     (2)叉積和點(diǎn)積的運(yùn)用(如線段相交

12、的判定,點(diǎn)到線段的距離等). (poj2031,poj1039)     (3)多邊型的簡(jiǎn)單算法(求面積)和相關(guān)判定(點(diǎn)在多邊型內(nèi),多邊型是否相交)         (poj1408,poj1584)     (4)凸包. (poj2187,poj1113)中級(jí): 一.基本算法:     (1)C+的標(biāo)準(zhǔn)模版庫的應(yīng)用. (poj3096,poj3007)   

13、;  (2)較為復(fù)雜的模擬題的訓(xùn)練(poj3393,poj1472,poj3371,poj1027,poj2706) 二.圖算法:     (1)差分約束系統(tǒng)的建立和求解. (poj1201,poj2983)     (2)最小費(fèi)用最大流(poj2516,poj2516,poj2195)     (3)雙連通分量(poj2942)     (4)強(qiáng)連通分支及其縮點(diǎn).(poj2186)   

14、;  (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.

15、(poj3264,poj3368)     (5)并查集的高級(jí)應(yīng)用. (poj1703,2492)     (6)KMP算法. (poj1961,poj2406) 四.搜索     (1)最優(yōu)化剪枝和可行性剪枝     (2)搜索的技巧和優(yōu)化 (poj3411,poj1724)     (3)記憶化搜索(poj3373,poj1691) 五.動(dòng)態(tài)規(guī)劃  &#

16、160;  (1)較為復(fù)雜的動(dòng)態(tài)規(guī)劃(如動(dòng)態(tài)規(guī)劃解特別的施行商問題等)         (poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)     (2)記錄狀態(tài)的動(dòng)態(tài)規(guī)劃. (POJ3254,poj2411,poj1185)     (3)樹型動(dòng)態(tài)規(guī)劃(poj2057,poj1947,poj2486,poj3140) 六.數(shù)學(xué)  &

17、#160;  (1)組合數(shù)學(xué):         1.容斥原理.         2.抽屜原理.         3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).         4.遞推關(guān)系和母函數(shù).  

18、   (2)數(shù)學(xué).         1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)         2.概率問題. (poj3071,poj3440)         3.GCD、擴(kuò)展的歐幾里德(中國剩余定理) (poj3101)     (3)計(jì)

19、算方法.         1.0/1分?jǐn)?shù)規(guī)劃. (poj2976)         2.三分法求解單峰(單谷)的極值.         3.矩陣法(poj3150,poj3422,poj3070)         4.迭代逼近(poj3301)   

20、  (4)隨機(jī)化算法(poj3318,poj2454)     (5)雜題.         (poj1870,poj3296,poj3286,poj1095) 七.計(jì)算幾何學(xué).         (1)坐標(biāo)離散化.         (2)掃描線算法(例如求矩形的面積和周長(zhǎng)并,常和線段樹或堆一起使用)

21、.             (poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)         (3)多邊形的內(nèi)核(半平面交)(poj3130,poj3335) (4)幾何工具的綜合應(yīng)用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429) 高級(jí): 一.基本算法要求:

22、0;       (1)代碼快速寫成,精簡(jiǎn)但不失風(fēng)格            (poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)       (2)保證正確性和高效性. poj3434 二.圖算法:       (1)度限制最小生成樹和第K最短路. (p

23、oj1639)       (2)最短路,最小生成樹,二分圖,最大流問題的相關(guān)理論(主要是模型建立和求解)         (poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446       (3)最優(yōu)比率生成樹. (poj2728)       (4)最小樹形圖

24、(poj3164)       (5)次小生成樹.       (6)無向圖、有向圖的最小環(huán)    三.數(shù)據(jù)結(jié)構(gòu).        (1)trie圖的建立和應(yīng)用. (poj2778)       (2)LCA和RMQ問題(LCA(最近公共祖先問題) 有離線算法(并查集+dfs) 和 在線算法 

25、0;         (RMQ+dfs).(poj1330)       (3)雙端隊(duì)列和它的應(yīng)用(維護(hù)一個(gè)單調(diào)的隊(duì)列,常常在動(dòng)態(tài)規(guī)劃中起到優(yōu)化狀態(tài)轉(zhuǎn)移的           目的). (poj2823)       (4)左偏樹(可合并堆).    

26、0;   (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ù)存儲(chǔ)狀態(tài)、轉(zhuǎn)化為串用hash表判重、按位壓縮存儲(chǔ)狀態(tài)、雙向廣搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj

27、1482) (3) 深搜的優(yōu)化:盡量用位運(yùn)算、一定要加剪枝、函數(shù)參數(shù)盡可能少、層數(shù)不易過大、可以考慮雙向搜索或者是輪換搜索、IDA*算法. (poj3131,poj2870,poj2286)五.動(dòng)態(tài)規(guī)劃        (1)需要用數(shù)據(jù)結(jié)構(gòu)優(yōu)化的動(dòng)態(tài)規(guī)劃.         (poj2754,poj3378,poj3017)       (2)四邊形不等式理論. 

28、0;     (3)較難的狀態(tài)DP(poj3133) 六.數(shù)學(xué)        (1)組合數(shù)學(xué).         1.MoBius反演(poj2888,poj2154)         2.偏序關(guān)系理論.       (2)博奕論.  

29、60;      1.極大極小過程(poj3317,poj1085)         2.Nim問題. 七.計(jì)算幾何學(xué).        (1)半平面求交(poj3384,poj2540)       (2)可視圖的建立(poj2966)       (3)點(diǎn)集最小圓覆蓋

30、.       (4)對(duì)踵點(diǎn)(poj2079)  八.綜合題.       (poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,p oj2148,poj1263) 相關(guān)的知識(shí) 圖論   路徑問題         0/1邊權(quán)最短路徑     

31、;    BFS         非負(fù)邊權(quán)最短路徑（Dijkstra）             可以用Dijkstra解決問題的特征         負(fù)邊權(quán)最短路徑         Bellman-Ford&#

32、160;            Bellman-Ford的Yen-氏優(yōu)化             差分約束系統(tǒng)         Floyd             廣義路

33、徑問題             傳遞閉包             極小極大距離 / 極大極小距離         Euler Path / Tour           

34、  圈套圈算法             混合圖的 Euler Path / Tour         Hamilton Path / Tour             特殊圖的Hamilton Path / Tour 構(gòu)造    

35、 生成樹問題         最小生成樹         第k小生成樹         最優(yōu)比率生成樹         0/1分?jǐn)?shù)規(guī)劃         度限制生成樹   

36、  連通性問題         強(qiáng)大的DFS算法         無向圖連通性             割點(diǎn)             割邊    &#

37、160;        二連通分支             有向圖連通性             強(qiáng)連通分支             2-SAT  &

38、#160;          最小點(diǎn)基     有向無環(huán)圖         拓?fù)渑判?#160;            有向無環(huán)圖與動(dòng)態(tài)規(guī)劃的關(guān)系     二分圖匹配問題      

39、;   一般圖問題與二分圖問題的轉(zhuǎn)換思路         最大匹配             有向圖的最小路徑覆蓋             0 / 1矩陣的最小覆蓋        

40、完備匹配         最優(yōu)匹配         穩(wěn)定婚姻     網(wǎng)絡(luò)流問題         網(wǎng)絡(luò)流模型的簡(jiǎn)單特征和與線性規(guī)劃的關(guān)系         最大流最小割定理      

41、;   最大流問題             有上下界的最大流問題                 循環(huán)流         最小費(fèi)用最大流 / 最大費(fèi)用最大流     弦圖的性質(zhì)和判

42、定 組合數(shù)學(xué)     解決組合數(shù)學(xué)問題時(shí)常用的思想         逼近         遞推 / 動(dòng)態(tài)規(guī)劃     概率問題         Polya定理 計(jì)算幾何 / 解析幾何     計(jì)算幾何的核心：叉積 / 面

43、積     解析幾何的主力：復(fù)數(shù)     基本形         點(diǎn)         直線，線段         多邊形     凸多邊形 / 凸包       

44、0; 凸包算法的引進(jìn)，卷包裹法     Graham掃描法         水平序的引進(jìn)，共線凸包的補(bǔ)丁     完美凸包算法     相關(guān)判定         兩直線相交         兩線段相交   &#

45、160;     點(diǎn)在任意多邊形內(nèi)的判定         點(diǎn)在凸多邊形內(nèi)的判定     經(jīng)典問題         最小外接圓             近似O(n)的最小外接圓算法     &

46、#160;   點(diǎn)集直徑             旋轉(zhuǎn)卡殼，對(duì)踵點(diǎn)         多邊形的三角剖分 數(shù)學(xué) / 數(shù)論   最大公約數(shù)         Euclid算法        

47、0;    擴(kuò)展的Euclid算法                 同余方程 / 二元一次不定方程                 同余方程組     線性方程組    

48、     高斯消元法             解mod 2域上的線性方程組         整系數(shù)方程組的精確解法     矩陣         行列式的計(jì)算       

49、;      利用矩陣乘法快速計(jì)算遞推關(guān)系     分?jǐn)?shù)         分?jǐn)?shù)樹         連分?jǐn)?shù)逼近     數(shù)論計(jì)算         求N的約數(shù)個(gè)數(shù)      

50、   求phi(N)         求約數(shù)和         快速數(shù)論變換              素?cái)?shù)問題         概率判素算法      

51、60;  概率因子分解 數(shù)據(jù)結(jié)構(gòu)     組織結(jié)構(gòu)         二叉堆         左偏樹         二項(xiàng)樹         勝者樹      &

52、#160;  跳躍表         樣式圖標(biāo)         斜堆         reap     統(tǒng)計(jì)結(jié)構(gòu)         樹狀數(shù)組         虛二叉樹         線段樹             矩形面積并             圓形面積并     關(guān)系結(jié)構(gòu)