Noi知识点总提纲

《Noi知识点总提纲》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、0.算法的时空分析K  0.1时间分析K  0.2空间分析K  0.3时空分配K  1.基础算法  1.1枚举K  1.2模拟K  1.3递推K  1.4贪心K  1.5递归K  1.6分治K  2.排序算法  2.1冒泡排序K  2.2选择排序K  2.3桶排序K  2.4插入排序K  2.5归并排序K  2.6快速排序K  2.7堆排序K  2.8二叉排序树K  3.查找算法  3.1顺序查找K  3.2二分查找K  3.3二分答案K  4.搜索算法  4.1BFS和DFSK  4.2简单剪枝K  4.3记忆化搜索K  5.动态规划

2、  5.1动态规划初步K  5.2背包问题K  5.3最大(小)代价子母树K  6.排列组合  6.1基本概念K  6.2二项式定理K  6.3康托展开K  6.4袋与球问题K  7.数论  7.1素数判断K  7.2最大公约数K  7.3扩展欧几里德K  7.4不定方程K  7.5几类数列K  7.6数的进制K  8.线性表  8.1数组和向量K  8.2堆栈K  8.3队列K  8.4字符串K  9.图  9.1图的遍历和拓扑排序  9.1.1图的遍历K  9.1.2拓扑排序O  9.2最短路  9.2.1Floyd算法K  9.2

3、.2Dijstra算法K  9.2.3Bellman-Ford算法(效率太低)  9.2.4SPFA算法K  9.3生成树  9.3.1Prim算法K  9.3.2Kruskal算法K  9.4圈和块  9.4.1最小环O  9.4.2负权环O  9.4.3连通块O/noip10.树  10.1树的遍历K  10.2树上距离问题  10.2.1节点到根的距离O(DFS)  10.2.2最近公共祖先O(DFS)  10.2.3节点间的距离O(DFS)  10.2.4树的直径O  10.3哈夫曼树K  10.4二叉堆K  10.5树形动态规

4、划K  10.6二叉排序树K  10.7并查集K11.HASHK  11.1ELFhash  11.2SDBM  11.3BKDR  11.4RK12.数论  12.1矩阵乘法O  12.2高斯消元(L)  12.3异或方程组(L)  13.动态规划  13.1多维状态动态规划  13.2状态压缩动态规划  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.

5、6四边形不等式（懒得鸟他）14.二分图  14.1最大匹配  14.1.1匈牙利算法O  14.1.2最大流算法O  14.1.3覆盖集和独立集  14.1.4非二分图最大匹配  14.2带权二分图匹配  14.2.1KM算法  14.2.2费用流算法15.网络流  15.1网络流初步  15.2最大流  15.2.1Dinic算法  15.2.2Sap算法  15.2.3有上下界的最大流  15.3最小割  15.3.1最小割  15.3.2平面图最小割  15.3.3闭合图  15.3.4最小点权覆盖集与最大点权独立集  15.3.

6、50/1分数规划  15.3.6最大密度子图  15.4费用流  15.4.1最短路增广费用流  15.4.2zkw-费用流  15.4.3最小费用可行流16.图和树  16.1路径问题K  16.1.1K短路  16.1.2差分约束系统  16.2生成树  16.2.1生成树的另类算法  16.2.2次小生成树  16.2.3特殊生成树  16.32-SAT  16.4线段树O  16.5平衡树  16.5.1Treap  16.5.2Splay  16.6LCA与RMQ  16.7树状数组  17.字符串K  17.1TrieK  

7、17.2KMP及扩展K  17.3后缀数组K  18.选学内容  18.1启发式搜索  18.2跳舞链  18.3随机调整与随机贪心  18.4爬山法与模拟退火  18.5博弈论  18.6动态树  18.6.1树链剖分  18.6.2Link-CutTree  18.7计算几何  18.8DFT和FFT