ACM培训大纲

《ACM培训大纲》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、ACM培训大纲基础内容：数据结构——》搜索——》图论DP数论博弈中级内容数据结构网络流第一章搜索1.二分搜索2.三分搜索3.栈4.队列5.深搜6.广搜第二章数据结构1.优先队列2.并查集3.二叉搜索树4.线段树（单点更新）5.Trie第一章图论1.图的表示1.1二维数组1.2邻接表1.3前向星2.图的遍历2.1双连通分量2.2拓扑排序3.最短路3.1迪杰斯特拉3.2弗洛伊德3.3SPFA4.匹配匈牙利算法5.生成树6.网络流简介第二章动态规划1.状态转移方程2.引入2.10-1背包2.2硬币问题2.3矩

2、阵链乘3.区间DP4.按位DP5.树形DP6.状压DP第三章数论1.欧几里得2.扩展欧几里得3.因数分解4.费马小定理5.欧拉定理6.素数6.1筛法6.2素数判定6.2.1O(√n)方法1.1.1Miller-rabin测试第一章博弈1.Nim和2.SG函数第二章中级数据结构1.树状数组2.RMQ3.KMP4.AC自动机5.线段树（区间更新）第三章图论进阶1.网络流问题综述在很多人眼里，东北大学秦皇岛分校不算是985高校。所以我们要用自己的能力证明我们有985的实力。ACM是计算机界认可度最高的一个比赛

3、，可以说只要区域赛有过奖牌，国内任何IT公司没有理由不要。同时，在高校之中，对一个大学计算机专业的评价，大部分人也会首先看ACM的水平。将ACM打出学校，在国内打出一定成绩，对扩大我校影响力很有帮助。考虑到本校暂时没有进行专题训练的出题能力，专题训练的题目主要从UESTC2014年集训队专题训练中获取，再加上从别的OJ上找一些题目。训练的平台设置在华中科技大学的vertualjudge上面。本人将在毕业之前承担培训任务。在2015学年开始之前，培训计划为每两周一次，中间空闲的时间由大二或者大一熟悉C++

4、的同学给不熟悉C++的同学进行基础的讲解。寒假时间计划每周一次。2015学年开始之后，考虑到本人要进行考研备考，培训的频率定为一个月一次，根据实际情况增加课程，所以将在寒假结束之前尽量完成多的培训任务。培训的目标是在2015年区域赛中能够获得出线的资格，并且在2016年邀请赛中能够有队伍能够拿到银牌的水平。根据各大高校的培训资料及总校给的资料汇总，将ACM的内容分成以下几章。每章的开始根据本人的认知经验，分成必考题和常考题两类。必考题为每场必出题型，大部分水题在必考题范围之内。想取得成绩必考题必须作对。

5、常考题型有时候会最为水题，有时候会作为拉分题。培训分为基础部分和中级部分，本人实力有限，没有能力进行高级部分的讲解。高级部分留给学弟学妹们继续努力^_^。第一章搜索二分和三分是很基础的一种技术。参考外校的培训教材，没有把二分和三分放入搜索一章。但是实在不知道应该放到哪里去，就在这里讲。反正都是搜索。二分最基本的应用是求单调函数跟x轴交点的问题使用的方法，有些算法也会使用二分搜索来降低复杂度。一个应用是在最长递增子序列中将DP的O（n2）算法优化为O（nlogn）三分的应用是求抛物线等在一定区间内有唯一极

6、值的问题中，求极值的方法。栈和队列本属于数据结构的内容，考虑到这两种数据结构在搜索中应用较多，将其放入搜索一章。栈是一种先入先出的数据结构。可以用一个数组来保存栈中元素，用一个指针指向栈顶，就实现了一个栈，也可以用STL中提供的栈。队列是一种先入后出的数据结构。可以用一个数组来保存队列的元素，一个指针指向队列头，一个指针指向队列尾，每次入队列队尾向后一个，出队列队首向后一个。STL也提供了队列。递归转换是一个很常见的优化措施。有些题目可能会卡着让递归形式的算法超时，这个时候就必须改成非递归形式。非递归形

7、式使用栈来实现。典型的例子就是二叉树的后续遍历可以改成非递归形式。深度优先搜索与广度优先搜索是两种最基本的搜索方式。很多启发式的搜索建立在这两种方式之上。本章只设计深度优先及广度优先。本章必须掌握的知识有栈和队列的定义，二叉树遍历的递归与非递归形式，深度优先搜索，广度优先搜索。深刻的理解递归搜索的原理。第一章数据结构数据结构是必考题型之一。优先队列在之前的培训之中讲解过一次，考虑到那次培训没有讲清楚，这里重新再讲一遍。优先队列是一种特殊的队列，它能够在O（logn）的时间内找出队列中优先级最高的元素。虽

8、然STL中提供了优先队列的模板，但是这里要求能够自己实现优先队列并查集是一种集合操作的数据结构。其基本操作是“并”和“查”。实现起来简单，速度快。并查集最直接的运用是图论中最短路算法，在这里仅讲并查集，为图论打下基础。线段树是区间操作很重要的一种数据结构，可以实现单点更新，区间更新，区间查询，复杂度大约是O（√h）。在这里只讲单点更新，区间查询。区间的更新留到中级数据结构讲。字典树是字符串操作的很重要的类型，能够快速查询字符串是否在曾经出现