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