- chjshen 的博客
提高级知识点汇总
- 2023-7-3 10:47:35 @
提高级知识点汇总
以最新版的NOI大纲为依据。
一级 | 二级 | 三级 |
---|---|---|
数据结构 | 线性结构 | 【 5 】双端栈 |
【 5 】双端队列 | ||
【 5 】单调队列 | ||
【 6 】优先队列 | ||
集合与森林 | 【 6 】并查集 | |
【 6 】树的孩子兄弟表示法 | ||
特殊树 | 【 6 】二叉堆 | |
【 6 】树状数组 | ||
【 6 】线段树 | ||
【 6 】字典树(Trie树) | ||
【 7 】笛卡尔树 | ||
【 8 】平衡树:AVL 树、Treap、 Splay 等 | ||
常见图 | 【 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 】高斯消元 |