第一階段：練經典常用算法，下面的每個算法給我打上十到二十遍，同時自己精簡代碼，因為太常用，所以要練到寫時不用想，10-15分鐘內打完，甚至關掉顯示器都可以把程序打出來.最短路（Floyd、Dijstra,BellmanFord）最小生成樹（先寫個prim,kruscal要用并查集，不好寫）大數（高精度）加減乘除二分查找.（代碼可在五行以內）叉乘、判線段相交、然后寫個凸包.BFS、DFS，同時熟練hash表（要熟，要靈活，代碼要簡）數學上的有：輾轉相除（兩行內），線段交點、多角形面積公式.調用系統(tǒng)的qsort,技巧很多，慢慢掌握.任意進制間的轉換第二階段：練習復雜一點，但也較常用的算法。如：二分圖匹配（匈牙利），最小路徑覆蓋網絡流，最小費用流。線段樹.并查集。熟悉動態(tài)規(guī)劃的各個典型：LCS、最長遞增子串、三角剖分、記憶化dp博弈類算法。博弈樹，二進制法等。最大團，最大獨立集。判斷點在多邊形內。差分約束系統(tǒng).雙向廣度搜索、A*算法，最小耗散優(yōu)先.相關的知識圖論路徑問題0/1邊權最短路徑BFS非負邊權最短路徑(Dijkstra)可以用Dijkstra解決問題的特征負邊權最短路徑Bellman-FordBellman-Ford的Yen-氏優(yōu)化差分約束系統(tǒng)Floyd廣義路徑問題傳遞閉包極小極大距離/極大極小距離EulerPath/Tour圈套圈算法混合圖的EulerPath/TourHamiltonPath/Tour特殊圖的HamiltonPath/Tour構造生成樹問題最小生成樹第k小生成樹最優(yōu)比率生成樹0/1分數規(guī)劃度限制生成樹連通性問題強大的DFS算法無向圖連通性割點割邊二連通分支有向圖連通性強連通分支2-SAT最小點基有向無環(huán)圖拓撲排序有向無環(huán)圖與動態(tài)規(guī)劃的關系二分圖匹配問題一般圖問題與二分圖問題的轉換思路最大匹配有向圖的最小路徑覆蓋0/1矩陣的最小覆蓋完備匹配最優(yōu)匹配穩(wěn)定婚姻網絡流問題網絡流模型的簡單特征和與線性規(guī)劃的關系最大流最小割定理最大流問題有上下界的最大流問題循環(huán)流最小費用最大流/最大費用最大流弦圖的性質和判定組合數學解決組合數學問題時常用的思想逼近遞推/動態(tài)規(guī)劃概率問題Polya定理計算幾何/解析幾何計算幾何的核心：叉積/面積解析幾何的主力：復數基本形點直線，線段多邊形凸多邊形/凸包凸包算法的引進，卷包裹法Graham掃描法水平序的引進，共線凸包的補丁完美凸包算法相關判定兩直線相交兩線段相交點在任意多邊形內的判定點在凸多邊形內的判定經典問題最小外接圓近似O(n)的最小外接圓算法點集直徑旋轉卡殼，對踵點多邊形的三角剖分數學/數論最大公約數Euclid算法擴展的Euclid算法同余方程/二元一次不定方程同余方程組線性方程組高斯消元法解mod2域上的線性方程組整系數方程組的精確解法矩陣行列式的計算利用矩陣乘法快速計算遞推關系分數分數樹連分數逼近數論計算求N的約數個數求phi(N)求約數和快速數論變換素數問題概率判素算法概率因子分解數據結構組織結構二叉堆左偏樹二項樹勝者樹跳躍表樣式圖標斜堆reap統(tǒng)計結構樹狀數組虛二叉樹線段樹矩形面積并圓形面積并關系結構Hash表并查集路徑壓縮思想的應用STL中的數據結構vectordequeset/map

動態(tài)規(guī)劃/記憶化搜索動態(tài)規(guī)劃和記憶化搜索在思考方式上的區(qū)別最長子序列系列問題最長不下降子序列最長公共子序列最長公共不下降子序列一類NP問題的動態(tài)規(guī)劃解法樹型動態(tài)規(guī)劃背包問題動態(tài)規(guī)劃的優(yōu)化四邊形不等式函數的凸凹性狀態(tài)設計規(guī)劃方向線性規(guī)劃常用思想二分最小表示法KMP Trie結構后綴樹/后綴數組 LCA/RMQ有限狀態(tài)自動機理論排序選擇/冒泡 快速排序 堆排序 歸并排序基數排序拓撲排序 排序網絡中級：一.基本算法：C++的標準模版庫的應用.(poj3096,poj3007)較為復雜的模擬題的訓練(poj3393,poj1472,poj3371,poj1027,poj2706)二圖算法：差分約束系統(tǒng)的建立和求解.(poj1201,poj2983)最小費用最大流(poj2516,poj2516,poj2195)雙連通分量(poj2942)強連通分支及其縮點.(poj2186)圖的割邊和割點(poj3352)最小割模型、網絡流規(guī)約(poj3308,)三.數據結構.線段樹.(poj2528,poj2828,poj2777,poj2886,poj2750)靜態(tài)二叉檢索樹.(poj2482,poj2352)樹狀樹組(poj1195,poj3321)RMQ.(poj3264,poj3368)并查集的高級應用.(poj1703,2492)KMP算法.(poj1961,poj2406)搜索最優(yōu)化剪枝和可行性剪枝搜索的技巧和優(yōu)化(poj3411,poj1724)記憶化搜索(poj3373,poj1691)動態(tài)規(guī)劃較為復雜的動態(tài)規(guī)劃(如動態(tài)規(guī)劃解特別的施行商問題等)(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)記錄狀態(tài)的動態(tài)規(guī)劃.(POJ3254,poj2411,poj1185)樹型動態(tài)規(guī)劃(poj2057,poj1947,poj2486,poj3140)六擻學組合數學：容斥原理.抽屜原理.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).遞推關系和母函數.數學.高斯消元法(poj2947,poj1487,poj2065,poj1166,poj1222)概率問題.(poj3071,poj3440)GCD、擴展的歐幾里德(中國剩余定理)(poj3101)計算方法.1.0/1分數規(guī)劃.(poj2976)三分法求解單峰(單谷)的極值.矩陣法(poj3150,poj3422,poj3070)迭代逼近(poj3301)隨機化算法(poj3318,poj2454)雜題.(poj1870,poj3296,poj3286,poj1095)七.計算幾何學.坐標離散化.掃描線算法(例如求矩形的面積和周長并，常和線段樹或堆一起使用).(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)多邊形的內核(半平面交)(poj3130,poj3335)幾何工具的綜合應用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)高級：一.基本算法要求：代碼快速寫成，精簡但不失風格(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)保證正確性和高效性.poj3434二圖算法：度限制最小生成樹和第K最短路.(poj1639)最短路，最小生成樹，二分圖，最大流問題的相關理論(主要是模型建立和求解)(poj3155,poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446最優(yōu)比率生成樹.(poj2728)最小樹形圖(poj3164)次小生成樹.無向圖、有向圖的最小環(huán)三.數據結構.trie圖的建立和應用.(poj2778)LCA和RMQ問題(LCA(最近公共祖先問題)有離線算法(并查集+dfs)和在線算法(RMQ+dfs)).(poj1330)雙端隊列和它的應用(維護一個單調的隊列，常常在動態(tài)規(guī)劃中起到優(yōu)化狀態(tài)轉移的目的).(poj2823)左偏樹(可合并堆).后綴樹(非常有用的數據結構，也是賽區(qū)考題的熱點).(poj3415,poj3294)搜索較麻煩的搜索題目訓練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)廣搜的狀態(tài)優(yōu)化:利用M進制數存儲狀態(tài)、轉化為串用hash表判重、按位壓縮存儲狀態(tài)、雙向廣搜、A*算法.(poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)深搜的優(yōu)化:盡量用位運算、一定要加剪枝、函數參數盡可能少、層數不易過大、可以考慮雙向搜索或者是輪換搜索、IDA*算法.(poj3131,poj2870,poj2286)動態(tài)規(guī)劃需要用數據結構優(yōu)化的動態(tài)規(guī)劃.(poj2754,poj3378,poj3017)四邊形不等式理論.較難的狀態(tài)DP(poj3133)六擻學組合數學.MoBius反演(poj2888,poj2154)偏序關系理論.博奕論.極大極小過程(poj3317,poj1085)Nim問題.七.計算幾何學.半平面求交(poj3384,poj2540)可視圖的建立(poj2966)點集最小圓覆蓋.對踵點(poj2079)八.綜合題.(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)初期：一.基本算法：(1)枚舉.(poj1753,poj2965)(2)貪心(poj1328,poj2109,poj2586)(3)遞歸和分治法. (4)遞推.構造法.(poj3295) (6)模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)二圖算法：圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷.最短路徑算法(dijkstra,bellman-ford,floyd,heap+dijkstra)(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)最小生成樹算法(prim,kruskal)(poj1789,poj2485,poj1258,poj3026)拓撲排序(poj1094)二分圖的最大匹配(匈牙利算法)(poj3041,poj3020)最大流的增廣路算法(KM算法).(poj1459,poj3436)三.數據結構.串(poj1035,poj3080,poj1936)排序(快排、歸并排(與逆序數有關)、堆排)(poj2388,poj2299)簡單并查集的應用.哈希表和二分查找等高效查找法(數的Hash，串的Hash)(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)哈夫曼樹(poj3253)堆trie樹(靜態(tài)建樹、動態(tài)建樹)(poj2513)四.簡單搜索深度優(yōu)先搜索(poj2488,poj3083,poj3009,poj1321,poj2251)廣度優(yōu)先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)簡單搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)五.動態(tài)規(guī)劃背包問題.(poj1837,poj1276)型如下表的簡單DP(可參考lrj的書page149):E[j]=opt{D+w(i,j)}(poj3267,poj1836,poj1260,poj2533)E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij}(最長公共子序列)(poj3176,poj1080,poj1159)C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優(yōu)二分檢索樹問題)六擻學組合數學：加法原理和乘法原理.排列組合.遞推關系.(POJ3252,poj1850,poj101