計算機OnlineJudge訓練方案

1、0j上的一些水題(可用來練手和增加自信)(poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094)初期：一 基本算法：(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

2、,floyd,heap-bdijkstra)(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)(3) 最小生成樹算法(prim,kruskal)(poj1789,poj2485,poj1258,poj3026)(4) 拓撲排序(poj1094)(5) 二分圖的最大匹配(匈牙利算法)(pej3944,poj3020)(6) 最人流的增廣路算法(km算法).(poj1459,poj3436)三. 數(shù)據(jù)結(jié)構(gòu).串(poj 1035,poj3080,poj 1936)(2) 排序(快排、歸并排(與逆序數(shù)有關(guān))、堆排)(poj2388,poj2299)(3)

3、 簡單并查集的應(yīng)用.(poj2524)(4) 哈希表和二分查找等高效查找法(數(shù)的hash,串的hash)(poj3349,poj3274,poj2151,poj1840,poj2002,poj2503)(5) 哈夫曼樹(poj3253)堆(7) trie樹(靜態(tài)建樹、動態(tài)建樹)(poj2513,poj1500)四. 簡單搜索(1) 深度優(yōu)先搜索(poj2488,poj3083,poj3009,poj1321 ,poj2251)(2) 廣度優(yōu)先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)(3) 簡單搜索技巧和剪枝(poj2531,poj 1416,poj

4、2676,1129)五動態(tài)規(guī)劃(1) 背包問題.(poj 1837,poj 1276)(2) 型如下表的簡單dp(可參考irj的書page149):1. ej=optd+w(i,j) (poj3267,poj 1836,poj 1260,poj2533)2. ei,j=optdi-1,j+xi,di,j-1+yj,di-1j-1+zij(最長公共子序列)(poj3176, poj 1080, poj 1159)3. ci,j=wi,j+optci,k-1+ck,j.(最優(yōu)二分檢索樹問題)六數(shù)學(1) 組合數(shù)學：1 加法原理和乘法原理.2. 排列組合.3. 遞推關(guān)系.(poj3252, poj

5、1850, poj 1019, poj 1942)(2) 數(shù)論.1. 素數(shù)與整除問題2. 進制位.3. 同余模運算.(poj2635, poj3292,poj1845,poj2115)(3) 計算方法.1. 二分法求解單調(diào)函數(shù)相關(guān)知 w.(poj3273,poj3258,poj1905,poj3122)七計算兒何學.(1) 幾何公式.(2) 叉積和點積的運用(如線段相交的判定，點到線段的距離等).(poj2031,poj 1039)(3) 多邊型的簡單算法(求面積)和相關(guān)判定(點在多邊型內(nèi)，多邊型是否相交)(poj1408,poj 1584)(4) 凸包.(poj2187,poj1113)中級

6、：一.基本算法：(1) c+的標準模版庫的應(yīng)用.(poj3096,poj3007)(2) 較為復雜的模擬題的訓練(poj3393,poj1472,poj3371,poj1027,poj2706)二圖算法：(1) 差分約束系統(tǒng)的建立和求解.(poj1201,poj2983)(2) 最小費用最大流(poj2516,poj2516,poj2195)(3) 雙連通分 ffi(poj2942)(4) 強連通分支及其縮點.(poj2186)(5) 圖的割邊和割點(poj3352)(6) 最小割模型、網(wǎng)絡(luò)流規(guī)約(poj3308,) 三.數(shù)據(jù)結(jié)構(gòu).(1) 線段樹.(poj2528,poj2828,poj277

7、7,poj2886,poj2750)(2) 靜態(tài)二叉檢索樹.(poj2482,poj2352)(3) 樹狀樹組(poj1195,poj3321)(4) rmq. (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) 較為復雜的動態(tài)規(guī)劃(如動態(tài)規(guī)劃解特別的施行商問題等)(poj1191,poj1054,poj3280,poj2029,poj

8、2948,poj1925,poj3034)(2) 記錄狀態(tài)的動態(tài)規(guī)劃.(poj3254,poj2411 ,poj1185)(3) 樹型動態(tài)規(guī)劃(poj2057,poj1947,poj2486,poj3140)六. 數(shù)學(1) 組合數(shù)學：1. 容斥原理.2. 抽屜原理.3. 置換群與 polya 定理(poj1286,poj2409,poj3270,poj1026).4. 遞推關(guān)系和母函數(shù).(2) 數(shù)學.1 高斯消元法(poj2947,poj1487, poj2065,poj 1166,poj 1222)2. 概率問題.(poj3071 ,poj3440)3. gcd、擴展的歐幾里徳(中國剩余定

9、理)(poj3101)(3) 計算方法.1.0/1 分數(shù)規(guī)劃.(poj2976)2. 三分法求解單峰(單谷)的極值.3. 矩陣法(poj3150,poj3422,poj3070)4. 迭代逼近(poj3301)(4) 隨機化算法(poj3318,poj2454)(5) 雜題.(poj1870,poj3296,poj3286,poj1095)七計算兒何學.(1) 坐標離散化.(2) 掃描線算法(例如求矩形的面積和周長并，常和線段樹或堆一起使用).(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)(3) 多邊形的內(nèi)核(半平面交)(poj3130,po

10、j3335)(4) 幾何工具的綜合應(yīng)用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429) 高級：一.基本算法要求：(1) 代碼快速寫成，精簡但不失風格(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)(2) 保證正確性和高效性.poj3434二圖算法：(1) 度限制最小生成樹和笫k最短路.(poj1639)(2) 最短路，最小生成樹，二分圖，最大流問題的相關(guān)理論(主要是模型建立和求解)(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216

11、,poj2446(3) 最優(yōu)比率生成樹.(poj2728)(4) 最小樹形圖(poj3164)(5) 次小生成樹.(6) 無向圖、有向圖的最小環(huán)三. 數(shù)據(jù)結(jié)構(gòu).(1) trie圖的建立和應(yīng)用.(poj2778)(2) lca和rmq問題(lca(最近公共祖先問題)有離線算法(并查集+dfs)和在線篦法(rmq+dfs).(poj1330)(3) 雙端隊列和它的應(yīng)用(維護一個單調(diào)的隊列，常常在動態(tài)規(guī)劃屮起到優(yōu)化狀態(tài)轉(zhuǎn)移的目的).(poj2823)(4) 左偏樹(可合并堆).(5) 后綴樹(罪常有用的數(shù)據(jù)結(jié)構(gòu)，也是賽區(qū)考題的熱點).(poj3415,poj3294)四. 搜索(1) 較麻煩的搜索題

12、目訓練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)(2) r搜的狀態(tài)優(yōu)化:利用m進制數(shù)存儲狀態(tài)、轉(zhuǎn)化為串用hash表判重、按位壓縮存儲狀 態(tài)、雙向廣搜、a*算法.(poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)(3) 深搜的優(yōu)化:盡量用位運算、一定要加剪枝、函數(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) pq邊

13、形不等式理論.(3) 較難的狀態(tài)dp(poj3133)六.數(shù)學(1) 組合數(shù)學.1 .mobius 反演(poj2888,poj2154)2. 偏序關(guān)系理論.(2) 博奕論.1極大極小過程(poj3317,poj1085)2. nim問題.七計算兒何學.(1) 半平而求交(poj3384,poj2540)(2) 可視圖的建立(poj2966)(3) 點集最小圓覆蓋.(4) 對踵點(poj2079)八綜合題.(poj3109,poj 1478, poj 1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj 1263)以及補充dp狀態(tài)設(shè)計與方程總結(jié)1 .

14、不完全狀態(tài)記錄v1青蛙過河問題v2利用區(qū)間dp2. 背包類問題1 0-1背包，經(jīng)典問題v2無限背包，經(jīng)典問題v3判定性背包問題v4帶附屬關(guān)系的背包問題5 + -1背包問題v6雙背包求最優(yōu)值v7構(gòu)造三角形問題v8帶上下界限制的背包問題(012背包)3. 線性的動態(tài)規(guī)劃問題v1積木游戲問題v2決斗(判定性問題)v3圓的最大多邊形問題v4統(tǒng)計單詞個數(shù)問題v5棋盤分割v6 口程安排問題v7最小逼近問題（求出兩數(shù)z比最接近某數(shù)/兩數(shù)之和等于某數(shù)等等）v8方塊消除游戲（某區(qū)間可以連續(xù)消去求最大效益）v9資源分配問題v10數(shù)字三角形問題11漂亮的打印v12郵局問題與構(gòu)造答案v13最高積木問題v14兩段連續(xù)和

15、最人152次幕和問題16n個數(shù)的最大m段子段和v17交叉最大數(shù)問題4. 判定性問題的dp（如判定整除、判定可達性等）1模k問題的dp2特殊的模k問題，求最大（最?。┠的數(shù)v3變換數(shù)問題5. 單調(diào)性優(yōu)化的動態(tài)規(guī)劃1仁sum問題22-sum 問題3序列劃分問題（單調(diào)隊列優(yōu)化）6. 剖分問題（多邊形剖分/石子合并/圓的剖分/乘積最大）v1凸多邊形的三角剖分問題v2乘積最大問題v3多邊形游戲（多邊形邊上是操作符,頂點有權(quán)值）v4石子合并（n3/n八2/nlogn各種優(yōu)化）7. 貪心的動態(tài)規(guī)劃v1最優(yōu)裝載問題v2-部分背包問題v3乘船問題4貪心策略v5雙機調(diào)度問題johnson算法8. 狀態(tài)dpv1牛

16、仔射擊問題（博弈類）v2哈密頓路徑的狀態(tài)dpv3兩支點天平平衡問題v4個有向圖的最接近二部圖9. 樹型dp1 完美服務(wù)器問題（每個節(jié)點有3種狀態(tài)）2小胖守皇宮問題v3網(wǎng)絡(luò)收費問題v4樹中漫游問題v5樹上的博弈v6樹的最大獨立集問題v7樹的最大平衡值問題v 8 構(gòu)造樹的最小環(huán)acm題目分類總結(jié)及pku題目分類acm-題型分類的代碼主流算法：1. 搜索回溯2. dp （動態(tài)規(guī)劃）3. 貪心4. 圖論/dijkstnx、最小生成樹、網(wǎng)絡(luò)流5. 數(shù)論解模線性方程6. 計算兒何凸殼、同等安置矩形的并的面積與周長7. 組合數(shù)學/polya定理8. 模擬9. 數(shù)據(jù)結(jié)構(gòu)并查集、堆10. 博弈論1、排序1423

17、, 1694, 1723, 1727, 1763, 1788, 1828, 1838, 1840, 2201,2376, 2377, 2380, 131 & 1877, 1928, 1971, 1974, 1990, 2001,2002, 2092,2379, 1002 （需要字符處理,排序用快排即可）1007 （穩(wěn) 定的排序）2159 （題意較難懂）2231 2371 （簡單排序）2388 （順序統(tǒng)計算法）2418 （二 叉排序樹）2、搜索、回溯、遍歷1022 lllld 1118 1129 1190 1562 1564 1573 1655 2184 2225 2243 2312 2

18、362 2378 23861010,1011,101 &1020,1054,1062,1256,1321,1363,1501,1650,1659,1664,1753,2078,2083,2303,2310,2329簡單：112& 1166, 1176, 1231, 1256, 1270, 1321, 1543, 1606,1664, 1731, 1742, 1745,1847, 1915, 1950, 203& 2157, 2182, 2183, 2381, 2386, 2426,不易：1024, 1054, 1117, 1167, 1708, 1746, 1775,

19、1878, 1903, 1966, 2046, 2197, 2349,推薦：1011, 1190, 1191, 1416, 1579, 1632, 1639, 1659, 1680, 1683, 1691, 1709, 1714, 1753, 1771, 1826, 1855, 1856, 1890, 1924, 1935, 194& 1979, 1980, 2170, 228& 2331, 2339, 2340,1979 （和迷宮類似）1980 （對剪枝要求較高）3、歷法1008 2080 （這種題要小心）4、枚舉1012, 1046, 1387,1411, 2245, 23

20、26, 2363, 2381, 1054 （剪枝要求較高）,1650 （小數(shù)的精度問題）5、數(shù)據(jù)結(jié)構(gòu)的典型算法容易：1182, 1656, 2021, 2023, 2051,2153, 2227, 2236, 2247, 2352, 2395,不易：1145, 1177, 1195, 1227, 1661, 1834,推薦：1330, 1338, 1451, 1470, 1634, 1689, 1693, 1703, 1724, 1988, 2004, 2010, 2119, 2274, 1125（弗洛伊徳算法），2421 （圖的最小生成樹）6、動態(tài)規(guī)劃1037 a decorative fe

21、nce1050 to the max1088滑雪1125 stockbroker grapevine1141 brackets sequence1159 palindrome1160 post office1163 the triangle1458 common subsequence1579 function run fun1887 testing the catcher1953 world cup noise2386 lake counting7、貪心1042, 1065, 1230, 1323, 1477, 1716, 1784,1328 1755 （或用單純形方法）,2054, 101

22、7,1328,1862,1922 , 2054,2209,2313,2325,2370。8、模擬容易：1006, 1008, 1013, 1016, 1017, 1169, 1298, 1326, 1350, 1363, 1676, 1786, 1791, 1835, 1970, 2317, 2325, 2390,不易：1012, 1082,1099, 1114, 1642, 1677, 1684, 1886,1281 1928 2083 2141 20159、遞歸166410、字符串處理1488, 1598, 1686, 1706, 1747, 1748, 1750, 1760, 1782,

23、 1790, 1866, 1888, 1896, 1951,2003, 2121, 2141, 2145, 2159, 2337, 2359, 2372, 2406, 2408, 1016 1051 1126 1318 1572 1917 1936 2039 2083 2136 2271 2317 2330, 2121 240311、數(shù)論1006,1014,1023,1061,1152,1183,1730,226212、幾何有關(guān)的題目凸包：1113,122& 1794,2007,2187,1113 wall, 2187 beauty contest容易：1319, 1654, 1673

24、, 1675, 1836, 2074, 2137, 2318,不易：1685, 1687, 1696, 1873,1901,2172,2333,13、任意精度運算、數(shù)字游戲、高精度計算1001 1023 1047 1060 1079 1131 1140 1142 1207 1220 1284 1289 1306 1316 1338 1405 1454 1503 1504 1519 1565 1650 1969 2000 2006 2081 2247 2262 2305 2316 2389 1001, 1220, 1405, 1503,1001 (髙精度乘法)2413(高精度加法，還有二分查找)

25、14、概率統(tǒng)計1037,105015、小費用最大流、最大流2195 going home, 2400 supervisor, supervisee, 1087 a plug for unix, 1149 pigs, 1273 drainage ditches, 1274 the perfect stall» 1325 machine schedule, 1459 power network, 2239 selecting courses16、壓縮存儲的dp1038 bugs integrated inc, 1185 炮兵陣地，2430 lazy cow17、最長公共子串(lcs)10

26、80 human gene functions, 1159 palindrome, 1458 common subsequence, 2192 zipper18、圖論及組合數(shù)學2421 constructing roads2369 permutations2234 matches game2243 knight moves2249 binomial showdown2255 tree recovery2084 game of connections1906 three powers1833排列185() code1562 oil deposits1496 word index1306 comb

27、inations1125 stockbroker grapevine1129 channel allocation1146 id codes1095 trees made to order找規(guī)律2247 humble numbers2309 bst、2346 lucky tickets >2370 democracy in danger>2365 rope>2101 honey and milk land2028 when can we meet?>2084 game of connections1915 knight moves>1922 ride to sch

28、ook1941 the sierpinski fractal >1953 world cup noise>1958 strange towers of hanoi >1969 count on canton >1806 manhattan 2025、1809 regetni>1844 sum、1870 bee breeding、1702 evavs balance1728 a flea on a chessboard、1604 just the facts >1642 stacking cubes >1656 counting black>165

29、7 distance on chessboard >1662 coins1663 number steps >1313 booklet printing1316 self numbers >1320 street numbers >1323 game prediction >1338 ugly numbers >1244 slots of fun >1250 tanning salon、1102 lc-display>1147 binary codes>1013 counterfeit dollar>19、博弈類1067取石子游戲、1

30、740 a new stone game>2234 matches game>1082 calendar game、2348 euclidvs game、2413 how many fibs?>2419 forest20、簡單、模擬題1001 exponentiation、1002 487-3279.1003 hangover 、1701 dissatisfying lift>2301 beat the spread! >2304 combination lock>2328 guessing game、2403 hay points、2406 power s

31、trings2339 rock, scissors, paper2350 above average n2218 does this make me look fat?>2260 error correction2262 goldbachvs conjecture >2272 bullseye2136 vertical histogram >2174 decoding task>2183 bovine math geniuses、2000 gold coins、2014 flow layout、2051 argus >2081 calendar >1918

32、ranking list>1922 ride to school.1970 the game>1972 dice stacking >1974 the happy worm1978 hanafuda shuffle、1979 red and black、1617 crypto columns、1666 candy sharing game>1674 sorting by swapping>1503 integer inquiry n1504 adding reversed numbers>1528 perfection a1546 basically spe

33、aking1547 clay bully>1573 robot motion >1575 easier done than said?、1581 a contesting decision>1590 palindromes>1454 factorial frequencies1363 rails >12i8the drunk jailer1281 manager、1132 border1028 web navigation >21、初等數(shù)學1003 hangover>1045 bode plot>1254 hansel and grethel12

34、69 intersecting lines>1401 factorial >1410 intersection2363 blocks、2365 rope、2242 the circumferenee of the circle、2291 rotten ropes >2295 a dp problem >2126 factoring a polynomial >2191 mersenne composite numbers2196 specialized four-digit numbers、1914 cramervs rule1835宇航員、1799 yeehaa

35、!>1607 deck1244 slots of fun >1269 intersecting lines >1299 polar explorer >1183反正切函數(shù)的應(yīng)用、22>匹配1274, 1422, 1469, 1719, 2060, 2239,經(jīng)典1011 （搜索好題）1012 （學會打表）10131019 （它體現(xiàn)了很多此類問題的特點）1050 （絕對經(jīng)典的dp）1088 （dp 好題）1157 （花店，經(jīng)典的dp）1163 （怎么經(jīng)典的dp那么多呀？ ？ ？）1328 （貪心）1458 （最長公共子序列）1647 （很好的真題，考臨場分析準確和下

36、手迅速）1654 （學會多邊形面積的三角形求法）1655 （類無根樹的dp問題）1804 （逆序?qū)Γ?084 （經(jīng)典組合數(shù)學問題）2187 （用凸包求最遠點對，求出凸包后應(yīng)該有o（n）的求法，可我就是調(diào)不出來）2195 （二分圖的最佳匹配）2242 （計算兒何經(jīng)典）2295 （等式處理）2353 （dp,但要記錄最佳路徑）2354 （立體解析兒何）2362 （搜索好題）2410 （讀懂題是關(guān)鍵）2411 （經(jīng)典 dp）趣味1067 （很難的數(shù)學，但仔細研究，是一片廣闊的領(lǐng)域）1147 （有o（n）的算法,需要思考）1240 （直到一棵樹的先序和后序遍歷，那么有幾種中序遍歷呢？ dp）1426

37、（是數(shù)論嗎？錯，是圖論?。?648 （別用計算兒何，用整點這個特點繞過精度的障礙吧）1833 （找規(guī)律）1844 （貌似dp或是搜索，其實是道有趣的數(shù)學題）1922 （貪心,哈哈）22312305 （不需要高精度噢）2328 （要仔細噢）2356 （數(shù)論知識）2359 （約瑟夫問題變種）2392 （有趣的問題）很繁的題100110081087 （構(gòu)圖很煩，還有二分圖的最大兀配）1128 （usaco）124513291550 （考的是讀題和理解能力）1649 （dp）2200 （字符串處理+枚舉）2358 （枚舉和避免重復都很煩）2361 （仔細仔細再仔細）難題1014 （數(shù)學證明比較難，但有那種想法更重要）1037 （比較難的dp）1405 （高精度算法也分有等級之分，不斷改進吧）2002 （不知道有沒有比o（na2*logn）更有的算法？）2054 （極難，很強的思考能力）2085 （組合數(shù)學）2414 （dp,但要剪枝）2415 （搜索）2423 （計算兒何+統(tǒng)計）多解題1002 （可以用排序，也可以用統(tǒng)計的方法）1338 （搜索和dp都可以）1664 （搜索和dp都練一練吧）2082 （這