ACM入门培训资料.doc

的 ACM训练手册 来源: ChinaUnix博客 　日期： 2009.11.06 15:50　(共有0条评论) 我要评论 第一阶段：练经典常用算法，下面的每个算法给我打上十到二十遍，同时自己精简代码，因为太常用，所以要练到写时不用想，10-15分钟内打完。 　　1．最短路（Floyd、Dijstra、BellmanFord）； 　　2．最小生成树（先写个prim，kruscal要用并查集，不好写）； 　　3．大数（高精度）加减乘除； 　　4．二分查找（代码可在五行以内）； 　　5．叉乘、判线段相交、然后写个凸包； 　　6．BFS、DFS，同时熟练hash表（要熟，要灵活,代码要简）； 　　7．数学上的有：辗转相除（两行内），线段交点、多角形面积公式； 　　8．调用系统的qsort, 技巧很多，慢慢掌握； 　　9．任意进制间的转换 第二阶段：练习复杂一点，但也较常用的算法。 如： 　　1．二分图匹配（匈牙利），最小路径覆盖； 　　2．网络流，最小费用流； 　　3．线段树； 　　4. 并查集； 　　5．熟悉动态规划的各个典型：LCS、最长递增子串、三角剖分、记忆化dp ； 　　6．博弈类算法。博弈树，二进制法等； 　　7．最大团，最大独立集； 　　8．判断点在多边形内； 　　9．差分约束系统； 　　10．双向广度有哪些信誉好的足球投注网站、A*算法，最小耗散优先 May the force be with you! R2 声明：由于R2解散，本blog已经于2008年5月关闭！ C++博客 首页 新文章 新随笔 聚合 管理 posts - 52, comments - 32, trackbacks - 0 【zz】POJ题目分类推荐 from zhucheng 前面的那个50题估计能做的都差不多了， 开始做这个分类吧…… 发信人: iamlzx (iamlzx), 信区: ACM_ICPC 标 题: 推荐个比较好的题目分类 发信站: BBS 珞珈山水站 (Sat Dec 22 02:02:08 2007) 把这三个阶段的题目做完，基本上应付现今的ICPC竞赛没问题了…… 大家加油！特别是刚开始的同学，推荐按照这个分类做题 转贴 ACM的算法（觉得很好，有层次感） OJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094) 初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序 (poj1094) (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) 三.数据结构. (1)串 (poj1035,poj3080,poj1936) (2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299) (3)简单并查集的应用. (4)哈希表和二分查找等高效查找法(数的Hash,串的Hash) (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503) (5)哈夫曼树(poj3253) (6)堆 (7)trie树(静态建树、动态建树) (poj2513) 四.简单有哪些信誉好的足球投注网站 (1)深度优先有哪些信誉好的足球投注网站 (poj2488,poj3083,poj3009,poj1321,poj2251) (2)广度优先有哪些信誉好的足球投注网站(poj3278,poj142