正文

ACM题目分类总结2005-09-21 02:05:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/ddtme/5069.html

分享到:

ACM-题型分类的代码

主流算法:

Ø         1.搜索 //回溯

Ø         2.DP(动态规划) 

Ø         3.贪心 

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

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

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

Ø         7.组合数学 //Polya定理

Ø         8.模拟 

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

Ø         10.博弈论 

 

 

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(稳定的排序) 2159(题意较难懂) 2231 2371(简单排序) 2388(顺序统计算法) 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,15011650,1659,1664,1753,2078,2083,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、  历法

1008 2080 (这种题要小心)

4、  枚举

10121046 1387 1411 2245 2326 2363 23811054(剪枝要求较高),1650 (小数的精度问题)

5、   数据结构的典型算法

容易: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、  动态规划

1037 A decorative fence

1050 To the Max

1088 滑雪、

1125 Stockbroker Grapevine

1141 Brackets Sequence

1159 Palindrome

1160 Post Office

1163 The Triangle

1458 Common Subsequence

1579 Function Run Fun

1887 Testing the CATCHER

1953 World Cup Noise

2386 Lake Counting

7、  贪心

1042, 1065, 1230, 1323, 1477, 1716, 1784,1328 1755(或用单纯形方法),20541017 13281862 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,1281 1928 2083 2141 2015

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, 1016 1051 1126 1318 1572 1917 1936 2039 2083 2136 2271 2317 23302121 2403

11、数论

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

12、几何有关的题目

凸包:1113, 1228, 1794, 2007, 2187,1113 wall2187 beauty contest

容易:1319, 1654, 1673, 1675, 1836, 2074, 2137, 2318,
不易:1685, 1687, 1696, 1873, 1901, 2172, 2333,

13、任意精度运算、数字游戏、高精度计算

1001 1023 1047 1060 1079 1131 1140 1142 1207 1220 1284 1289 1306 1316 1338 1405 1454 1503 1504 1519 1565 1650 1969 2000 2006 2081 2247 2262 2305 2316 2389
1001, 1220, 1405, 1503,1001
(高精度乘法) 2413(高精度加法,还有二分查找)

14、概率统计

1037,1050

15、小费用最大流、最大流

2195 going home2400 supervisor, supervisee1087 a plug for UNIX1149 PIGS1273 drainage ditches1274 the perfect stall1325 machine schedule1459 power network2239 selecting courses

16、压缩存储的DP

1038 bugs integrated inc1185 炮兵阵地,2430 lazy cow

17、最长公共子串(LCS

1080 human gene functions1159 palindrome1458 common subsequence2192 zipper

18、图论及组合数学

2421 Constructing Roads

2369 Permutations

2234 Matches Game

2243 Knight Moves

2249 Binomial Showdown

2255 Tree Recovery

2084 Game of Connections

1906 Three powers

1833 排列、

1850 Code

1562 Oil Deposits

1496 Word Index

1306 Combinations

1125 Stockbroker Grapevine

1129 Channel Allocation

1146 ID Codes

1095 Trees Made to Order、找规律

2247 Humble Numbers

2309 BST

2346 Lucky tickets

2370 Democracy in danger

2365 Rope

2101 Honey and Milk Land
2028 When Can We Meet?

2084 Game of Connections

1915 Knight Moves

1922 Ride to School

1941 The Sierpinski Fractal

1953 World Cup Noise

1958 Strange Towers of Hanoi

1969 Count on Canton

1806 Manhattan 2025

1809 Regetni

1844 Sum

1870 Bee Breeding

1702 Eva\'s Balance

1728 A flea on a chessboard

1604 Just the Facts

1642 Stacking Cubes

1656 Counting Black

1657 Distance on Chessboard

1662 CoIns

1663 Number Steps

1313 Booklet Printing

1316 Self Numbers

1320 Street Numbers

1323 Game Prediction

1338 Ugly Numbers

1244 Slots of Fun

1250 Tanning Salon

1102 LC-Display

1147 Binary codes

1013 Counterfeit Dollar

19、博弈类

1067 取石子游戏、

1740 A New Stone Game

2234 Matches Game

1082 Calendar Game

2348 Euclid\'s Game

2413 How many Fibs?

2419 Forest

20、简单、模拟题
1001 Exponentiation

1002 487-3279

1003 Hangover

1701 Dissatisfying Lift

2301 Beat the Spread!

2304 Combination Lock

2328 Guessing Game

2403 Hay Points

2406 Power Strings

2339 Rock, Scissors, Paper

2350 Above Average

2218 Does This Make Me Look Fat?

2260 Error Correction

2262 Goldbach\'s Conjecture

2272 Bullseye

2136 Vertical Histogram

2174 Decoding Task

2183 Bovine Math Geniuses

2000 Gold Coins

2014 Flow Layout

2051 Argus

2081 Calendar

1918 Ranking List

1922 Ride to School

1970 The Game

1972 Dice Stacking

1974 The Happy Worm

1978 Hanafuda Shuffle

1979 Red and Black

1617 Crypto Columns

1666 Candy Sharing Game

1674 Sorting by Swapping

1503 Integer Inquiry

1504 Adding Reversed Numbers

1528 Perfection

1546 Basically Speaking

1547 Clay Bully

1573 Robot Motion

1575 Easier Done Than Said?

1581 A Contesting Decision

1590 Palindromes

1454 Factorial Frequencies

1363 Rails

1218 THE DRUNK JAILER

1281 MANAGER

1132 Border

1028 Web Navigation

21、初等数学

1003 Hangover

1045 Bode Plot

1254 Hansel and Grethel

1269 Intersecting Lines

1401 Factorial

1410 Intersection

2363 Blocks

2365 Rope

2242 The Circumference of the Circle

2291 Rotten Ropes

2295 A DP Problem

2126 Factoring a Polynomial

2191 Mersenne Composite Numbers

2196 Specialized Four-Digit Numbers

1914 Cramer\'s Rule

1835 宇航员、

1799 Yeehaa!

1607 Deck

1244 Slots of Fun

1269 Intersecting Lines

1299 Polar Explorer

1183 反正切函数的应用、

22、匹配

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

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

经典
1011
(搜索好题)
1012
(学会打表)

1013
1019
(它体现了很多此类问题的特点)
1050
(绝对经典的dp
1088
dp好题)
1157
(花店,经典的dp
1163
(怎么经典的dp那么多呀???)
1328
(贪心)
1458
(最长公共子序列)
1647
(很好的真题,考临场分析准确和下手迅速)
1654
(学会多边形面积的三角形求法)
1655
(一类无根树的dp问题)
1804
(逆序对)
2084
(经典组合数学问题)
2187
(用凸包求最远点对,求出凸包后应该有O(N)的求法,可我就是调不出来)
2195
(二分图的最佳匹配)
2242
(计算几何经典)
2295
(等式处理)
2353
dp,但要记录最佳路径)
2354
(立体解析几何)
2362
(搜索好题)
2410
(读懂题是关键)
2411
(经典dp

趣味
1067
(很难的数学,但仔细研究,是一片广阔的领域)
1147
(有O(n)的算法,需要思考)
1240
(直到一棵树的先序和后序遍历,那么有几种中序遍历呢?dp
1426
(是数论吗?错,是图论!)
1648
(别用计算几何,用整点这个特点绕过精度的障碍吧)
1833
(找规律)
1844
(貌似dp或是搜索,其实是道有趣的数学题)
1922
(贪心,哈哈)
2231
2305
(不需要高精度噢)
2328
(要仔细噢)
2356
(数论知识)
2359
(约瑟夫问题变种)
2392
(有趣的问题)

很繁的题
1001
1008
1087
(构图很烦,还有二分图的最大匹配)
1128
USACO
1245
1329
1550
(考的是读题和理解能力)
1649
dp
2200
(字符串处理+枚举)
2358
(枚举和避免重复都很烦)
2361
(仔细仔细再仔细)

难题
1014
(数学证明比较难,但有那种想法更重要)
1037
(比较难的dp
1405
(高精度算法也分有等级之分,不断改进吧)
2002
(不知道有没有比O(n^2*logn)更有的算法?)
2054
(极难,很强的思考能力)
2085
(组合数学)
2414
dp,但要剪枝)
2415
(搜索)
2423
(计算几何+统计)

多解题
1002
(可以用排序,也可以用统计的方法)
1338
(搜索和dp都可以)
1664
(搜索和dp都练一练吧)
2082
(这可是我讲的题噢)
2352
(桶排和二叉树都行)

Note:
1011:
很经典的剪支
1014:
难在数学上
1017:
严格的数学证明貌似不容易
1021:
有点繁,考察对图形进行各种旋转的处理
1083:
巧妙的思考角度
1150:
分奇偶讨论,lg(n)算法
1218:
三行就够了,虽然简单,但也有优劣之别
1505:
二分加贪心
1654:
做法也许很多吧,本人用有向面积做的
1674:
计算圈的个数(算是graph )
1700:
数学证明不容易

1742: O(m*n)
的算法
1863:
要耐心地慢慢写…^_^
1988:
并查集

2051:

2078:
不难,但剪支可以做到很好
2082::O(n),
你想到了吗?
2084:
卡特兰数
2182:
线段树
2195:
最小费用最大流
2234:
经典博弈算法
2236:
并查集
2299:
二分思想
2395: Kruskal
最小生成树的拓展
2406: KMP
2411:
用二进制串来表示状态

阅读(14717) | 评论(3)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

loading...
您需要登录后才能评论,请 登录 或者 注册