关于CSP-J与S复习大纲（比较全

孩子们，明天就考试了，最后给你们看看J组复习的内容吧， 还有没有遗漏，求求了（ 
2.1.1 基础知识与编程环境..
2.1.2 C++程序设计.
5.数学库常用函数 
8.字符串的处理 
【2】字符数组与相关函数
【3】string 类与相关函数
10.结构体与联合体 
【3】联合体
【3】枚举
12.文件及基本读写 
【2】文本文件类型与二进制文件类型
【2】文件重定向、文件读写等操作.
13.STL 模板
【3】常用函数与算法模板
【4】常用容器
2.1.3 数据结构
1.线性结构
2.简单树
3.特殊树
【4】哈夫曼树的定义和构造、哈夫曼编码
【4】二叉搜索树的定义和构造
【4】线索二叉树
4.简单图
2.1.4 算法
1.算法概念和描述
2.入门算法
3.基础算法
【4】二分法（单调数列上二分、问题二分）
【4】倍增法（快速幂）
4.算法策略 
【3】前缀和
【4】差分
5.数值处理算法 
【4】高精度的加法和乘法
【4】高精度的减法
【4】高精度整数除以单精度整数的商和余数
6.排序算法
【3】冒泡排序
【3】选择排序
【3】插入排序
【3】计数排序.
7.搜索算法
【5】深度优先搜索（排列组合所有可能的穷举、二维数组上的深搜（优化成一维））
【5】广度优先搜索（最短路（步骤）问题）.
8.图论算法 
【4】深度优先遍历（邻接矩阵、邻接表、前向星）
【4】广度优先遍历（邻接矩阵、邻接表、前向星）
【5】泛洪算法（Flood Fill）
9.动态规划 
【4】简单一维动态规划（三个字符串 DP）
【4】简单背包类型动态规划（01、完全（方案数）、多重（二进制优化）、分组、混合、
依赖）
【5】简单区间类型动态规划（石子合并、合并石子、子序列相邻差值之和最小）.24
2.1.5 数学与其他
2.初等数学
【1】代数.
【1】几何
3.初等数论 
【3】整除、因数、倍数、指数、质（素）数、合数
【4】整数唯一分解定理（单个数分解、多个数筛法打表分解）
【3】辗转相除法
【4】素数筛法：埃氏筛法与线性筛法
4.离散与组合数学
【4】排列（枚举）
【4】组合（枚举）
【4】杨辉三角
5.其他
【2】格雷码

S组
2.2.1 基础知识与编程环境.3
1.【5】Linux 系统终端中常用的文件与目录操作命令 ..3
2.【5】Linux 系统下常见文本编辑工具的使用 ..4
3.【5】常用编译命令 g++与相关编译选项.4
4.【5】在 Linux 系统终端中运行程序，使用 time 命令查看程序用时..4
5.【5】调试工具 GDB 的使用.5
2.2.2 C++程序设计 .6
1.类 .6
【6】类的概念及简单应用.6
【6】成员函数与运算符重载.6
2.STL 模板.6
【5】容器（container）和迭代器（iterator） .6
【5】对（pair）、元祖（tuple）..6
【5】映射（map）、多重映射（multimap）..8
【5】位集合（bitset） .8
2.2.3 数据结构 .9
1.线性结构..9
【5】双端栈.9
【6】ST 表（Sparse Table）..9
2.集合与森林..9
【6】并查集（想一想带权并查集）.9
【6】树的孩子兄弟表示法.9
3.特殊树..10
【6】二叉堆.10
【6】树状数组.10
【6】线段树（注意带不带 lazy）..10
【6】字典树.12
【7】笛卡尔树（O(n)建树、具有堆性质、中序遍历是原数列）..13
【8】平衡树：AVL、Treap、Splay 等..13
4.常见图..15
【5】偶图（二分图）.15
【6】欧拉图（欧拉回路的图就是欧拉图，欧拉路的图就是半欧拉图）.15
【6】有向无环图.15
【7】连通图与强连通图.15
【7】双连通图.15
5.哈希表..15
【6】字符串哈希函数构造.15
【6】哈希冲突的常用处理方法.16
2.2.4 算法 ..17
1.复杂度分析..17
2.算法策略..17
【6】离散化.17
CSP-S 提高级
2
【7】扫描线.17
3.基础算法..17
【6】分治算法.17
4.排序算法..17
【5】归并排序.17
【5】快速排序.18
【6】堆排序.21
【5】桶排序.25
【6】基数排序.25
【5】树型排序.26
5.字符串算法..27
【6】字符串匹配：KMP 算法..27
【7】Manacher 算法.29
6.搜索算法..30
【6】搜索的剪枝优化.30
【6】记忆化搜索.30
【7】启发式搜索（f(n)总代价 = g(n)已走实际代价 + h(n)估价） ..30
【7】双向广度优先搜索.30
【7】迭代加深搜索.30
7.图论算法..30
【6】最小生成树：Prim 和 Kruskal 等算法.30
【6】单源最短路：Bellman-Ford、Dijkstra、SPFA 等算法..33
【7】单源次短路.42
【6】Floyd-Warshall 算法（传递闭包、图上倍增）..42
【6】有向无环图的拓扑排序.43
【6】欧拉道路和欧拉回路.43
【6】二分图的判定.45
【7】强连通分量（带缩点）.45
【7】割点、割边.46
【6】树的重心、直径、DFS 序与欧拉序..47
【6】树上差分、子树和与倍增.50
【6】最近公共祖先.50
8.动态规划..51
【6】多维动态规划.51
【6】树型动态规划.51
【7】状态压缩动态规划.51
【8】动态规划的常用优化.51
2.2.5 数学与其他 ..51
1.初等数学..51
2.初等数论..51
【5】同余式.51
【7】欧拉定理和欧拉函数.51
【7】费马小定理.52
【7】威尔逊定理.52
【7】裴蜀定理.52
【7】模运算意义下的逆元.52
【7】扩展欧几里得算法.52
【7】中国剩余定理.54
3.离散与组合数学..54
【6】多重集合.54
【6】等价关系与等价类.54
【6】多重集上的排列.54
【6】多重集上的组合.54
【6】错排列、圆排列.54
【6】鸽巢原理.54
【6】二项式定理.54
【7】容斥原理.54
【7】卡特兰（Catalan）数.54
4.线性代数..55
【6】向量与矩阵的概念.55
【6】向量的运算.55
【7】高斯消元法.55