北大ACM题分类

1、北大ACM题分类作者:日期:北大AC M题分类20 0 7年06月07日主流算法：星期四21:04最小生成树、网络流1 .搜索/回溯?3.贪心？56.计算几何7.组合数学8 .模拟9.数据结构2.DP （动态规划）4.图论 /D i jkst r a、 ?.数论/解模线性方程/凸壳、同等安置矩形的并的面积与周长/Polya 定理/并查集、堆？1 0.博弈论1、排序1723, 1 7 2 7 ,237 7 , 2380, 1318,2379,1 42 3, 1 6 94 ,2201,237 6 ,9 90, 2001 , 2002 , 2092,176 3,1 8 77,17 8 8, 1828

2、, 1838, 1 8 40,19 2 8, 197 1,1974, 1100 2 （需要字符处理，排序用快排即可较难懂）2 2 31 23 7 1（简单排序）2388（顺序统计算法） 树）1007 （稳定的排序）215 9（题意2 4 1 8（二叉排序2、搜索、回溯、遍历1022 1111d 2243 231 21 2 56 ,1321 ,10,231118 1 129 1 190 1 5 6 2 1 5 64 15 7 3 1 6 55 2184 2 2 252362 237 8 23861 0 10, 101 1, 1018, 102 0, 1054,1062,1363,15 0 1,

3、165 0 ,1659,1 6 64,1753,2078 2083,?, 2303, 2 311 2 8,1 6 64,1166, 1176, 1231,1 2 56 , 1 27 0, 1 3 2 1, 154 3 , 1 61 731,1742,1 7 4 5,1847 , 1915,1 9 50, 203 8,22 386,2 426, ?不易：1 0 2 4, 1 0 54,21简单：0 6,1 5 7,2 182, 218 3 , 2 3 8 1 ,1117, 1167,1708, 1 74 6 , 1775, 187 8, 1903,1 966,2046, 2197,34 9 ,?

4、推荐：1 0 1 1, 1190, 11 91, 1416, 1579, 1632,163 9,1659 ,680, 1683 ,1 691, 170 9, 1714 , 1753, 1771 , 182 6, 185 5,1924, 1935 ,9 79（和迷宫类似）1980 （对剪枝要求较高）1856, 1890,194 8 ,1979, 1980,2170 , 2288, 23 31, 2 339,2340,13、历法100 82 080 （这种题要小心）4、枚举1012, 1 0 4 6 ,1 3 8 7, 1411 ,2245,2 32 6 , 2 3 63,2 381, 1 054

5、（剪枝要求较高），1650 （小数的精度问题）5、数据结构的典型算法容易：1182,165 6,2021,202 3 , 2 0 51 , 215 3 , 2227, 2236,2352, 23 9 5,?不易:1145, 1177, 1195,推荐：1 330, 1 33 8 , 1452 4, 1 9 88, 2004, 2010,（图的最小生成树）2 247,1 2 27, 1661, 1834 ,1 6 34 , 16 8 9,1 6 93, 1 7 03,211 9, 2274,1 ,1470,11 25（弗洛伊德算法），2174 2 16、动态规划103 7 A d ecor a

6、tive fenS to c kb r oker Gr aI 141 Brackets Seque nc1159 P al in d r ome、II 6 0 Po s t Of fice、1163? Th e Tr i145 8C omno n Subse q1 579 Fun c ti on R un195 3 Wor l d Cup Noisc e、?10 50P evi ne、e、7、贪心1042, 106 5, 1 2 30, 1 纯形方法）,2 0 54, 1017, 325,2 3 7 0。模拟a ng lu e n ce、F u n、1887? T e sti nh e Max

7、、1088?滑雪、g th e CATCI ER2386? L ak e Co untin g3 23,1 4 77,132 8, 1 86 2,1716,19 2 21125?1 7 8 4,1328 1 755（或用单,20 5 4, 22 0 9, 2313,2容易：13 6不易：1 7, 111 6 76, 178 6 , 1791, 18 35, 1 9 70,1 4, 1642, 1677, 1681006,1 008, 1 0 1 3 , 1 0 16,1 03,1 0 12,1 0 82, 1 0 99, 116 9, 1 2 98, 1 3 26 , 1350,2317,2

8、32 5 , 2 3 94 ,1886,128 19 28 2 0 8 3 2141 20 1 59、递归166410、字符串处理1 74 7,1748 , 1750,1 9 51,20 03, 2121,23 37, 23 5 9, 2372, 2406,2 408,148 8,15 9 8,1 68 6 , 1706,7 90, 1 8 6 6 ,1888, 1 896,5 9,1211 016 1 051 1126 1 3 18 15721 76 0 ,1782,214 1 , 2145,1 917 1 9 36 20 3 92083 2136 2271 23 1 72 3 3 0,2

9、121 24 0 3011、数论1 006,10 1 4,1 0 23, 1 06 1 ,115 2 , 1 1 8 3 ,173 0 ,2262 12、几何有关的题目凸包：1 1 13, 1228,1794, 2007, 21 8 7 ,1113 wall,2187 be au t y cntest容易：1319, 1654, 16 73, 1675 ,183 6,2074, 2 137, 2318,不易：1 685, 1 6 87, 1 6 96, 187 3 ,1 9 01,21 7 2 , 2333, 13、任意精度运算、数字游戏、高精度计算1001 10231 0 47 1 0 6

10、0 1 0 7 91 1 311140 1142 1207 122 012842891306131 61338 1405 1454 1 5 031 5041 51 9 1 565 16501969 2000 2006 2081 22472 2 62 2 30 5 2316 23891 001,1 22 0 ,4 05 , 1 503,1 001 （高精度乘法）241 3（高精度加法，还有二分查找） 1 4、概率统计 1 0 3 7 ,10 5 015、小费用最大流、最大流21 9 5 goi n g h ome,2400 s u pe rvisor, s uperv i see,10 8 7

11、a plug for UNIX, 1 14 9 P IGS, 1 2 73 dr a in a ge d i t c he s,1274 t he p e rfects tall, 1 3 25 machine schedule,145 9power networ k,ti ng c our se s22 3 9 sel e c1 6、压缩存储的DP10 3 8 bug si nt egrat ed inc , 1185炮兵阵地，2430lazy c o w17、最长公共子串（LCS ）1 080 h U man g ene f un c ti ons,1159 seq uence ,2192

12、 zippe rpalindrom e ,145 8 c omno n sub18、图论及组合数学242 1 Const r uc t i ng R o a d s、2369 P ermu ta tions、2234? M atc he s22 4 3 K n i ght Mo ves、2249? B ino m ial Sho wdown ?2 255 T r ee Recov e ry、Ga me、2 0 8 4 Game of Conn e c t io n s、1906? Th ree powe r s、183 3 排列、1 8 50 Code、15? 6 2 Oil Depo s i

13、t s、1496 Word I ndex、1 306 Com bina t ions、1?1 25 S tockb r oker G ra p evi n e、1129 Cha nne l A ll ocat ion、1146 ID Co de s、1095? Trees Made t ob l e Numbe rs、?2 30 9 BST、2 3 46 Lucky t ickets、2370 Democ r a cy i n da n ge r、23 6 52 10Game(192 219 5 31 958 Stran ge T ow e rs of H anoi、1 9 69 Co un

14、t on Canton、18 0 6Ma nhattan 2 0 25、180? 9 Reg e1 8 44 S u m1870 Bee Bree d i ng、1702? Ev a's? 1 604 J u st theCubesa ck、on Chessboar d、1662? C o I ns、1663?Number S teps、nt i ng、Rope1o fRide to School 、?1 941 W orld C up Nois e、Honey and M ilk Land 2028? WhenC onnections、?19 1 5 Knigh tT he S ie

15、r pt nide r、找规律？2 247 Humn We Meet ?、2?0 8 4CaMoinsk i Fract a l、ve s、a c h ess boa rd、1 642 Stacki ng1656 Counting B l1 6 57 Dist a nee?1 3 13 Bo oklet PriBa l a n ce> 1728? A f lea onF a c ts、1316 Self N umbers、1 3 20 StreetNum bers、13?2 3 Game Pr edict io n、1?3 38 Ugly Nu mb ers、1244 Slots of

16、Fun 、1 250 Tannin g Sal on、1 10 2 L C-D i splay、1 1 47 Bi n ary c odes、1?0 13 C o unterfeit Do l l a r、1 9、博弈类106 7 取石子游戏、17 4 0 A Ne w S to ne G a me 2234? Ma t ch es Game、?1 082 Cale nd a r Game、2348 Euc l id ' s Game2 4 13 How many Fi bs?、2419? Fores t20、简单、模拟题 1001? E xpo nent i a t io n、100

17、2? 4 8 7- 3 279、1 003 Ha ngover、1?7 01 Di s s at i sfyi n g L i ft、2?3 01 Beat theSp r ead!、？2 30 4 Co mb in ation Loc k、2328 Gues sing240 3 Hay Point s 2406 Po w er Stri n2 3 50 A bo v e Av e 2218 Do es This2 2 6 0 Er ror (22 62 Goldb ac h's Cl H i stog r a m218 3 B o vi n e MathGamegs、23?3 9 R

18、o c k, Sci s sors , Paper、 :r a ge、Make Me L ook F a t?、C orrect i on、o nje ctu r e、227?2 B ullseyeTask、Gold Co ins、2?1 74 De co d in gGen iu ses、2?0 0 0、2136? Vert i ca20174 Fl ow La yo ut、20 5 1 Argus、2 08 1 Cale n dar、191 8 Ra nk ing L i192 2 R i d e to Sc1 97 2 Dicest、h ool、1?9 7 0 TheS tac k i

19、n g、Game1974 The Hap py Wor m、19 7 8 Han afud a Shu f fle、1979? Red16 1 7 Cryp t o C olum n s、1?6 6 6 Candy S h a r ing Ga man d B lack、e、 1674? S o rtin g by S、1?5 0 3 I n teg e r Inquiry 、1?5 0 4 A dding Re v e r s e d Num b e r s、1?5 28 Perfect1 5 46 Basic a ll154 7 Clay BThan Said?、1 581 A ContF

20、 r e quenc136 3 Railyul ly、ion、S peak ing、15? 7 3 R obot Moti o n、1575?E a s ie r Don eDecis i on、15?9 0 P ali ndrom e s、14574 Factorialest ingies、s、?1 218 T H E D RUNK JAI L ER、128 1 MAN AGER?113 2 Border、1028? WebNav igation 、2 1、初等数学1 003 Ha n g o ver (o v er )、1 045 B o de P I o t、1 2 54 Hansel

21、an d G r eth e l、F a c t oria 1、14 1 0 In ter se ct i on、?2 36 32 3 65 Rope2 2 42 Th e Cir cumferenc2 2 91 Ro t ten Ro pes、22 9 5 A DP Problem、2126? F acto r ing a Po 1 ynomial s enne C o mpos i t e N umb er s、2196? Spec ia li zed Numbers 191?4 Cra mer's Ru l e、1 8 35宇航员、1 799 Yeeha a !、1?6 0 7

22、De c k、?1 24 4 S lot s of F Inters e c ti ng Li n es、?1 269 In terseB l ock se o f th e C ic t i ng L i n es、14? 0 1rcle、？2F ouu n、191 Mer r -Di g it?1 2691299 Polar Ex plo r er、1183?反正切函数的应用、 22、匹配1274,1422,14 69,1 71 9, 2060 , 2239 ,经典1011 （搜索好题）1 012 （学会打表）10?13 1019?（它体现了很多此类问题的特点）10 5 0（绝对经典的dp

23、）1 088（dp好题）？1 157 （花店,经典的dp ）1163（怎么经典的dp那么多呀？ ？）1 3 28 （贪心）1458?（最长公共子序列）1647（很好的真题,考临场分析准确和下手迅速）?1 654 （学会多边形面积的三角 形求法）1655 （一类无根树的dp问题）1804?（逆序对）2084 （经典组合数学问题）218?7（用凸包求最远点对,求出凸包后应该有0（ N） 的求法，可我就是调不出来）21 9 5 （二分图的最佳匹配）？2 242（计算几何经典）2?2 95 （等式处理）23?5 3 （d P,但要记录最佳路径）2?3 5 4（立体解析几何）2362（搜索好题）2 4

24、10 （读懂题是关键）？2 4 1 1 （经典dp） 趣味1 0 67（很难的数学，但仔细研究，是一片广阔的领域 ）?1 147 （有0（n）的算法, 需要思考）1240 （直到一棵树的先序和后序遍历，那么有几种中序遍历呢？dp ）1426（是数论吗？错,是图论！）164 8 （别用计算几何，用整点这个特点绕过精度的障碍吧 ）183 3 （找规律）1844（貌似dp或是搜索，其实是道有趣的数学题）1 9 22 （贪心，哈哈）223? 1 230?5（不需要高精度噢）232? 8（要仔细噢）235 6 （数论知识）2 3 5 9 （约瑟夫问题变种）2392（有趣的问题）很繁的题1?0 011008?108 7 （构图很烦，还有二分图的最大匹配）？1