提高级知识点汇总

以最新版的NOI大纲为依据。

一级 二级 三级
数据结构 线性结构 【 5 】双端栈
【 5 】双端队列
【 5 】单调队列
【 6 】优先队列
集合与森林 【 6 】并查集
【 6 】树的孩子兄弟表示法
特殊树 【 6 】二叉堆
【 6 】树状数组
【 6 】线段树
【 6 】字典树(Trie树)
【 7 】笛卡尔树
【 8 】平衡树AVL 树TreapSplay
常见图 【 5 】稀疏图
【 6 】偶图(二分图)
【 6 】欧拉图
【 6 】有向无环图
【 7 】连通图与强连通图
【 7 】双连通图
哈希表 【 5 】数值哈希函数构造
【 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 】动态规划的常用优化:单调队列/单调栈优化
【 8 】动态规划的常用优化:斜率优化
【 8 】动态规划的常用优化:四边形不等式优化
【 8 】动态规划的常用优化:状态设计优化
数学 初等数论 【 5 】同余式
【 7 】欧拉定理欧拉函数
【 7 】费马小定理
【 7 】威尔逊定理
【 7 】裴蜀定理
【 7 】模运算意义下的逆元
【 7 】扩展欧几里得算法
【 7 】中国剩余定理
离散与组合数学 【 6 】多重集合
【 6 】等价类
【 6 】多重集上的排列
【 6 】多重集上的组合
【 6 】错位排列圆排列
【 6 】鸽巢原理
【 6 】 二项式定理
【 7 】容斥原理
【 7 】卡特兰(Catalan)数
线性代数 【 5 】向量矩阵的概念
【 6 】向量的运算
【 6 】矩阵的初等变换
【 6 】矩阵的运算:加法、减法、乘法与转置
【 6 】特殊矩阵的概念:单位阵、三角阵、 对称阵和稀疏矩阵
【 7 】高斯消元