2.2.2 C++程序设计

1.类(class)

• 【6】类的概念及简单应用
• 【6】成员函数和运算符重载

2.STL模板

• 【5】容器(container)和迭代器(iterator)。
• 【5】对(pair)、元组(tuple)
• 【5】集合(set)、多重集合(multiset)
• 【5】双端队列(deque)、优先队列(priority_queue)
• 【5】映射(map)、多重映射(multimap)
• 【5】位集合(bitset)
• 【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】离散化
• 【7】扫描线

3.基础算法

• 【6】分治算法

4.排序算法

• 【5】归并排序
• 【5】快速排序
• 【6】堆排序
• 【5】桶排序
• 【6】基数排序

5.字符串算法

• 【6】字符串匹配:KMP算法
• 【7】Manacher算法

6.搜索算法

• 【6】搜索的剪枝优化
• 【6】记忆化搜索
• 【7】启发式搜索
• 【7】双向广度优先搜索
• 【7】迭代加深搜索

7.图论算法

• 【6】最小生成树:Prim和Kruskal等算法
• 【6】单源最短路:Bellman-Ford、Dijkstra、SPFA等算法
• 【7】单源次短路
• 【6】Floyd-Warshall算法
• 【6】有向无环图的拓扑排序
• 【6】欧拉道路和欧拉回路
• 【6】二分图的判定
• 【7】强连通分量
• 【7】割点、割边
• 【6】树的重心、直径、DFS序与欧拉序
• 【6】树上差分、子树和与倍增
• 【6】最近公共祖先

8.动态规划

• 【6】多维动态规划
• 【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】高斯消元法

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com