POJ題目分類推薦 （很好很有層次感）

著名題單，最初來源不詳。直接來源：http://blog.csdn.net/a1dark/article/details/11714009

OJ上的一些水題(可用來練手和增加自信) (POJ 3299,POJ 2159,POJ 2739,POJ 1083,POJ 2262,POJ 1503,POJ 3006,POJ 2255,POJ 3094)

初期:

一.基本算法:

1. 枚舉. (POJ 1753,POJ 2965)
2. 貪心(POJ 1328,POJ 2109,POJ 2586)
3. 遞歸和分治法.
4. 遞推.
5. 構造法.(POJ 3295)
6. 模拟法.(POJ 1068,POJ 2632,POJ 1573,POJ 2993,POJ 2996)

二.圖算法:

1. 圖的深度優先周遊和廣度優先周遊.
2. 最短路徑算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (POJ 1860,POJ 3259,POJ 1062,POJ 2253,POJ 1125,POJ 2240)
3. 最小生成樹算法(prim,kruskal) (POJ 1789,POJ 2485,POJ 1258,POJ 3026)
4. 拓撲排序 (POJ 1094)
5. 二分圖的最大比對 (匈牙利算法) (POJ 3041,POJ 3020)
6. 最大流的增廣路算法(KM算法). (POJ 1459,POJ 3436)

三.資料結構.

1. 串 (POJ 1035,POJ 3080,POJ 1936)
2. 排序(快排、歸并排(與逆序數有關)、堆排) (POJ 2388,POJ 2299)
3. 簡單并查集的應用.
4. 哈希表和二分查找等高效查找法(數的Hash,串的Hash) (POJ 3349,POJ 3274,POJ 2151,POJ 1840,POJ 2002,POJ 2503)
5. 哈夫曼樹(POJ 3253)
6. 堆
7. trie樹(靜态建樹、動态建樹) (POJ 2513)

四.簡單搜尋

1. 深度優先搜尋 (POJ 2488,POJ 3083,POJ 3009,POJ 1321,POJ 2251)
2. 廣度優先搜尋(POJ 3278,POJ 1426,POJ 3126,POJ 3087.POJ 3414)
3. 簡單搜尋技巧和剪枝(POJ 2531,POJ 1416,POJ 2676,POJ 1129)

五.動态規劃

1. 背包問題. (POJ 1837,POJ 1276)
2. 型如下表的簡單DP(可參考lrj的書 page149):
   • E[j]=opt{D+w(i,j)} (POJ 3267,POJ 1836,POJ 1260,POJ 2533)
   • E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長公共子序列) (POJ 3176,POJ 1080,POJ 1159)
   • C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優二分檢索樹問題)

六.數學

1. 組合數學:
   • 加法原理和乘法原理.
   • 排列組合.
   • 遞推關系.
   • (POJ 3252,POJ 1850,POJ 1019,POJ 1942)
2. 數論.
   • 素數與整除問題
   • 進制位.
   • 同餘模運算.
   • (POJ 2635, POJ 3292,POJ 1845,POJ 2115)
3. 計算方法.
   • 二分法求解單調函數相關知識.(POJ 3273,POJ 3258,POJ 1905,POJ 3122)

七.計算幾何學.

1. 幾何公式.
2. 叉積和點積的運用(如線段相交的判定,點到線段的距離等). (POJ 2031,POJ 1039)
3. 多邊型的簡單算法(求面積)和相關判定(點在多邊型内,多邊型是否相交) (POJ 1408,POJ 1584)
4. 凸包. (POJ 2187,POJ 1113)

中級:

1. C++的标準模版庫的應用. (POJ 3096,POJ 3007)
2. 較為複雜的模拟題的訓練(POJ 3393,POJ 1472,POJ 3371,POJ 1027,POJ 2706)

1. 差分限制系統的建立和求解. (POJ 1201,POJ 2983)
2. 最小費用最大流(POJ 2516,POJ 2195)
3. 雙連通分量(POJ 2942)
4. 強連通分支及其縮點.(POJ 2186)
5. 圖的割邊和割點(POJ 3352)
6. 最小割模型、網絡流規約(POJ 3308)

1. 線段樹. (POJ 2528,POJ 2828,POJ 2777,POJ 2886,POJ 2750)
2. 靜态二叉檢索樹. (POJ 2482,POJ 2352)
3. 樹狀樹組(POJ 1195,POJ 3321)
4. RMQ. (POJ 3264,POJ 3368)
5. 并查集的進階應用. (POJ 1703,POJ 2492)
6. KMP算法. (POJ 1961,POJ 2406)

四.搜尋

1. 最優化剪枝和可行性剪枝
2. 搜尋的技巧和優化 (POJ 3411,POJ 1724)
3. 記憶化搜尋(POJ 3373,POJ 1691)

1. 較為複雜的動态規劃(如動态規劃解特别的施行商問題等) (POJ 1191,POJ 1054,POJ 3280,POJ 2029,POJ 2948,POJ 1925,POJ 3034)
2. 記錄狀态的動态規劃. (POJ 3254,POJ 2411,POJ 1185)
3. 樹型動态規劃(POJ 2057,POJ 1947,POJ 2486,POJ 3140)

1. • 容斥原理.
   • 抽屜原理.
   • 置換群與Polya定理(POJ 1286,POJ 2409,POJ 3270,POJ 1026).
   • 遞推關系和母函數.
2. 數學.
   • 高斯消元法(POJ 2947,POJ 1487,POJ 2065,POJ 1166,POJ 1222)
   • 機率問題. (POJ 3071,POJ 3440)
   • GCD、擴充的歐幾裡德(中國剩餘定理) (POJ 3101)
3. • 0/1分數規劃. (POJ 2976)
   • 三分法求解單峰(單谷)的極值.
   • 矩陣法(POJ 3150,POJ 3422,POJ 3070)
   • 疊代逼近(POJ 3301)
4. 随機化算法(POJ 3318,POJ 2454)
5. 雜題. (POJ 1870,POJ 3296,POJ 3286,POJ 1095)

1. 坐标離散化.
2. 掃描線算法(例如求矩形的面積和周長并,常和線段樹或堆一起使用). (POJ 1765,POJ 1177,POJ 1151,POJ 3277,POJ 2280,POJ 3004)
3. 多邊形的核心(半平面交)(POJ 3130,POJ 3335)
4. 幾何工具的綜合應用.(POJ 1819,POJ 1066,POJ 2043,POJ 3227,POJ 2165,POJ 3429)

進階:

一.基本算法要求:

1. 代碼快速寫成,精簡但不失風格 (POJ 2525,POJ 1684,POJ 1421,POJ 1048,POJ 2050,POJ 3306)
2. 保證正确性和高效性. POJ 3434

1. 度限制最小生成樹和第K最短路. (POJ 1639)
2. 最短路,最小生成樹,二分圖,最大流問題的相關理論(主要是模型建立和求解) (POJ 3155, POJ 2112,POJ 1966,POJ 3281,POJ 1087,POJ 2289,POJ 3216,POJ 2446 )
3. 最優比率生成樹. (POJ 2728)
4. 最小樹形圖(POJ 3164)
5. 次小生成樹.
6. 無向圖、有向圖的最小環

1. trie圖的建立和應用. (POJ 2778)

2. LCA和RMQ問題(LCA(最近公共祖先問題) 有離線算法(并查集+dfs) 和 線上算法

   (RMQ+dfs)).(POJ 1330)

3. 雙端隊列和它的應用(維護一個單調的隊列,常常在動态規劃中起到優化狀态轉移

   的目的). (POJ 2823)

4. 左偏樹(可合并堆).
5. 字尾樹(非常有用的資料結構,也是賽區考題的熱點). (POJ 3415,POJ 3294)

1. 較麻煩的搜尋題目訓練(POJ 1069,POJ 3322,POJ 1475,POJ 1924,POJ 2049,POJ 3426)

2. 廣搜的狀态優化:利用M進制數存儲狀态、轉化為串用hash表判重、按位壓縮存儲

   狀态、雙向廣搜、A*算法. (POJ 1768,POJ 1184,POJ 1872,POJ 1324,POJ 2046,POJ 1482)

3. 深搜的優化:盡量用位運算、一定要加剪枝、函數參數盡可能少、層數不易過大

   、可以考慮雙向搜尋或者是輪換搜尋、IDA*算法. (POJ 3131,POJ 2870,POJ 2286)

1. 需要用資料結構優化的動态規劃. (POJ 2754,POJ 3378,POJ 3017)
2. 四邊形不等式理論.
3. 較難的狀态DP(POJ 3133)

1. 組合數學.
   • MoBius反演(POJ 2888,POJ 2154)
   • 偏序關系理論.
2. 博奕論.
   • 極大極小過程(POJ 3317,POJ 1085)
   • Nim問題.

1. 半平面求交(POJ 3384,POJ 2540)
2. 可視圖的建立(POJ 2966)
3. 點集最小圓覆寫.
4. 對踵點(POJ 2079)

八.綜合題.

(POJ 3109,POJ 1478,POJ 1462,POJ 2729,POJ 2048,POJ 3336,POJ 3315,POJ 2148,POJ 1263)