ACM培训计划教程.doc

 HYPERLINK /liuxueyang/archive/2012/11/06/2756748.html 转载 ACM训练计划 看完人家的博客，发现任重道远。。。 一位高手对我的建议： 一般要做到50行以内的程序不用调试、100行以内的二分钟内调试成功.acm主要是考算法的，主要时间是花在思考算法上，不是花在写程序与debug上。?下面给个计划你练练： 第一阶段：练经典常用算法，下面的每个算法给我打上十到二十遍，同时自己精简代码，因为太常用，所以要练到写时不用想，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. 把oibh上的论文看看（大概几百篇的，我只看了一点点，呵呵）。?2. 平时扫扫zoj上的难题啦，别老做那些不用想的题.(中大acm的版主经常说我挑简单的来做:-P )?3. 多参加网上的比赛，感受一下比赛的气氛，评估自己的实力.?4. 一道题不要过了就算，问一下人，有更好的算法也打一下。?5. 做过的题要记好 :-) （一） 不可能都完全记住那么多的算法.?常用算法,拿过来就可以写出来?不常用的,拿起书来,看10分钟,就能理解算法(因为以前记过).?对以前没有记过的算法,就不好说了,难的可能要研究好几天.?这样就可以了. 应该熟练掌握的常用的算法应该有:?各种排序算法（插入排序、冒泡排序、选择排序，快速排序，堆排序，归并排序）?线性表(一般的线性表,栈,队列)的插入和删除?二叉树的遍历（前序，中序，后序）?图的遍历（深度优先，广度优先）?二分法查找，排序二叉树，Hash查找（处理冲突的方法）。 （二） 分析一个东西,你可以用不同的眼光去看待,有很多时候,就跟自己生活一样,觉得小时候看待问题很幼稚,现在看问题全面了,而且方式不一样了,为什么,就是成长吧,就跟这个一样的,你对算法,比如写一个程序,可能直接写很简单,可是可以有一些有趣的方式,比如通过什么样来表达,怎么样更高效..等等吧 （三） 于大学里把基本的专业课学扎实就ok，如：数据结构，离散，操作系统等。碰到一些基本的数据结构和算法，如查找排序要根据原理马上能写出相应的代码就行了，我个人是这样理解的，对于更深层次的东西，也是建立在自己熟练的基础之上的吧 （四） 算法与数据结构考验试题精析》第2版 机械工业出版社?如果你想练习的话，这里有N多的题可以来练习，但实际中能用到的比较少，除非搞一些高端的玩意，不过平时也可以在自己的项目中结合使用 ?（五） 数据结构在平时可能用不上，但数据结构可以培养你程序时如果注意效率的意识，一个学过数据结构的人和一个没有学过数结构的人写出来的程序可能在效率上有差别。 （六） 搞ACM需要的掌握的算法.?要注意,ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.?适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红,?发挥自己的长处,这才是重要的. 同时由于个人练习的时候可能有些偏向性,可能上面的总结不是很全,还请大家提出和指正,而且由于ACM的题目中专门针对某个算法的题目可能比较少出现,所以上面的分类中的题有可能有多种解法或者是一些算法的综合,这都不会影响大家做题,希望练习的同学能够认真,扎实地训练,做到真正的理解算法,掌握算法.同时在论坛上还有许多前辈的分类,总结,大家也可以按自己的情况采用.注意FTP上有很多的资料,希望大家好好地利用. 如果同学能在明年暑假前能掌握上面大部分算法,那你也基本上达到了训练的目的,到暑假的时候你就可以选择自己比较喜欢的方面进行加深和