NOI 大纲 提高级

提高级

计算机基础知识与编程环境

1. [5] Linux系统终端中常用的文件与目录操作命令
2. [5] Linux系统下常见文本编辑工具的使用
3. [5] g++、gcc 等编译器与相关见编译选项
4. [5] 在 Linux 系统终端中运行程序，使用time命令查看程序用时
5. [5] 调试工具GDB的使用

C++ 程序设计

1. 类(class)
   [6] 类的概念及简单应用
   [6] 成员函数和运算符重载
2. STL 模板
   [5] 容器(container)和迭代器(iterator)
   [5]对 (pair) 、元组 (tuple)
   [5] 集合 (set)、多重集合(multiset)
   [5] 双端队列(deque)、优先队列(priority_queue)
   [5] 映射(map)，多重映射(multimap)
   [5] 算法模板库中的常用函数

数据结构

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] 哈希冲突的常用处理方法

算法

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] 单源最短路：Dijkstra、bellman_ford、SPFA 等算法
   [7] 单源次短路
   [6] Floyd-Warshall 算法
   [6] 有向无环图的拓扑排序算
   [6] 欧拉道路和欧拉回路
   [6] 二分图的判定
   [7] 强连通分量
   [7] 割点、割边
   [6] 树的重心、直径、DFS序与欧拉序
   [6] 树上差分、子树和与倍增
   [6] 最近公共祖先
8. 动态规划
   [6] 树型动态规划
   [7] 状态压缩动态规划
   [8] 动态规划的常用优化

数学

1. 初等数学
   [5] 代数(高中部分)
   [6] 几何(高中部分)
2. 初等数论
   [5] 同余式
   [7] 欧拉定理和欧拉函数
   [7] 费马小定理
   [7] 威尔逊定理
   [7] 裴蜀定理
   [7] 模运算意义下的逆元
   [7] 扩展欧几里得算法
   [7] 中国剩余定理
3. 离散与组合数学
   [6] 多重集合
   [6] 等价类
   [6] 多重集上的排列
   [7] 多重集上的组合
   [6] 错排列、圆排列
   [6] 鸽巢原理
   [6] 二项式定理
   [7] 容斥原理
   [7] 卡特兰(Catalan)数
   4.线性代数
   [5] 向量与矩阵概念
   [6] 向量的运算
   [6] 矩阵的初等变换
   [6] 矩阵的运算:加法、减法、乘法与转置
   [6] 特殊矩阵的概念:单位阵、三角阵、对称阵和稀疏矩阵
   [7] 高斯消元法