CPS-S 大纲
2.2.1 基础知识与编程环境
-
【 5 】Linux 系统终端中常用的文件与目录操 作命令
-
【 5 】Linux 系统下常见文本编辑工具的使用
-
【 5 】g++、gcc 等编译器与相关编译选项
-
【 5 】在 Linux 系统终端中运行程序，使用 time 命令查看程序用时
-
【 5 】调试工具 GDB 的使用
2.2.2 C++ 程序设计 2
- 类（class）
-
【 6 】类的概念及简单应用
-
【 6 】成员函数和运算符重载
- STL 模板
-
【 5 】容器（container）和迭代器（iterator）
-
【 5 】对（pair）、元组（tuple）
-
【 5 】集合（set）、多重集合（multiset）
-
【 5 】双端队列（deque）、优先队列（priority_ queue）
-
【 5 】映射（map）、多重映射（multimap）
-
【 5 】算法模板库中的常用函数
2.2.3 数据结构
- 线性结构
- 【 5 】双端栈
- 【 5 】双端队列
- 【 5 】单调队列
- 【 6 】优先队列
- 【 6 】ST 表（Sparse Table）
- 集合与森林
-
【 6 】并查集
-
【 6 】树的孩子兄弟表示法
- 特殊树
-
【 6 】二叉堆
-
【 6 】树状数组
-
【 6 】线段树
-
【 6 】字典树（Trie 树）
-
【 7 】笛卡尔树
-
【 8 】平衡树：AVL、treap、splay 等
- 常见图
-
【 5 】稀疏图
-
【 6 】偶图（二分图）
-
【 6 】欧拉图
-
【 6 】有向无环图
-
【 7 】连通图与强连通图
-
【 7 】双连通图
- 哈希表
-
【 5 】数值哈希函数构造
-
【 6 】字符串哈希函数构造
-
【 6 】哈希冲突的常用处理方法
2.2.4 算法
- 复杂度分析
-
【 6 】时间复杂度分析
-
【 6 】空间复杂度分析
- 算法策略
- 【 6 】离散化
- 基础算法
- 【 6 】分治算法
- 排序算法
-
【 5 】归并排序
-
【 5 】快速排序
-
【 6 】堆排序
-
【 5 】桶排序
-
【 6 】基数排序
- 字符串相关算法
- 【 5 】字符串匹配：KMP 算法
- 搜索算法
-
【 6 】搜索的剪枝优化
-
【 6 】记忆化搜索
-
【 7 】启发式搜索
-
【 7 】双向广度优先搜索
-
【 7 】迭代加深搜索
- 图论算法
-
【 6 】最小生成树：Prim 和 Kruskal 等算法
-
【 7 】次小生成树
-
【 6 】单源最短路：Bellman-Ford、Dijkstra、
SPFA 等算法
-
【 7 】单源次短路
-
【 6 】Floyd-Warshall 算法
-
【 6 】有向无环图的拓扑排序
-
【 6 】欧拉道路和欧拉回路
-
【 6 】二分图的判定
-
【 7 】强连通分量
-
【 7 】割点、割边
-
【 6 】树的重心、直径、DFS 序与欧拉序
-
【 6 】树上差分、子树和与倍增
-
【 6 】最近公共祖先
- 动态规划
-
【 6 】树型动态规划
-
【 7 】状态压缩动态规划
-
【 8 】动态规划的常用优化
2.2.5 数学与其他
- 初等数学
-
【 5 】代数（高中部分）
-
【 6 】几何（高中部分）
- 初等数论
-
【 5 】同余式
-
【 7 】欧拉定理和欧拉函数
-
【 7 】费马小定理
-
【 7 】威尔逊定理
-
【 7 】裴蜀定理
-
【 7 】模运算意义下的逆元
-
【 7 】扩展欧几里得算法
-
【 7 】中国剩余定理
- 离散与组合数学
-
【 6 】多重集合
-
【 6 】等价类
-
【 6 】多重集上的排列
-
【 6 】多重集上的组合
-
【 6 】错排列、圆排列
-
【 6 】鸽巢原理
-
【 6 】二项式定理
-
【 7 】容斥原理
-
【 7 】卡特兰（Catalan）数
- 线性代数
-
【 5 】向量与矩阵概念
-
【 6 】向量的运算
-
【 6 】矩阵的初等变换
-
【 6 】矩阵的运算：加法、减法、乘法与转置
-
【 6 】特殊矩阵的概念：单位阵、三角阵、 对称阵和稀疏矩阵
-
【 7 】高斯消元法