PAGE7北大ACM題庫習(xí)題分類與簡介2008-07-3112:03zz題目分類

Postedbyfishheadat2007-01-1312:44:58.0

1、排序

1423,1694,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（題意較難懂）2231

2371（簡單排序）2388（順序統(tǒng)計算法）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,208

3,2303,2310,2329

簡單：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,1979（和迷宮類似）1980（對剪枝要求較高）

3、歷法

10082080（這種題要小心）

4、枚舉

1012，1046，1387，1411，2245，2326，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ī)劃

1037Adecorativefence、

1050TotheMax、

1088滑雪、

1125StockbrokerGrapevine、

1141BracketsSequence、

1159Palindrome、

1160PostOffice、

1163TheTriangle、

1458CommonSubsequence、

1579FunctionRunFun、

1887TestingtheCATCHER、

1953WorldCupNoise、

2386LakeCounting

動態(tài)規(guī)劃

容易：

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,

7、貪心

1042,1065,1230,1784,13281755（或用單純形方法），2054，1017，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,12811928208321412015

9、遞歸

1664

10、字符串處理

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

11、數(shù)論

1006,1014,1023,1061,1152,1183,1730,2262

12、幾何有關(guān)的題目

凸包：1113,1228,1794,2007,2187,1113wall，2187beautycontest

容易：1319,1654,1673,1675,1836,2074,2137,2318,

不易：1685,1687,1696,1873,1901,2172,2333,

13、任意精度運算、數(shù)字游戲、高精度計算

10011023104710601079113111401142120712201284128913061316133814051504151915651650196920002006208122472262230523162389

1001,1220,1405,1503,1001（高精度乘法）2413(高精度加法，還有二分查找)

14、概率統(tǒng)計

1037,1050

15、小費用最大流、最大流

2195goinghome，2400supervisor,supervisee，1087aplugforUNIX，1149PIGS，1273drainageditches，1274theperfectstall，1325machineschedule，1459powernetwork，2239selectingcourses

16、壓縮存儲的DP

1038bugsintegratedinc，1185炮兵陣地，2430lazycow

17、最長公共子串（LCS）

1080humangenefunctions，1159palindrome，1458commonsubsequence，2192zipper

18、圖論及組合數(shù)學(xué)

2421ConstructingRoads、

2369Permutations、

2234MatchesGame、

2243KnightMoves、

2249BinomialShowdown、

2255TreeRecovery、

2084GameofConnections、

1906Threepowers、

1833排列、

1850Code、

1562OilDeposits、

1496WordIndex、

1306Combinations、

1125StockbrokerGrapevine、

1129ChannelAllocation、

1146IDCodes、

1095TreesMadetoOrder、找規(guī)律

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、

19、博弈類

1067取石子游戲、

1740ANewStoneGame、

2234MatchesGame、

1082CalendarGame、

2348Euclid\'sGame、

2413HowmanyFibs、

2419Forest

20、簡單、模擬題

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、

21、初等數(shù)學(xué)

1003Hangover、

1045BodePlot、

1254HanselandGrethel、

1269IntersectingLines、

1401Factorial、

1410Intersection、

2363Blocks、

2365Rope、

2242TheCircumferenceoftheCircle、

2291RottenRopes、

2295ADPProblem、2126FactoringaPolynomial、2191MersenneCompositeNumbers、2196SpecializedFour-DigitNumbers、1914Cramer\'sRule、1835宇航員、1799Yeehaa!、1607Deck、1244SlotsofFun、1269IntersectingLines、1299PolarExplorer、1183反正切函數(shù)的應(yīng)用、22、匹配1274,1422,1469,1719,2060,2239===================================經(jīng)典1011（搜索好題）1012（學(xué)會打表）10131019（它體現(xiàn)了很多此類問題的特點）1050（絕對經(jīng)典的dp）1088（dp好題）1157（花店，經(jīng)典的dp）1163（怎么經(jīng)典的dp那么多呀）1328（貪心）1458（最長公共子序列）1647（很好的真題，考臨場分析準確和下手迅速）1654（學(xué)會多邊形面積的三角形求法）1655（一類無根樹的dp問題）1804（逆序?qū)Γ?084（經(jīng)典組合數(shù)學(xué)問題）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ù)學(xué)，但仔細研究，是一片廣闊的領(lǐng)域）1147（有O(n)的算法，需要思考）1240（直到一棵樹的先序和后序遍歷，那么有幾種中序遍歷呢dp）1426（是數(shù)論嗎錯，是圖論！）1648（別用計算幾何，用整點這個特點繞過精度的障礙吧）1833（找規(guī)律）1844（貌似dp或是搜索，其實是道有趣的數(shù)學(xué)題）1922（貪心，哈哈）22312305（不需要高精度噢）2328（要仔細噢）2356（數(shù)論知識）2