省选算法整理
[TOC]
基础数据结构
- 数组
- 链表、双向链表
- 队列、单调队列、优先队列、双端队列
- 栈、单调栈
中级数据结构
- 堆
- 并查集、带权并查集
- Hash表
- 自然溢出
- 双Hash
高级数据结构
- 树状数组
- 线段树、线段树合并
- 平衡树
- Treap
- splay
- 替罪羊树
- 块状数组、块状链表
- 嵌套数据结构
- 树套树
- DP套DP
- 可并堆
- 左偏树
- 配对堆
- K-D Tree、四分树
可持久化数据结构
- 可持久化线段树
- 主席树
- 可持久化平衡树
- 可持久化并查集
- 可持久化块状数组
字符串算法
- KMP
- Manacher
- Trie
- AC自动机
- 后缀数组
- 后缀树
- 后缀自动机
图论算法
- 最短路径、次短路
- Dijkstra
- Bell-man Ford
- SPFA
- Floyd
- 图的连通
- 强连通分量
- 双连通分量
- 割点、桥
- 网络流
- 最大流
- 最小割
- 费用流
- 分数规划
- 无汇无源可行流
- 二分图
- KM算法
- Hungary算法、HK算法
- 最小生成树
- prim
- krusual
- 最小树形图
- 朱刘算法
- 欧拉图
- 环套树
- 仙人掌
树相关
- 树上倍增
- 最近公共祖先
- 树链剖分
- 动态树
- Link-Cut Tree
- 树分块
- 树分治
- 点分治
- 边分治
- 虚树
- Prufer编码
- 拓扑排序
数论
- 欧几里得算法
- 扩展欧几里得算法
- 筛法
- 杜教筛
- 快速幂
- 裴蜀定理
- 欧拉函数
- 欧拉定理
- 费马小定理
- 排列组合
- Lucas定理
- 乘法逆元
- 矩阵乘法
- 数学概率与期望
- 博弈论
- SG函数
- 树上删边游戏
- 拉格朗日乘子法
- 中国剩余定理
- 线性规划
- 单纯形
- 辛普森积分
- 模线性方程组
- 莫比乌斯反演
- 莫比乌斯函数
- 容次原理
- 置换群
- FFT、NTT
- BSGS
- 扩展BSGS
动态规划
- 背包问题
- 概率DP
- 状压DP
- 区间DP
- 树形DP
- 数位DP
- 插头DP
- 斯坦纳树
- DP优化
- 单调队列优化
- 矩阵乘法优化
- 斜率优化
- 四边形不等式优化
计算几何
- 计算几何基础
- 梯形剖分
- 三角形剖分
- 旋转卡壳
- 半平面交
- pick定理
- 扫描线
搜索
- DFS、BFS
- A*、IDA*
- 迭代加深搜索
- 双向BFS
随机化
- 模拟退火
- 爬山算法
- 随机增量法
其他
- 分治
- CDQ分治
- 整体二分
- 莫队算法
- 树上莫队算法
- 待修改莫队算法
- 分块
- 高精度
- 离线
- RMQ
- ST表
- 二分法
- 二分答案
- 二分查找
- 三分法
- 贪心
- 模拟