Noi知识点总提纲

1、0. 算法的时空分析 K0.1 时间分析 K0.2 空间分析 K0.3 时空分配K1. 基础算法1.1 枚举K1.2 模拟K1.3 递推K1.4 贪心K1.5 递归K1.6 分治K2. 排序算法2.1 冒泡排序K2.2 选择排序K2.3 桶排序K2.4 插入排序K2.5 归并排序K2.6 快速排序K2.7 堆排序K2.8 二叉排序树K3. 查找算法3.1 顺序查找K3.2 二分查找K3.3 二分答案K4. 搜索算法4.1 BFS和DFSK4.2 简单剪枝K4.3 记忆化搜索K5. 动态规划5.1 动态规划初步K5.2 背包问题K5.3 最大(小)代价子母树K6. 排列组合6.1 基本概念K6.

2、2 二项式定理K6.3 康托展开K6.4 袋与球问题K7. 数论7.1 素数判断K7.2 最大公约数K7.3 扩展欧几里德K7.4 不定方程K7.5 几类数列K7.6 数的进制K8. 线性表8.1 数组和向量K8.2 堆栈K8.3 队列K8.4 字符串K9. 图9.1 图的遍历和拓扑排序 9.1.1 图的遍历K 9.1.2 拓扑排序O9.2 最短路 9.2.1 Floyd算法K 9.2.2 Dijstra算法K 9.2.3 Bellman-Ford算法(效率太低) 9.2.4 SPFA算法K9.3 生成树 9.3.1 Prim算法K 9.3.2 Kruskal算法K9.4 圈和块 9.4.1

3、最小环O 9.4.2 负权环O 9.4.3 连通块O /noip10. 树10.1 树的遍历K10.2 树上距离问题 10.2.1 节点到根的距离O(DFS) 10.2.2 最近公共祖先O(DFS) 10.2.3 节点间的距离O(DFS) 10.2.4 树的直径O10.3 哈夫曼树K10.4 二叉堆K10.5 树形动态规划K10.6 二叉排序树K10.7 并查集K11. HASH K11.1 ELFhash11.2 SDBM11.3 BKDR11.4 RK12. 数论 12.1 矩阵乘法O12.2 高斯消元 (L)12.3 异或方程组(L)13. 动态规划13.1 多维状态动态规划13.2 状

4、态压缩动态规划 13.2.1 递推K 13.2.2 基于连通性13.3 动态规划优化 13.3.1 降低维度 K 13.3.2 优先队列 K 13.3.3 单调队列K 13.3.4 矩阵加速O 13.3.5 斜率优化(凸包就是这样！) 13.3.6 四边形不等式（懒得鸟他）14. 二分图14.1 最大匹配 14.1.1 匈牙利算法O 14.1.2 最大流算法O 14.1.3 覆盖集和独立集 14.1.4 非二分图最大匹配14.2 带权二分图匹配 14.2.1 KM算法 14.2.2 费用流算法15. 网络流15.1 网络流初步15.2 最大流 15.2.1 Dinic算法 15.2.2 Sap

5、算法 15.2.3 有上下界的最大流15.3 最小割 15.3.1 最小割 15.3.2 平面图最小割 15.3.3 闭合图 15.3.4 最小点权覆盖集与最大点权独立集 15.3.5 0/1分数规划 15.3.6 最大密度子图15.4 费用流 15.4.1 最短路增广费用流 15.4.2 zkw-费用流 15.4.3 最小费用可行流16. 图和树16.1 路径问题K 16.1.1 K短路 16.1.2 差分约束系统16.2 生成树 16.2.1 生成树的另类算法 16.2.2 次小生成树 16.2.3 特殊生成树16.3 2-SAT16.4 线段树O16.5 平衡树 16.5.1 Treap 16.5.2 Splay16.6 LCA与RMQ16.7 树状数组17. 字符串K17.1 TrieK17.2 KMP及扩展K17.3 后缀数组K18. 选学内容18.1 启发式搜索18.2 跳舞链18.3 随机调整与随机贪