ACM 完全分类 POJ.docx

ACM 完全分类 POJ.docx

《ACM 完全分类 POJ.docx》由会员分享，可在线阅读，更多相关《ACM 完全分类 POJ.docx（19页珍藏版）》请在冰点文库上搜索。

ACM完全分类POJ

按照ac的代码长度分类（主要参考最短代码和自己写的代码）

短代码：

0.01K–0.50K；中短代码：

0.51K–1.00K；中等代码量：

1.01K–2.00K；长代码：

2.01K以上。

短：

1147、1163、1922、2211、2215、2229、2232、2234、2242、2245、2262、2301、2309、2313、2334、2346、2348、2350、2352、2381、2405、2406；

中短：

1014、1281、1618、1928、1961、2054、2082、2085、2213、2214、2244、2247、2255、2257、2258、2260、2265、2272、2273、2275、2287、2299、2329、2376；

中等：

1001、1018、1037、1039、1054、1125、1655、2165、2210、2212、2225、2240、2241、2243、2246、2254、2303、2312、2339；

长：

1009、1010、1015、2050。

附注：

短（中短）代码但要有思想（一定难度）：

1014、1147、1618、1961、2054、2082、2232、2244、2255、2273、2287、2299、2313、2348、2352、2376、2406；

长代码但没有难度：

2050。

—————————————————————————————————————————

动态规划：

1037Adecorativefence、1050TotheMax、1088滑雪、1125StockbrokerGrapevine、1141BracketsSequence、1159Palindrome、1160PostOffice、1163TheTriangle、1458CommonSubsequence、1579FunctionRunFun、1887TestingtheCATCHER、1953WorldCupNoise、2386LakeCounting

简单、模拟题：

1001Exponentiation、1002487-3279、1003Hangover、1701DissatisfyingLift、2301BeattheSpread!

、2304CombinationLock、2328GuessingGame、2403HayPoints、2406PowerStrings、2339Rock,Scissors,Paper、2350AboveAverage、2218DoesThisMakeMeLookFat?

、2260ErrorCorrection、2262Goldbach\’sConjecture、2272Bullseye、2136VerticalHistogram、2174DecodingTask、2183BovineMathGeniuses、2000GoldCoins、2014FlowLayout、2051Argus、2081Calendar、1918RankingList、1922RidetoSchool、1970TheGame、1972DiceStacking、1974TheHappyWorm、1978HanafudaShuffle、1979RedandBlack、1617CryptoColumns、1666CandySharingGame、1674SortingbySwapping、1503IntegerInquiry、1504AddingReversedNumbers、1528Perfection、1546BasicallySpeaking、1547ClayBully、1573RobotMotion、1575EasierDoneThanSaid?

、1581AContestingDecision、1590Palindromes、1454FactorialFrequencies、1363Rails、1218THEDRUNKJAILER、1281MANAGER、1132Border、1028WebNavigation、

博弈类

1067取石子游戏、1740ANewStoneGame、2234MatchesGame、1082CalendarGame、2348Euclid\’sGame、2413HowmanyFibs?

、2419Forests

初等数学

1003Hangover、1045BodePlot、1254HanselandGrethel、1269IntersectingLines、1401Factorial、1410Intersection、2363Blocks、2365Rope、2242TheCircumferenceoftheCircle、2291RottenRopes、2295ADPProblem、2126FactoringaPolynomial、2191MersenneCompositeNumbers、2196SpecializedFour-DigitNumbers、1914Cramer\’sRule、1835宇航员、1799Yeehaa!

、1607Deck、1244SlotsofFun、1269IntersectingLines、1299PolarExplorer、1183反正切函数的应用、

图论及组合数学

2421ConstructingRoads、2369Permutations、2234MatchesGame、2243KnightMoves、2249BinomialShowdown、2255TreeRecovery、2084GameofConnections、1906Threepowers、1833排列、1850Code、1562OilDeposits、1496WordIndex、1306Combinations、1125StockbrokerGrapevine、1129ChannelAllocation、1146IDCodes、1095TreesMadetoorder、找规律2247HumbleNumbers、2309BST、2346Luckytickets、2370Democracyindanger、2365Rope、2101HoneyandMilkLand

2028WhenCanWeMeet?

、2084GameofConnections、1915KnightMoves、1922RidetoSchool、1941TheSierpinskiFractal、1953WorldCupNoise、1958StrangeTowersofHanoi、1969CountonCanton、1806Manhattan2025、1809Regetni、1844Sum、1870BeeBreeding、1702Eva\’sBalance、1728Afleaonachessboard、1604JusttheFacts、1642StackingCubes、1656CountingBlack、1657DistanceonChessboard、1662CoIns、1663NumberSteps、1313BookletPrinting、1316SelfNumbers、1320StreetNumbers、1323GamePrediction、1338UglyNumbers、1244SlotsofFun、1250TanningSalon、1102LC-Display、1147Binarycodes、1013CounterfeitDollar、

—————————————————————————————————————————

题目分类

排序1002（需要字符处理，排序用快排即可）1007（稳定的排序）2159（题意较难懂）22312371（简单排序）2388（顺序统计算法）2418（二叉排序树）

回溯搜索：

1979（和迷宫类似）1980（对剪枝要求较高）

数学计算简单（或不值得做的题）：

100310041005106813261656165716581663192219782000201320142017207021012105214021902272230124052419

中等：

1006（中国剩余定理）132319692015（解密码）2081（预处理）2085（找规律）

难：

1014103711472082（这些是上课讲的）

高精度计算：

1001（高精度乘法）2413（高精度加法，还有二分查找）

历法：

10082080（这种题要小心）

枚举：

1054（剪枝要求较高）1650（小数的精度问题）

数据结构的典型算法：

1125（弗洛伊德算法）2421（图的最小生成树）

动态规划：

1163（经典题）

贪心：

13281755（或用单纯形方法）2054

模拟：

12811928208321412015

递归：

1664

字符串处理：

21212403

—————————————————————————————————————————

有标准模型的：

1125116311831979118511841187

寻找新算法的：

10141067114719222082

调节情绪用：

1004950121812811928197820002027

—————————————————————————————————————————

主流算法：

1.搜索　//回溯

2.DP（动态规划）　

3.贪心　

4.图论　//Dijkstra、最小生成树、网络流

5.数论　//解模线性方程

6.计算几何　//凸壳、同等安置矩形的并的面积与周长

7.组合数学　//Polya定理

8.模拟　

9.数据结构　//并查集、堆

10.博弈论　

//表示举例

非主流算法：

1.送分题　

2.构造　

3.高精度　

4.几何　

5.排序　

6.日期/时间处理　（这类题目相当多的）

7.数学方法　

8.枚举　

9.递推　

10.递归　

11.分治　

说明：

　　显然“送分题”不是一种算法。

但是ACM竞赛中经常有一些很简单很简单的题目，具体涉及内容繁杂，难以归类，干脆就管他们叫送分题。

　　几何不同于计算几何，计算几何或者叫S计算几何，以Shamos在1975年发表的一篇论文为诞生标志。

其实两者有很大的不同。

部分题目分类统计：

网络流：

最大流：

1087aplugforUNIX

1149PIGS

1273drainageditches

1274theperfectstall

1325machineschedule

1459powernetwork

2239selectingcourses

最小费用最大流：

2195goinghome

?

2400supervisor,supervisee

压缩存储的DP

1038bugsintegratedinc

1185炮兵阵地

2430lazycow

最长公共子串（LCS）：

1080humangenefunctions

1159palindrome

1458commonsubsequence

2192zipper

凸包

1113wall

2187beautycontest

—————————————————————————————————————————

说明：

递推算动归，离散化算数据结构，并查集算数据结构，博弈算动归，麻烦题一般都是不错的综合题，最短路算图论，数据的有序化算排序

麻烦题：

1697,1712,1713,1720,1729,1765,1772,1858,1872,1960,1963,2050,2122,2162,2219,2237,

简单题目：

1000,1003,1004,1005,1007,1046,1207,1226,1401,1504,1552,1607,1657,1658,1674,1799,1862,1906,1922,1929,1931,1969,1976,2000,2005,2017,2027,2070,2101,2105,2109,2116,2136,2160,2190,2232,2234,2275,2301,2350,2363,2389,2393,2413,2419,

推荐：

1063,1064,1131,1140,1715,2163,

杂题：

1014,1218,1316,1455,1517,1547,1580,1604,1663,1678,1749,1804,2013,2014,2056,2059,2100,2188,2189,2218,2229,2249,2290,2302,2304,2309,2313,2316,2323,2326,2368,2369,2371,2402,2405,2407,

推荐：

1146,1147,1148,1171,1389,1433,1468,1519,1631,1646,1672,1681,1700,1701,1705,1728,1735,1736,1752,1754,1755,1769,1781,1787,1796,1797,1833,1844,1882,1933,1941,1978,2128,2166,2328,2383,2420,

高精度：

1001,1220,1405,1503,

排序：

1002,1318,1877,1928,1971,1974,1990,2001,2002,2092,2379,2388,2418,

推荐：

1423,1694,1723,1727,1763,1788,1828,1838,1840,2201,2376,2377,2380,

搜索

容易：

1128,1166,1176,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,1855,1856,1890,1924,1935,1948,1979,1980,2170,2288,2331,2339,2340,

数据结构

容易：

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,

动态规划

容易：

1018,1050,1083,1088,1125,1143,1157,1163,1178,1179,1189,1208,1276,1322,1414,1456,1458,1609,1644,1664,1690,1699,1740,1742,1887,1926,1936,1952,1953,1958,1959,1962,1975,1989,2018,2029,2033,2063,2081,2082,2181,2184,2192,2231,2279,2329,2336,2346,2353,2355,2356,2385,2392,2424,

不易：

1019,1037,1080,1112,1141,1170,1192,1239,1655,1695,1707,1733,1737,1837,1850,1920,1934,1937,1964,2039,2138,2151,2161,2178,

推荐：

1015,1635,1636,1671,1682,1692,1704,1717,1722,1726,1732,1770,1821,1853,1949,2019,2127,2176,2228,2287,2342,2374,2378,2384,2411,

字符串：

1488,1598,1686,1706,1747,1748,1750,1760,1782,1790,1866,1888,1896,1951,2003,2121,2141,2145,2159,2337,2359,2372,2406,2408,

贪心：

1042,1065,1230,1323,1477,1716,1784,

图论

容易：

1161,1164,1258,1175,1308,1364,1776,1789,1861,1939,1940,1943,2075,2139,2387,2394,2421,

不易：

1041,1062,1158,1172,1201,1275,1718,1734,1751,1904,1932,2173,2175,2296,

网络流：

1087,1273,1698,1815,2195,

匹配：

1274,1422,1469,1719,2060,2239,

Euler：

1237,1637,1394,2230,

推荐：

2049,2186,

计算几何

容易：

1319,1654,1673,1675,1836,2074,2137,2318,

不易：

1685,1687,1696,1873,1901,2172,2333,

凸包：

1113,1228,1794,2007,2187,

模拟

容易：

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,

数学

容易：

1061,1091,1142,1289,1305,1306,1320,1565,1665,1666,1730,1894,1914,2006,2042,2142,2158,2174,2262,2305,2321,2348,

不易：

1067,1183,1430,1759,1868,1942,2167,2171,2327,

推荐：

1423,1450,1640,1702,1710,1721,1761,1830,1930,2140,

—————————————————————————————————————————

POJ部分题目分类

算法入门（简单题）

1000100310041005100610071015（学会dp）1016101710181042（dp）1046（简单数学）1054（简单的剪枝）1062（dp）1068

10951113（凸包，但规模小，O（n^2）的也行）1125112711521154

1183（用笔算算）121812211244128113121313（找找规律）

1315（学会搜索）1321（同1315）1323（dp）132613311491

1493（找规律）1503（高精度）15041517151915471552

1563（考虑仔细一点，还要注意精度）1650（不是好题）1651（dp）1656

1657165816631675（计算几何）16811702（三进制运算）1799

18281862（简单数学）18871906（实战好题）19141915（宽搜）

192819361978197920002019（dp好题）2027（垃圾题）2028

2078（不要重复搜索）208020812083214021412184（活用dp）

219021922193219621992209221122432248（搜索）

2260226122622291230123042309（找规律）23162317

231823252355235723632378（树的dp）238123852393

239423952413（高精度基础）24182419

经典

1011（搜索好题）

1012（学会打表）

1013

1019（它体现了很多此类问题的特点）

1050（绝对经典的dp）

1088（dp好题）

1157（花店，经典的dp）

1163（怎么经典的dp那么多呀？

？

？

）

1328（贪心）

1458（最长公共子序列）

1647（很好的真题，考临场分析准确和下手迅速）

1654（学会多边形面积的三角形求法）

16