杭電acm分類

2012-04-14 16:34

youxin

閱讀(919)

評論(0)

編輯

舉報

第一個分類版本:

基礎題：1000、1001、1004、1005、1008、1012、1013、1014、1017、1019、1021、1028、1029、1032、1037、1040、1048、1056、1058、1061、1070、1076、1089、1090、1091、1092、1093、1094、1095、1096、1097、1098、1106、1108、1157、1163、1164、1170、1194、1196、1197、1201、1202、1205、1219、1234、1235、1236、1248、1266、1279、1282、1283、1302、1303、1323、1326、1330、1334、1335、1339、1390、1391、1393、1395、1397、1405、1406、1407、1408、1412、1418、1420、1465、1491、1555、1562、1563、1570、1587、1673、1678、1708、1718、1720、1785、1799、1859、1862、1877、1898、1976、1977、1985、1994、2000、2001、2002、2003、2004、2005、2006、2007、2008、2009、2010、2011、2012、2013、2014、2015、2016、2017、2018、2019、2020、2021、2022、2023、2024、2025、2026、2027、2028、2029、2030、2031、2032、2033、2034、2035、2039、2040、2042、2043、2048、2049、2051、2053、2055、2056、2057、2060、2061、2071、2073、2075、2076、2078、2081、2083、2088、2090、2092、2093、2095、2096、2097、2098、2099、2101、2103、2106、2107、2109、2113、2114、2115、2123、2131、2132、2133、2135、2136、2137、2138、2139、2143、2148、2153、2156、2161、2162、2164、2178、2186、2192、2200、2201、2212、2304、2309、2317、2401、2500、2502、2503、2504、2519、2520、2521、2523、2524、2535、2537、2539、2547、2548、2549、2550、2551、2552、2555、2560、2561、2562、2566、2567、2568、2700、2710、

DP：1003、10240、1029、1069、1074、1087、1114、1159、1160、1171、1176、1203、1231、1257、1260、1284、1421、1789、1978、2059、2084、2159、2191、2544、2571、2602、2709、

搜尋：1010、1015、1016、1026、1072、1075、1175、1180、1181、1238、1239、1240、1241、1242、1253、1254、1312、1372、1548、1597、1671、1677、1728、1800、1983、2102、2141、2553、2563、2605、2612、2614、1616、2717

貪心：1009、1045、1049、1050、1051、1052、1257、1800、2037、2111、2124、2187、2391、2570

數學題：1018、1065、1071、1115、1141、1162、1212、1220、1492、1593、1701、1722、1798、1840、1999、2036、2080、2086、2089、2105、2108、2134、2303、2393、2438、2529、2547、2548、2552、2554、2601、2603、2701、

遞推：1133、1143、1207、1249、1267、1284、1290、1297、1396、1992、1995、1996、2013、2014、2044、2045、2046、2047、2050、2064、2065、2067、2068、2070、2077、2085、2151、2154、2160、2190、2501、2512、2563、2569、2709、2716、

字元串：1020、1039、1043、1062、1073、1075、1088、1113、1161、1200、1251、1256、1288、1321、1328、1379、1804、1860、1982、1984、2017、2024、2025、2026、2027、2043、2052、2054、2072、2074、2087、2131、2137、2140、2163、2203、2206、2352、2500、2549、2564、2565、2567、2572、2609、2607、2707、2708、2719、2721、2723、

大數：1002、1042、1133、1250、1297、1715、1753、1865、2100、

胡搞：1022、1027、1030、1035、1128、1165、1209、1210、1215、1222、1228、1229、1230、1237、1259、1276、1286、1337、1342、1361、1370、1506、1577、1597、1702、1716、1727、1868、1870、1896、1981、1986、1987、1988、1997、1998、1999、2058、2062、2089、2090、2094、2104、2116、2117、2135、2175、2183、2184、2197、2303、2368、2370、2374、2511、2522、2527、2600、2615、2703、2711、2714、2715、2725、

博弈：1077、1404、1517、1524、1525、1527、1536、1564、1729、1730、1846、1847、1848、1849、1850、2147、2149、2176、2177、2188

母函數：1085、1171、1398、2079、2082、2110、2152、2189、2566、

hash：1264、1280、1425、1496、1800、2522、2600、

第二種分類文章：

1001 這個就不用說了吧

1002 簡單的大數

1003 DP經典問題，最大連續子段和

1004 簡單題

1005 找規律（循環點）

1006 感覺有點BT的題，我到現在還沒過

1007 經典問題，最近點對問題，用分治

1008 簡單題

1009 貪心

1010 搜尋題，剪枝很關鍵

1011

1012 簡單題

1013 簡單題（有個小陷阱）

1014 簡單題

1015 可以看作搜尋題吧

1016 經典的搜尋

1017 簡單數學題

1018 簡單數學題

1019 簡單數學題

1020 簡單的字元串處理

1021 找規律的數學題

1022 資料結構的題（棧的應用）

1023 特殊的數（Catalan Number）

1024 經典DP，最大M子段和

1025 經典DP，最長遞增子序列（要用NLogN的方法過）

1026 搜尋

1027 數學題（或用STL）

1028 經典問題，整數拆分，用母函數做

1029 簡單題（一般方法容易逾時）

1030 簡單題，可用模拟過

1031 簡單題

1032 簡單題

1033 模拟題

1034 Candy Sharing Game

1035 模拟題

1036 簡單題

1037 簡單題，不是一般的簡單

1038 簡單題

1039 字元串處理

1040 簡單題，排序

1041 簡單題，用大數

1042 大數

1043 經典搜尋題，八數位問題

1044 稍微有點麻煩的搜尋題

1045 搜尋題，可用比對做

1046 簡單題

1047 簡單的大數

1048 簡單字元串處理

1049 簡單題

1050 貪心

1051 經典貪心，也可以用DP

1052 貪心

1053 貪心，關于Huffman編碼

1054 二分比對

1055 二分比對

1056 簡單題

1057 模拟題

1058 經典問題，醜數，DP

1059 經典問題，可以用母函數或DP（不針對題目優化都會逾時）

1060 數學題

1061 數學題

1062 簡單字元串處理

1063 模拟大數

1064 簡單題

1065 簡單題

1066 數學題，找規律

1067

1068 經典二分比對

1069 經典DP

1070 簡單題

1071 簡單數學題

1072 搜尋

1073 字元串處理

1074 DP

1075 字典樹

1076 簡單題

1077

1078 DP

1079 博弈（DP）

1080 DP

1081 經典DP

1082 簡單題

1083 二分比對

1084 簡單題

1085 母函數

1086 簡單幾何題

1087 簡單DP

1088 字元串處理

1089~1096 （練習輸入輸出的8個題目）

1097 簡單數學題

1098 數學題，注意找規律

1099 數學題

模拟題, 枚舉

1002 1004 1013 1015 1017 1020 1022 1029 1031 1033 1034 1035 1036 1037 1039 1042 1047 1048 1049 1050 1057 1062 1063 1064 1070 1073 1075 1082

1083 1084 1088 1106 1107 1113 1117 1119 1128 1129 1144 1148 1157 1161 1170 1172 1177 1197 1200 1201 1202 1205 1209 1212(大數取模) 1216（連結清單）

1218 1219 1225 1228 1229 1230 1234 1235 1236 1237 1239 1250

1256 1259 1262 1263 1265 1266 1276 1279 1282 1283 1287 1296 1302 1303 1304 1305 1306 1309 1311 1314

複雜模拟

搜尋，遞歸求解

1010 1016 1026 1043(雙廣) 1044 (BFS+DFS) 1045 1067 1072 1104 1175 1180 1195 1208 1226 1238 1240 1241 1242 1258 1271 1312 1317

博奕

1079

動态規劃

1003 1024 1025 1028 1051 1058 1059 1069 1074 1078 1080 1081 1085 1087 1114 1158 1159 1160 1171 1176 1181 1203 1224 1227 1231 1244 1248 1253

1254 1283 1300

數學，遞推，規律

1005 1006 1012 1014 1018 1019 1021 1023 1027 1030 1032 1038 1041 1046 1059 1060 1061 1065 1066 1071(微積分) 1097 1098 1099 1100 1108 1110 1112

1124 1130 1131 1132 1134 1141 1143 1152 1155(實體題) 1163 1165 1178 1194 1196(lowbit) 1210 1214 1200 1221 1223 1249 1261 1267 1273 1290 1291

1292 1294 1297 1313 1316

數論

1164 1211 1215 1222 1286 1299

計算幾何

1086 1115 1147

貪心

1009 1052 1055 1257

并查集

1198 1213 1232 1272

線段樹,離散化

1199 1255

圖論

最短路相關的問題 1142 1162 1217 1301

二分圖問題 1054 1068 1150 1151 1281

其他

1053 (huffman) 1102(MST) 1116（歐拉回路） 1233(MST) 1269（強連通）

資料結構

1103（堆+模拟）1166（數狀樹組）1247 1251 1285（Topol） 1298

漢諾塔系列

1207

最近頂點對 1007

1500 DP

1501 DP

1502 DP or 記憶化

1503 DP

1504 模拟

1505 DP

1506 DP

1507 2分比對

1508 記憶化容易點

1509 模拟

1510 DP

1511 搜尋可以過

1512 左偏樹

1513 DP

1514 DP

1515 DFS

1516 DP

1517 博奕

1518 搜尋

1519 DP（不确定）

1520 樹狀DP

1521 數學題，母函數什麼的。其實都可以過

1522 穩定婚姻

1523 DP

1524 博弈

1525 博弈

1526 Maxflow

1527 博弈

1528 2分比對

1529 簡單題

1530 最大團

1531 差分限制

1532 Maxflow 入門題

1533 KM Or 最小費用流

1534 差分限制

1535 差分限制

1536 博弈

1537 模拟加置換群的理論 CODE可以短些，其實沒必要。。。

1538 很有意思的題目。據說是Microsoft亞洲總裁面試的題目

1539 搜尋

1540 線段樹

1541 樹狀數組

1542 離散，線段樹

1543 線段樹

1544 簡單的

1545 DP

1546 搜尋

1547 模拟

1548 模拟

1551 2分答案

1553

1554

1555 簡單

1556 技巧。數學

1557 搜尋

1558 并查 + 線段判交

1559 DP

1560 減支 + 搜尋

1561 樹狀DP

1562 暴力 between 1000 and 9999

1563 簡單

1564 博弈。

1565 狀态DP

1566 數學

1567 模拟

1568 大數

1569 最小割

1570 數學

1571 最段路

1572 搜尋

1573 數學

1574 DP

1575 2分

1576 數論

1577 模拟，處理精度

1579 記憶化

1580 DP

1582 搜尋

1583 模拟

1584 搜尋

1585

1586

1587 簡單題目

1591 模拟

1592 簡單

1593 數學

1594 數學

1595 圖論

1596 圖論

1597 圖論

1598 圖論

1599 圖論

----------------------------------------------------------------------------------------------------------

分類3：

綜合總結

OJ上的一些水題(可用來練手和增加自信)

(poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094)

初期:

一.基本算法:

(1)枚舉. (poj1753,poj2965)

(2)貪心(poj1328,poj2109,poj2586)

(3)遞歸和分治法.

(4)遞推.

(5)構造法.(poj3295)

(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)

二.圖算法:

(1)圖的深度優先周遊和廣度優先周遊.

(2)最短路徑算法(dijkstra,bellman-ford,floyd,heap+dijkstra)

(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)

(3)最小生成樹算法(prim,kruskal)

(poj1789,poj2485,poj1258,poj3026)

(4)拓撲排序 (poj1094)

(5)二分圖的最大比對 (匈牙利算法) (poj3041,poj3020)

(6)最大流的增廣路算法(KM算法). (poj1459,poj3436)

三.資料結構.

(1)串 (poj1035,poj3080,poj1936)

(2)排序(快排、歸并排(與逆序數有關)、堆排) (poj2388,poj2299)

(3)簡單并查集的應用.

(4)哈希表和二分查找等高效查找法(數的Hash,串的Hash)

(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)

(5)哈夫曼樹(poj3253)

(6)堆

(7)trie樹(靜态建樹、動态建樹) (poj2513)

四.簡單搜尋

(1)深度優先搜尋 (poj2488,poj3083,poj3009,poj1321,poj2251)

(2)廣度優先搜尋(poj3278,poj1426,poj3126,poj3087.poj3414)

(3)簡單搜尋技巧和剪枝(poj2531,poj1416,poj2676,1129)

五.動态規劃

(1)背包問題. (poj1837,poj1276)

(2)型如下表的簡單DP(可參考lrj的書 page149):

1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)

2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長公共子序列)

(poj3176,poj1080,poj1159)

3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優二分檢索樹問題)

六.數學

(1)組合數學:

1.加法原理和乘法原理.

2.排列組合.

3.遞推關系.

(POJ3252,poj1850,poj1019,poj1942)

(2)數論.

1.素數與整除問題

2.進制位.

3.同餘模運算.

(poj2635, poj3292,poj1845,poj2115)

(3)計算方法.

1.二分法求解單調函數相關知識.(poj3273,poj3258,poj1905,poj3122)

七.計算幾何學.

(1)幾何公式.

(2)叉積和點積的運用(如線段相交的判定,點到線段的距離等). (poj2031,poj1039)

(3)多邊型的簡單算法(求面積)和相關判定(點在多邊型内,多邊型是否相交)

(poj1408,poj1584)

(4)凸包. (poj2187,poj1113)

中級:

一.基本算法:

(1)C++的标準模版庫的應用. (poj3096,poj3007)

(2)較為複雜的模拟題的訓練(poj3393,poj1472,poj3371,poj1027,poj2706)

二.圖算法:

(1)差分限制系統的建立和求解. (poj1201,poj2983)

(2)最小費用最大流(poj2516,poj2516,poj2195)

(3)雙連通分量(poj2942)

(4)強連通分支及其縮點.(poj2186)

(5)圖的割邊和割點(poj3352)

(6)最小割模型、網絡流規約(poj3308, )

三.資料結構.

(1)線段樹. (poj2528,poj2828,poj2777,poj2886,poj2750)

(2)靜态二叉檢索樹. (poj2482,poj2352)

(3)樹狀樹組(poj1195,poj3321)

(4)RMQ. (poj3264,poj3368)

(5)并查集的進階應用. (poj1703,2492)

(6)KMP算法. (poj1961,poj2406)

四.搜尋

(1)最優化剪枝和可行性剪枝

(2)搜尋的技巧和優化 (poj3411,poj1724)

(3)記憶化搜尋(poj3373,poj1691)

五.動态規劃

(1)較為複雜的動态規劃(如動态規劃解特别的施行商問題等)

(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)

(2)記錄狀态的動态規劃. (POJ3254,poj2411,poj1185)

(3)樹型動态規劃(poj2057,poj1947,poj2486,poj3140)

六.數學

(1)組合數學:

1.容斥原理.

2.抽屜原理.

3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).

4.遞推關系和母函數.

(2)數學.

1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)

2.機率問題. (poj3071,poj3440)

3.GCD、擴充的歐幾裡德(中國剩餘定理) (poj3101)

(3)計算方法.

1.0/1分數規劃. (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)多邊形的核心(半平面交)(poj3130,poj3335)

(4)幾何工具的綜合應用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)

進階:

一.基本算法要求:

(1)代碼快速寫成,精簡但不失風格

(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)

(2)保證正确性和高效性. poj3434

二.圖算法:

(1)度限制最小生成樹和第K最短路. (poj1639)

(2)最短路,最小生成樹,二分圖,最大流問題的相關理論(主要是模型建立和求解)

(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446

(3)最優比率生成樹. (poj2728)

(4)最小樹形圖(poj3164)

(5)次小生成樹.

(6)無向圖、有向圖的最小環

三.資料結構.

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

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

(RMQ+dfs)).(poj1330)

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

目的). (poj2823)

(4)左偏樹(可合并堆).

(5)字尾樹(非常有用的資料結構,也是賽區考題的熱點).

(poj3415,poj3294)

四.搜尋

(1)較麻煩的搜尋題目訓練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)

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

搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)

(3)深搜的優化:盡量用位運算、一定要加剪枝、函數參數盡可能少、層數不易過大、可以考慮雙向

搜尋或者是輪換搜尋、IDA*算法. (poj3131,poj2870,poj2286)

五.動态規劃

(1)需要用資料結構優化的動态規劃.

(poj2754,poj3378,poj3017)

(2)四邊形不等式理論.

(3)較難的狀态DP(poj3133)

六.數學

(1)組合數學.

1.MoBius反演(poj2888,poj2154)

2.偏序關系理論.

(2)博奕論.

1.極大極小過程(poj3317,poj1085)

2.Nim問題.

七.計算幾何學.

(1)半平面求交(poj3384,poj2540)

(2)可視圖的建立(poj2966)

(3)點集最小圓覆寫.

(4)對踵點(poj2079)

八.綜合題.

(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)

更多分類；

http://www.cnblogs.com/SueMiller/archive/2011/07/31/2122480.html

分類 ACM/ICPC