[转] 程序设计竞赛ACM训练手册

2014-05-28

首先说做ACM是个很锻炼人的过程，可以自已没正式训练过（中间做过很短很短的一段时间）。今天无意看到下面的文章，先不说要求自己几分钟内写多少码，至少这些算法得有空再研究研究，书也买来看看。

首先是编程的能力，一般要做到50行以内的程序不用调试、100行以内的二分钟内调试成功。

第一阶段：练经典常用算法，下面的每个算法给我打上十到二十遍，同时自己精简代码，因为太常用，所以要练到写时不用想，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*算法，最小耗散优先……

算法书有很多可以参考：

1、Concrete Mathematics — A Foundation For Computer Science
Ronald L. Graham ， Donald E. Knuth ， Oren Patashnik
这本书《具体数学》是Stanford计算机系的教材（1970 年开始给研究生授课），书的内容是Knuth的巨著TAOCP第一章的扩展，涉及了计算机科学领域内几乎所有可能遇到的数学知识。书中许多经典问题的解答比目前广泛流传的解法更易懂。对于提高大家的数学修养有很大帮助。

2、Introduction to Algorithms
Thomas H. Cormen ，Charles E. Leiserson ，Ronald L. Rivest ，Clifford Stein
《算法导论》MIT计算机系的经典算法教材。作者Rivest获得过ACM Turing Award，牛！本书内容全面，语言通俗，很适合大家入门。

3、实用算法的分析和程序设计
吴文虎王建德
大名鼎鼎的“黑书”。内容包括了竞赛需要的各种算法，各种层次的读者都适合。

4、网络算法与复杂性理论
谢政李建平
内容很丰富的图论教材

5、算法+数据结构=程序
N.Wirth
Pascal语言的发明人Wirth教授的名著，深入阐述了算法与数据结构的关系，对每个算法都提供详细的Pascal源程序，适合各种水平的读者。

最后，在学习算法提升战斗力的同时，也要多做题目，实战是很有必要的。其实并不是所有的题目都是靠算法的，有一些题目是有多种可以优化的手段，也有一些工程性比较强的题目。上手做和把题做精还是有很大区别的（惭愧的说，我就是属于上手做，没有做精，所以……）。

愿每一位程序设计竞赛爱好者挑战极限！