2020年信息学冬令营各层次教学提纲参考模板范本.doc

1、 2020年信息学冬令营各层次教学提纲集训班专题一：线段树及其应用，主要包括：1、线段树维护扫描线2、线段树的可持久化3、线段树合并4、线段树维护DFS序5、树链剖分专题二：平衡树，主要包括：1、treap定义、建立、插入和删除等维护2、非旋转treap定义、建立、插入和删除等维护3、splay建立、插入、删除、分裂和合并等维护4、KD-tree定义建立、查询、更新等维护操作5、LCT定义、建立和维护操作专题三：动态规划优化，主要包括：1、一般优化策略2、单调队列优化3、斜率优化4、决策单调性优化专题专题四：字符串专题，主要包括：1、AC自动机概念，建立及其查询2、后缀数组的定义及其建立。3、

2、利用后缀数组求LCP专题五：网络流，主要包括：1、网络流概念2、最大流3、dinic算法4、求费用流专题六：快速傅里叶变换，主要包括：1、多项式概念2、多项式的两种表示方法系数表示和点值表示3、多项式的运算，如多项式加法、多项式乘法4、系数表示转点值表示（求值），O（n2）暴力5、点值表示转系数表示（插值），O（n2）的拉格朗日插值6、n次单位复数根7、离散傅里叶变换8、快速傅里叶变换提高班专题一：搜索优化1、 理解搜索解决问题的过程2、 能熟练编写dfs和bfs3、 搜索中学会剪枝、迭代加深，学会编写双向宽搜。专题二：树结构1、 了解树的基本概念、树的的存储、树的遍历。2、 能熟练编写树上典

3、型问题，如：求树的深度、重心、中心、直径、LCA等。专题三：常用图论算法1、 了解图的概念、图的的三种存储、图的遍历。2、 理解并能熟练编写最小生成树算法。3、 理解并能熟练编写拓扑排序专题四：DP及推导1、 理解DP解决问题的条件、过程。2、 熟练掌握（线性、背包、区间、树型）等经典动态规划问题的推导专题五：DP优化及历届dp真题选讲1、 举例说明优化状态的设计。如摆渡车2、 举例说明优化决策的选择。如摆渡车、飞扬的小鸟、最长下降子序列。3、 举例说明单调队列优化DP，如跳房子、多重背包。专题六：数学专题组合数学1、 计数原理：加法原理、乘法原理、容斥原理2、 组合数学：排列与组合等3、 概

4、率与期望普及班专题一：队列及其应用，主要包括：1.队列的基本术语及模型（队首、队尾、入队、出队）2.队列的基本操作 入队、出队、取队首、判队空、获取队列元素个数3.队列的实现（数组模拟、stl中的queue）4.宽搜基础（宽搜思想）5.队列例题选讲专题二：宽搜及其应用，主要包括：1.宽搜概念2.宽搜代码框架3.宽搜例题选讲专题三：栈与递归，主要包括：1.栈的概念2.栈的操作：入栈push、出栈pop、取栈顶元素top、判栈空empty3.栈的实现：数组模拟、STL中的stack4.栈的基本应用5.递归的概念6.递归应用 专题四：深搜用其应用，主要包括：1.深搜概念2.深搜代码框架3.深搜例题选

5、讲专题五：搜索及其应用，主要包括：1.复习宽搜、深搜概念2.比较宽搜、深搜程序框架3.结合例题比较宽搜、深搜的应用专题六：树及其应用，主要包括：1、树的概念及相关知识2、二叉树的概念及相关知识3、树的表示、存储、遍历4、例题选讲基础班专题一：一维数组及其应用1.一维数组的定义、赋值及其初始化数组的含义引例羊羊运动会一维数组的定义一维数组的元素引用和物理存储方式2.一维数组的基本操作（输入、输出、插入、删除、查找、统计）一维数组的输入与输出操作一维数组元素的插入和删除操作一维数组中的顺序查找和二分查找3.一维数组应用模拟猴子选大王 铺地毯4.一维数组应用排序基本线性排序计数排序、桶排序常见的排序

6、选择排序、冒泡排序、插入排序排序算法的应用明明的随机数、近似排序专题二：二维数组1.二维数组的定义、赋值及其初始化2.二维数组的存储及应用成绩统计、杨辉三角形、扫雷游戏、马鞍数、方阵的旋转等3.数字方阵：拐角阵、螺旋方阵、回形方阵等专题三：字符串1.字符类型2.字符数组的定义、输入、输出、初始化3.C+中字符串的定义、输入、输出与赋值4.string类的主要函数 Size():求字符串长度 Getline(cin,s):读入一整行 Substr(开始位置i,子串长度):取字符串的子串 Insert(插入位置i,插入字符串s):插入 Erase(开始位置i,删除字符长度len):删除 Repla

7、ce(开始位置i,长度len,待替换字符串ss):替换5.字符串的应用， 统计单词个数、找第一个只出现一次的字符、选择你喜爱的水果 、车牌统计、单词替换、ISBN号码专题四：函数与结构体1. 函数及其应用函数的概念、定义及其调用参数的传递变量的作用域函数的应用，如统计素数、计算组合数等。2. 结构体及其应用结构体的概念 结构体的定义。 结构体的输入、输出、赋值。 结构体的应用: 成绩排名等 结构体的扩展及应用：上网计费、结构体排序专题五：递归1.递归的定义2.递归过程分析（系统栈）3.递归算法的设计，递归式及其递归结束条件4.递归算法的应用求阶乘、斐波那契数列、走台阶、求最大公约数、二分查找等。5.递归与循环的关5 / 5