OI知识点|NOIP考点|省选考点|教程与学习笔记合集

点亮技能树行动——

本篇blog按照分类将网上写的OI知识点归纳了一下，然后会附上蒟蒻我的学习笔记或者是我认为写的不错的专题博客qwqwqwq（好吧，其实已经咕咕咕了。。。）

基础算法
- 贪心
- 枚举
- 分治
- 倍增
- 构造
- 高精
- 模拟
图论
- 图
  - 最短路，次短路
  - k短路
  - 差分约束
  - 最小生成树
  - 拓扑排序
  - 欧拉图
  - 二分图染色，二分图匹配
  - 最大团，最大独立集
  - tarjan找scc、桥、割点，缩点
  - 网络流
    - 最大流,最小割,费用流
    - 有上下界的网络流
  - 分数规划
  - 2-SAT
- 树
  - LCA 最近公共祖先
  - 树的直径
  - 树的重心
  - dfs序
  - 树链剖分
  - 长链剖分
  - kruskal重构树
  - 树的分治算法
    - 点分治
    - 边分治
  - 基环树
  - 虚树
  - LCT
数论
- gcd、lcm
- 筛素数
- exgcd
- 求解同余方程
- 逆元
- 快速幂
- 斐波那契数
- 卡特兰数
- 组合数学这里是我的一些小整理
  - lucas定理
- 矩阵
- 矩阵树定理
- 概率和期望
- 博弈论
- 拉格朗日乘子法
- 中国剩余定理，excrt
- 辛普森积分
- 容斥
- 莫比乌斯反演
- 杜教筛
- 置换群
- 快速傅里叶变换 attack 大佬'blog 胡小兔大佬's blog
- BSGS,扩展BSGS
计算几何
- 计算几何基础
- 更详细的教程
- 三维计算几何初步
- 凸包
- 梯形剖分，三角形剖分
- 旋转卡壳
- 半平面交
- pick定理
- 扫描线
数据结构
- 链表
- 队列
  - 单调队列
  - 双向队列
- 栈
  - 单调栈
- 堆
- 并查集
  - 带权并查集
- st表
- hash表
- 线段树
  - 线段树合并
- 树状数组
- 平衡树
  - Treap
  - fhq treap
  - Splay
- 块状数组，块状链表
- 分块
- 树套树
- 可并堆
  - 左偏树
  - 配对堆
- KDtree，四分树
- 可持久化数据结构
  - 主席树
  - 可持久化数组
- 李超线段树
动态规划
- 背包DP
- 树形DP
- 记忆化搜索
- 区间DP
- 状压DP
- 数位DP
- 环+外向树上的DP
- 插头DP
- DP优化
  - 状态数量的缩减技巧
  - 矩阵优化
  - 优先队列优化
  - 斜率优化
  - 四边形不等式优化
- 斯坦纳树
- DP套DP
多项式
- FFT
- NTT
- FWT
搜索
- 暴搜（dfs、bfs）
- 搜索的剪枝
- 启发式搜索（A*）
- 迭代加深搜索
- 双向广搜
字符串
- KMP
- AC自动机
- 后缀数组1 后缀数组2
- 后缀树
- 后缀自动机
- 字典树 Trie
- manacher
- 回文自动机
其他
- 二分，三分
- meet in the middle
- 莫队
- 模拟退火
- 爬山
- 随机增量
- 悬线法
- CDQ分治
- 弦图和区间图
- 朱刘算法
- STL
  - set
  - map
  - vector
  - bitset
  - priority_queue