noip知识点

#### 自己总结的noip知识点，希望在noip之前全打勾 ------------ ###### 加油！qwq！ ------------ ``` 高精度 　　1.加法✔ 　　2.减法✔ 　　3.乘法（应该只会有高精乘单精) 　　4.高精度除单精 (后面c,d考的可能性较小，应该只考a,b) 排序算法 　　1.选择排序✔ 　　2.插入排序✔ 　　3.hash排序✔ 　　4.归并排序(单纯的排序可能用不到，有快排就行了，但是归并排序的思想很重要) 　　5.堆排序 　　6.快排✔ 数论 　　1.欧几里德算法(用辗转相除法求最大公约数) 　　2.扩展欧几里德算法、求解同余方程、逆元：ax+by=c 的正整数 　　3.素数  O(sqrt(n)) ✔ 　　4.筛法求素数（埃氏筛法） 　　5.快速乘方，快速幂：位运算+同余+高精 ✔ 　　6.矩阵 　　7.组合数学 　　8.莫比乌斯反演 　　9.中国剩余定理 　　10.博弈论相关 　　11.容斥原理 树论 　　1.二叉搜索树 　　2.优先队列（C++中priority_queue，相当于手动维护的小（大）根堆的数据结构优化）✔ 　　3.线段树、✔ 　　4.平衡树一种(建议学习SBT) 　　5.树上倍增（LCA）✔ 　　　　①离线 　　　　②在线 　　6.树的直径、树的重心 　　7.树链剖分 　　8.树套树 　　9.圆方树 　　10.主席树 　　11.树状数组✔ 　　12.线段树合并 　　13.RMQ,st算法✔ 图论 　　1.拓扑排序✔ 　　2.割顶，割边(桥) O(n) 　　3.强连通分支  O(n) 　　4.有向无回路图的最长路径 　　5.欧拉回路 　　6.最小生成树 　　　　① Prime  O(N2) 　　　　② Kruskal  O(M2) ✔ 　　7.次小生成树 {简单的删除最大边是不对的} 　　8.最短路径 　　　　① Dijkstra✔ 　　　　② Bellman-ford 　　　　③ spfa 　　　　④ flyod✔ 　　　　单源点最短路径算法推荐使用spfa，Dijkstra不能有负边不能有回路，所以用spfa更保险 　　9.二分图染色,二分图匹配 　　10.并查集✔ 　　11.仙人掌算法 　　12.网络流 　　13.虚树 　　14.点分治，边分治，动态点分治 计算几何  　　1.判断两条线段是否相交 　　2.凸包算法  O(n) 动态规划 　　1.背包DP✔(???) 　　2.树形DP 　　3.记忆化搜索,递推 　　4.区间DP 　　5.序列DP 　　6.插头DP 　　7.动态DP 　　8.树形DP 　　9.DP优化（不涉及斜率优化、四边形不等式等等） 　　10.基环树DP 　　11.仙人掌DP 　　11.trie图DP 　　12.期望DP 　　13.状压DP 　　13.数位DP 搜索 　　1.暴搜（dfs、bfs）✔(???) 　　2.搜索的剪枝 ✔(???) 　　3.记忆化搜索 　　4.启发式搜索（A*） 　　5.迭代加深搜索、* IDA* 　　6.随机化搜索 　　7.模拟退火✔(???) 字符串匹配算法 　　1.蛮力法✔ 　　2.KMP✔ 字符串 　　1.字符串哈希 　　2.AC自动机 　　3.后缀自动机 　　4.回文自动机 　　5.manacher✔ 　　6.后缀数组 　　7.trie字典树✔ 其他算法 　　1.枚举✔ 　　2.贪心✔ 　　3.分治✔ 　　4.二分✔ 　　5.模拟✔ 　　6.构造 　　7.三分法 　　8.打表✔ 　　9.分块✔ 　　9.单调队列✔ ```