ACM培训大纲.docx

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.3 SPFA4. 匹配 匈牙利算法5. 生成树6. 网络流简介第四章 动态规划1. 状态转移方程2. 引入2.1 0-1背包2.2 硬币问题2.3 矩阵链乘3. 区间DP4. 按位DP5. 树形DP6. 状压DP第五章 数论1. 欧几里得2. 扩展欧几里得3. 因数分解4. 费马小定理5. 欧拉定理6. 素数6.1 筛法6.2 素数判定6.2.1 O(n)方法6.2.2 Miller-rabin测试 第六章 博弈1. Nim和2. SG函数第七章 中级数据结构1. 树状数组2. RMQ3. KMP4. AC自动机5. 线段树（区间更新）第八章 图论进阶1. 网络流问题综述在很多人眼里，东北大学秦皇岛分校不算是985高校。所以我们要用自己的能力证明我们有985的实力。ACM是计算机界认可度最高的一个比赛，可以说只要区域赛有过奖牌，国内任何IT公司没有理由不要。同时，在高校之中，对一个大学计算机专业的评价，大部分人也会首先看ACM的水平。将ACM打出学校，在国内打出一定成绩，对扩大我校影响力很有帮助。 考虑到本校暂时没有进行专题训练的出题能力，专题训练的题目主要从UESTC 2014年集训队专题训练中获取，再加上从别的OJ上找一些题目。训练的平台设置在华中科技大学的vertual judge上面。本人将在毕业之前承担培训任务。在2015学年开始之前，培训计划为每两周一次，中间空闲的时间由大二或者大一熟悉C+的同学给不熟悉C+的同学进行基础的讲解。寒假时间计划每周一次。2015学年开始之后，考虑到本人要进行考研备考，培训的频率定为一个月一次，根据实际情况增加课程，所以将在寒假结束之前尽量完成多的培训任务。培训的目标是在2015年区域赛中能够获得出线的资格，并且在2016年邀请赛中能够有队伍能够拿到银牌的水平。根据各大高校的培训资料及总校给的资料汇总，将ACM的内容分成以下几章。每章的开始根据本人的认知经验，分成必考题和常考题两类。必考题为每场必出题型，大部分水题在必考题范围之内。想取得成绩必考题必须作对。常考题型有时候会最为水题，有时候会作为拉分题。培训分为基础部分和中级部分，本人实力有限，没有能力进行高级部分的讲解。高级部分留给学弟学妹们继续努力_。第一章 搜索二分和三分是很基础的一种技术。参考外校的培训教材，没有把二分和三分放入搜索一章。但是实在不知道应该放到哪里去，就在这里讲。反正都是搜索。二分最基本的应用是求单调函数跟x轴交点的问题使用的方法，有些算法也会使用二分搜索来降低复杂度。一个应用是在最长递增子序列中将DP的O（n2）算法优化为O（nlogn）三分的应用是求抛物线等在一定区间内有唯一极值的问题中，求极值的方法。栈和队列本属于数据结构的内容，考虑到这两种数据结构在搜索中应用较多，将其放入搜索一章。栈是一种先入先出的数据结构。可以用一个数组来保存栈中元素，用一个指针指向栈顶，就实现了一个栈，也可以用STL中提供的栈。队列是一种先入后出的数据结构。可以用一个数组来保存队列的元素，一个指针指向队列头，一个指针指向队列尾，每次入队列队尾向后一个，出队列队首向后一个。STL也提供了队列。递归转换是一个很常见的优化措施。有些题目可能会卡着让递归形式的算法超时，这个时候就必须改成非递归形式。非递归形式使用栈来实现。典型的例子就是二叉树的后续遍历可以改成非递归形式。深度优先搜索与广度优先搜索是两种最基本的搜索方式。很多启发式的搜索建立在这两种方式之上。本章只设计深度优先及广度优先。本章必须掌握的知识有栈和队列的定义，二叉树遍历的递归与非递归形式，深度优先搜索，广度优先搜索。深刻的理解递归搜索的原理。第二章 数据结构数据结构是必考题型之一。优先队列在之前的培训之中讲解过一次，考虑到那次培训没有讲清楚，这里重新再讲一遍。优先队列是一种特殊的队列，它能够在O（logn）的时间内找出队列中优先级最高的元素。虽然STL中提供了优先队列的模板，但是这里要求能够自己实现优先队列并查集是一种集合操作的数据结构。其基本操作是“并”和“查”。实现起来简单，速度快。并查集最直接的运用是图论中最短路算法，在这里仅讲并查集，为图论打下基础。线段树是区间操作很重要的一种数据结构，可以实现单点更新，区间更新，区间查询，复杂度大约是O（h）。在这里只讲单点更新，区间查询。区间的更新留到中级数据结构讲。字典树是字符串操作的很重要的类型，能够快速查询字符串是否在曾经出现过，是AC自动机的基础。本章必须掌握内容，优先队列的实现，并查集的实现，线段树单点更新及区间查询的实现。第三章 图论图论是一门很大的学科，涉及范围十分广泛。必考题型之一。难度大的图论会跟动态规划结合，但是这些内容在本章不涉及。图的表示方法很多，竞赛中常见的有三种，二维矩阵，邻接表，前向星。二维数组的缺点是浪费空间，邻接表如果用数组存储的话也会浪费空间，如果用容器存储会使速度变慢。前向星是一种即快又省空间的方法，但是实现起来会多几行代码。图的遍历问题在学校的数据结构课上面会有，但是仅仅是遍历，在这里要为大家展现遍历问题更有效的应用。最短路算法中，弗洛伊德算法是所有点到所有点的最短路径，迪杰斯特拉算法是点到其他所有点的最短路径，SPFA算法是中国国产的算法，理论上比迪杰斯特拉算法复杂度的常数要低一些。匈牙利算法用于二分图匹配问题，又称为小月亮算法。生成树问题一般会考最小生成树。网络流问题在本章仅仅简介，不做要求。本章必须掌握的知识点，图的三种表示方法，双连通分量的求法，拓扑排序的原理以及实现。弗洛伊德算法中用到了动态规划的知识，下一章就会讲到动态规划，所以这个算法要牢牢掌握。迪杰斯特拉算法的证明。SPFA在理论上由于迪杰斯特拉算法，所以会用SPFA代替迪杰斯特拉算法。匈牙利算法的实现，最小生成树的定义，求法。网络流的基本概念。第四章 动态规划动态规划是竞赛必考题型之一。有时候会出成送分题，有时候会出成难题。动态规划难度在于它不是一种特定的算法，而是一种思路，所以变化多端。跟任何题型都可以结合出题。动态规划最基本的是状态转移方程，将状态转移方程写出来以后，题目也就解出来了一半。有些题目可能会比较难实现，这就看平时的功力了。从最简单的0-1背包问题引入，逐渐深入。然后开始系统的讲解动态规划中常考的类型，如区间DP等。本章必须掌握的内容有动态规划方程，0-1背包问题，多重背包问题，完全背包问题，状态压缩中必须掌握位运算。各种类型的DP，简单的能够很快想出思路。第五章 数论数论是ACM中必考的题型，但是一般简单题里面不会涉及数论内容。欧几里得算法是求最大公约数的一个算法，在中学期间已经学过其过程，这里主要讲实现。扩展欧几里得算法是要求出一个x和y，是的ax+by=gcd(a,b)。因数分解是求出一个整数的所有素因子及其指数。费马小定理内容：设p是素数，a为任意整数，并且gcd(a,b)=1，则a(p-1)1(mod p)。这个定理是右面Miller-rabin算法的理论基础。欧拉函数是数论中很重要的一个函数，阐述了素数的分布规律，欧拉定理是其一个应用。素数的筛法是能够在O（n）的时间内找出n以内的所有素数，常用于大表之后解题。素数判定的第一种是试探的方法，找出一个能够整除的数，那么这个数就不是素数，试探到n就可以。Miller-rabin算法是一种在常数时间内测试出一个数是否是素数的方法，基于费马小定理。每次试探有四分之一的错误率。所以一般测试五次或者更多次。本章必须掌握的内容有欧几里得算法，扩展欧几里得算法，费马小定理的内容及证明，欧拉函数的概念，欧拉定理的内容。素数筛法，miller-rabin算法。第六章 博弈博弈是ACM中一类常考题型。主要内容不多。最根本的是取石子问题，就是两个人轮流取一些石子，按照一定的规则，第一个没有石子可拿的人为输。Nim和是两个数二进制表示的亦或后的结果。使用nim和可以方便的解决问题，证明也很简单。SG函数是表示两方输赢状态的函数也是结题的重要手段。本章必须掌握的内容，位运算，nim和，SG函数。第七章 中级数据结构树状数组是求区间和的数据结构，原理理解起来可能有一点点费劲，实现简单，但是局限性不少。RMQ是range minimum query的缩写，译