北大ACM題分類

1、北大ACM題分類作者:日期:北大AC M題分類20 0 7年06月07日主流算法：星期四21:04最小生成樹、網(wǎng)絡(luò)流1 .搜索/回溯?3.貪心？56.計(jì)算幾何7.組合數(shù)學(xué)8 .模擬9.數(shù)據(jù)結(jié)構(gòu)2.DP （動(dòng)態(tài)規(guī)劃）4.圖論 /D i jkst r a、 ?.數(shù)論/解模線性方程/凸殼、同等安置矩形的并的面積與周長/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（順序統(tǒng)計(jì)算法） 樹）1007 （穩(wěn)定的排序）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 （對(duì)剪枝要求較高）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 （小數(shù)的精度問題）5、數(shù)據(jù)結(jié)構(gòu)的典型算法容易：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、動(dòng)態(tài)規(guī)劃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、數(shù)論1 006,10 1 4,1 0 23, 1 06 1 ,115 2 , 1 1 8 3 ,173 0 ,2262 12、幾何有關(guān)的題目凸包：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、任意精度運(yùn)算、數(shù)字游戲、高精度計(jì)算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、概率統(tǒng)計(jì) 1 0 3 7 ,10 5 015、小費(fèi)用最大流、最大流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、壓縮存儲(chǔ)的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、圖論及組合數(shù)學(xué)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、找規(guī)律？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、初等數(shù)學(xué)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?反正切函數(shù)的應(yīng)用、 22、匹配1274,1422,14 69,1 71 9, 2060 , 2239 ,經(jīng)典1011 （搜索好題）1 012 （學(xué)會(huì)打表）10?13 1019?（它體現(xiàn)了很多此類問題的特點(diǎn)）10 5 0（絕對(duì)經(jīng)典的dp

23、）1 088（dp好題）？1 157 （花店,經(jīng)典的dp ）1163（怎么經(jīng)典的dp那么多呀？ ？）1 3 28 （貪心）1458?（最長公共子序列）1647（很好的真題,考臨場(chǎng)分析準(zhǔn)確和下手迅速）?1 654 （學(xué)會(huì)多邊形面積的三角 形求法）1655 （一類無根樹的dp問題）1804?（逆序?qū)Γ?084 （經(jīng)典組合數(shù)學(xué)問題）218?7（用凸包求最遠(yuǎn)點(diǎn)對(duì),求出凸包后應(yīng)該有0（ N） 的求法，可我就是調(diào)不出來）21 9 5 （二分圖的最佳匹配）？2 242（計(jì)算幾何經(jīng)典）2?2 95 （等式處理）23?5 3 （d P,但要記錄最佳路徑）2?3 5 4（立體解析幾何）2362（搜索好題）2 4

24、10 （讀懂題是關(guān)鍵）？2 4 1 1 （經(jīng)典dp） 趣味1 0 67（很難的數(shù)學(xué)，但仔細(xì)研究，是一片廣闊的領(lǐng)域 ）?1 147 （有0（n）的算法, 需要思考）1240 （直到一棵樹的先序和后序遍歷，那么有幾種中序遍歷呢？dp ）1426（是數(shù)論嗎？錯(cuò),是圖論?。?64 8 （別用計(jì)算幾何，用整點(diǎn)這個(gè)特點(diǎn)繞過精度的障礙吧 ）183 3 （找規(guī)律）1844（貌似dp或是搜索，其實(shí)是道有趣的數(shù)學(xué)題）1 9 22 （貪心，哈哈）223? 1 230?5（不需要高精度噢）232? 8（要仔細(xì)噢）235 6 （數(shù)論知識(shí)）2 3 5 9 （約瑟夫問題變種）2392（有趣的問題）很繁的題1?0 011008?108 7 （構(gòu)圖很煩，還有二分圖的最大匹配）？1