2.2.1 基础知识与编程环境

1. 【 5 】Linux 系统终端中常用的文件与目录操作命令

2. 【 5 】Linux 系统下常见文本编辑工具的使用

3. 【 5 】g++、gcc 等编译器与相关编译选项

4. 【 5 】在 Linux 系统终端中运行程序，使用 time 命令查看程序用时

5. 【 5 】调试工具 GDB 的使用

2.2.2 C++ 程序设计 2

1. 类（class）

· 【 6 】类的概念及简单应用

· 【 6 】成员函数和运算符重载

2. STL 模板

· 【 5 】容器（container）和迭代器（iterator）

· 【 5 】对（pair）、元组（tuple）

· 【 5 】集合（set）、多重集合（multiset）

· 【 5 】双端队列（deque）、优先队列（priority_ queue）

· 【 5 】映射（map）、多重映射（multimap）

· 【 5 】算法模板库中的常用函数

2.2.3 数据结构

1. 线性结构

· 【 5 】双端栈

· 【 5 】双端队列

· 【 5 】单调队列

· 【 6 】优先队列

· 【 6 】ST 表（Sparse Table）

2. 集合与森林

· 【 6 】并查集

· 【 6 】树的孩子兄弟表示法

3. 特殊树

· 【 6 】二叉堆

· 【 6 】树状数组

· 【 6 】线段树

· 【 6 】字典树（Trie 树）

· 【 7 】笛卡尔树

· 【 8 】平衡树：AVL、treap、splay 等

4. 常见图

· 【 5 】稀疏图

· 【 6 】偶图（二分图）

· 【 6 】欧拉图

· 【 6 】有向无环图

· 【 7 】连通图与强连通图

· 【 7 】双连通图

5. 哈希表

· 【 5 】数值哈希函数构造

· 【 6 】字符串哈希函数构造

· 【 6 】哈希冲突的常用处理方法

2.2.4 算法

1. 复杂度分析

· 【 6 】时间复杂度分析

· 【 6 】空间复杂度分析

2. 算法策略

· 【 6 】离散化

3. 基础算法

· 【 6 】分治算法

4. 排序算法

· 【 5 】归并排序

· 【 5 】快速排序

· 【 6 】堆排序

· 【 5 】桶排序

· 【 6 】基数排序

5. 字符串相关算法

· 【 5 】字符串匹配：KMP 算法

6. 搜索算法

· 【 6 】搜索的剪枝优化

· 【 6 】记忆化搜索

· 【 7 】启发式搜索

· 【 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 】最近公共祖先

8. 动态规划

· 【 6 】树型动态规划

· 【 7 】状态压缩动态规划

· 【 8 】动态规划的常用优化

2.2.5 数学与其他

1. 初等数学

· 【 5 】代数（高中部分）

· 【 6 】几何（高中部分）

2. 初等数论

· 【 5 】同余式

· 【 7 】欧拉定理和欧拉函数

· 【 7 】费马小定理

· 【 7 】威尔逊定理

· 【 7 】裴蜀定理

· 【 7 】模运算意义下的逆元

· 【 7 】扩展欧几里得算法

· 【 7 】中国剩余定理

3. 离散与组合数学

· 【 6 】多重集合

· 【 6 】等价类

· 【 6 】多重集上的排列

· 【 6 】多重集上的组合

· 【 6 】错排列、圆排列

· 【 6 】鸽巢原理

· 【 6 】二项式定理

· 【 7 】容斥原理

· 【 7 】卡特兰（Catalan）数

4. 线性代数

· 【 5 】向量与矩阵的概念

· 【 6 】向量的运算

· 【 6 】矩阵的初等变换

· 【 6 】矩阵的运算：加法、减法、乘法与转置

· 【 6 】特殊矩阵的概念：单位阵、三角阵、 对称阵和稀疏矩阵

· 【 7 】高斯消元法