ACM題目分類總結(jié)及pku題目分類

1、ACM題目分類總結(jié)及pku題目分類ACM-題型分類的代碼主流算法：1          搜索/回溯2          DP（動(dòng)態(tài)規(guī)劃）3          貪心4          圖論/Dijkstra、最小生成樹、網(wǎng)絡(luò)流5 

2、         數(shù)論/解模線性方程6          計(jì)算幾何/凸殼、同等安置矩形的并的面積與周長(zhǎng)7          組合數(shù)學(xué)/Polya定理8          模擬9      &

3、#160;   數(shù)據(jù)結(jié)構(gòu)/并查集、堆10      博弈論1、           排序, 1723, 1727, 1763, 1788, 1828, 1838, 1840, 2201, 2376, 2377, 2380, 1318, 1877, 1928, 1971, 1974, 1990, 2001, 2002, 2092, 2379, 1002（需要字符處理，排序用快排即可）1007（穩(wěn)定的排序）2159（題意較難懂）2

4、231 2371（簡(jiǎn)單排序） 2388（順序統(tǒng)計(jì)算法） 2418（二叉排序樹）2、           搜索、回溯、遍歷1022 1111 1118 1129 1190 1562 1564 1573 1655 2184 2225 2243 2312 2362 2378 2386 1010 1011 1018 1020 1054 1062 1256 1321 1363 1501 1650 1659 1664 1753 2078 2083 2303 2310 2329簡(jiǎn)單：1128, 1166, 1

5、176, 1231, 1256, 1270, 1321, 1543, 1606, 1664, 1731, 1742, 1745, 1847, 1915, 1950, 2038, 2157, 2182, 2183, 2381, 2386, 2426不易：1024, 1054, 1117, 1167, 1708, 1746, 1775, 1878, 1903, 1966, 2046, 2197,2349 推薦：1011, 1190, 1191, 1416, 1579, 1632, 1639, 1659, 1680, 1683, 1691, 1709, 1714, 1753, 1771, 1826,

6、 1855, 1856, 1890, 1924, 1935, 1948, 1979, 1980, 2170, 2288, 2331, 2339, 2340,1979（和迷宮類似）1980（對(duì)剪枝要求較高）3、           歷法1008 2080 （這種題要小心）4、           枚舉1387， 2363， 2381，1054（剪枝要求較高），1650 （小數(shù)的精度問題）5、

7、0;          數(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、  

8、;         動(dòng)態(tài)規(guī)劃1037 A decorative fence1050 To the Max1088 滑雪125 Stockbroker Grapevine1141 Brackets Sequence1159 Palindrome1160 Post Office1163 The Triangle1458 Common Subsequence1579 Function Run Fun1887 Testing the CATCHER1953 World Cup Noise2386 Lake Counting

9、7、           貪心, , 1230, 1323, 1477, 1716, 1784,1328 1755（或用單純形方法）,2054,1017,1328,1862, 1922, 2054,2209,2313,2325,2370 8、           模擬容易：1006, 1008, 1013, 1016, 1017, 1169, 1298, 1326, 1350, 1363, 167

10、6, 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, 1790, 1

11、866, 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ù)論 1014, 1023, 1061, 1152, 1183, 1730, 226212、        幾何有關(guān)的題目凸

12、包：1113, 1228, 1794, 2007, 2187,1113 wall，2187 beauty contest容易：1319, 1654, 1673, 1675, 1836, 2074, 2137, 2318, 不易：1685, 1687, 1696, 1873, 1901, 2172, 2333,13、        任意精度運(yùn)算、數(shù)字游戲、高精度計(jì)算1001 1023 1047 1060 1079 1131 1140 1142 1207 1220 1284 1289 1306 1316 1338 1405 14

13、54 1503 1504 1519 1565 1650 1969 2000 2006 2081 2247 2262 2305 2316 2389 1001, 1220, 1405, 1503,1001（高精度乘法） 2413(高精度加法，還有二分查找)14、        概率統(tǒng)計(jì)1037,105015、        小費(fèi)用最大流、最大流2195 going home2400 supervisor, supervisee1087 a plug for U

14、NIX1149 PIGS1273 drainage ditches1274 the perfect stall1325 machine schedule1459 power network2239 selecting courses16、        壓縮存儲(chǔ)的DP1038 bugs integrated inc，1185 炮兵陣地，2430 lazy cow17、        最長(zhǎng)公共子串（LCS）1080 human gene functions，

15、1159 palindrome，1458 common subsequence，2192 zipper18、        圖論及組合數(shù)學(xué)2421 Constructing Roads2369 Permutations2234 Matches Game2243 Knight Moves2249 Binomial Showdown2255 Tree Recovery2084 Game of Connections1906 Three powers1833 排列1850 Code1562 Oil Deposits1496 Wor

16、d Index1306 Combinations1125 Stockbroker Grapevine1129 Channel Allocation1146 ID Codes1095 Trees Made to Order找規(guī)律2247 Humble Numbers2309 BST2346 Lucky tickets2370 Democracy in danger2365 Rope2101 Honey and Milk Land2028 When Can We Meet?2084 Game of Connections1915 Knight Moves1922 Ride to School194

17、1 The Sierpinski Fractal1953 World Cup Noise1958 Strange Towers of Hanoi1969 Count on Canton1806 Manhattan 20251809 Regetni1844 Sum1870 Bee Breeding1702 Evas Balance1728 A flea on a chessboard1604 Just the Facts1642 Stacking Cubes1656 Counting Black1657 Distance on Chessboard1662 CoIns1663 Number St

18、eps1313 Booklet Printing1316 Self Numbers1320 Street Numbers1323 Game Prediction1338 Ugly Numbers1244 Slots of Fun1250 Tanning Salon1102 LC-Display1147 Binary codes1013 Counterfeit Dollar 19、        博弈類 1067 取石子游戲1740 A New Stone Game2234 Matches Game1082 Cale

19、ndar Game 2348 Euclids Game2413 How many Fibs?2419 Forest20、        簡(jiǎn)單、模擬題1001 Exponentiation1002 487-32791003 Hangover1701 Dissatisfying Lift2301 Beat the Spread!2304 Combination Lock2328 Guessing Game2403 Hay Points2406 Power Strings2339 Rock, Scissors, Paper2350

20、 Above Average2218 Does This Make Me Look Fat?2260 Error Correction2262 Goldbachs Conjecture2272 Bullseye2136 Vertical Histogram2174 Decoding Task2183 Bovine Math Geniuses2000 Gold Coins2014 Flow Layout2051 Argus2081 Calendar1918 Ranking List1922 Ride to School1970 The Game1972 Dice Stacking1974 The

21、 Happy Worm1978 Hanafuda Shuffle1979 Red and Black1617 Crypto Columns1666 Candy Sharing Game1674 Sorting by S1503 Integer Inquiry1504 Adding Reversed Numbers1528 Perfection1546 Basically Speaking1547 Clay Bully1573 Robot Motion1575 Easier Done Than Said?1581 A Contesting Decision1590 Palindromes1454

22、 Factorial Frequencies1363 Rails1218 THE DRUNK JAILER1281 MANAGER1132 Border1028 Web Navigation21、        初等數(shù)學(xué)1003 Hangover1045 Bode Plot1254 Hansel and Grethel1269 Intersecting Lines1401 Factorial1410 Intersection2363 Blocks2365 Rope2242 The Circumference of the C

23、ircle2291 Rotten Ropes2295 A DP Problem2126 Factoring a Polynomial2191 Mersenne Composite Numbers2196 Specialized Four-Digit Numbers1914 Cramers Rule1835 宇航員1799 Yeehaa!1607 Deck1244 Slots of Fun1269 Intersecting Lines1299 Polar Explorer1183 反正切函數(shù)的應(yīng)用22、        匹配12

24、74, 1422, 1469, 1719, 2060, 2239,23、        經(jīng)典1011（搜索好題） 1012（學(xué)會(huì)打表）10131019（它體現(xiàn)了很多此類問題的特點(diǎn)）1050（絕對(duì)經(jīng)典的dp）1088（dp好題）1157（花店，經(jīng)典的dp）1163（怎么經(jīng)典的dp那么多呀？）1328（貪心）1458（最長(zhǎng)公共子序列）1647（很好的真題，考臨場(chǎng)分析準(zhǔn)確和下手迅速）1654（學(xué)會(huì)多邊形面積的三角形求法）1655（一類無(wú)根樹的dp問題）1804（逆序?qū)Γ?084（經(jīng)典組合數(shù)學(xué)問題）2187（用凸包求最遠(yuǎn)點(diǎn)對(duì)，求出凸

25、包后應(yīng)該有O(N)的求法，可我就是調(diào)不出來(lái)）2195（二分圖的最佳匹配）2242（計(jì)算幾何經(jīng)典）2295（等式處理）2353（dp，但要記錄最佳路徑）2354（立體解析幾何）2362（搜索好題）2410（讀懂題是關(guān)鍵）2411（經(jīng)典dp）24、        趣味1067（很難的數(shù)學(xué)，但仔細(xì)研究，是一片廣闊的領(lǐng)域）1147（有O(n)的算法，需要思考）1240（直到一棵樹的先序和后序遍歷，那么有幾種中序遍歷呢？dp）1426（是數(shù)論嗎？錯(cuò)，是圖論?。?648（別用計(jì)算幾何，用整點(diǎn)這個(gè)特點(diǎn)繞過精度的障礙吧）1833（找規(guī)律）1844（貌似dp或是搜索，其實(shí)是道有趣的數(shù)學(xué)題）1922（貪心，哈哈）22312305（不需要高精度噢）2328（要仔細(xì)噢）2356（數(shù)論知識(shí)）2359（約瑟夫問題變種）2392（有趣的問題）25、        很繁的題100110081087（構(gòu)圖很煩，還有二分