===== 一、基础算法 ===== ==== 1. 模拟 ==== ==== 2. 递归与搜索 ==== * 深度优先搜索 * 广度优先搜索 * 启发式搜索 * 迭代加深搜索 * Min-Max搜索 * Alpha-beta剪枝 * 记忆化搜索 * Meet_In_the_middle ==== 3. 排序算法 ==== * 插入排序 * 归并排序 * 快速排序 * 桶排序 * 用数据结构排序 ==== 4. 贪心算法(fyh hxm wxg) ==== * Huffman编码及Huffman树 * K叉Huffman树 * 区间覆盖问题及拓展 * 思维性贪心 * 拟阵 ==== 5. 差分思想 ==== ---- ===== 二、图论 ===== ==== 1. 图的存储 ==== * 邻接表（链式前向星） * 邻接矩阵 ==== 2. 图的路径问题(fyh hxm) ==== > [[https://vjudge.net/contest/300167|[kuangbin]最短路练习]] * Floyd算法 * BellMan-Ford算法及其优化 * Dijkstra算法 * K短路问题 * 差分约束系统 ==== 3. 图的连通性(fyh hxm) ==== > [[https://vjudge.net/contest/348263|[kuangbin带你飞]专题九 连通图]] * 并查集 > [[https://vjudge.net/contest/312459|Kuangbin专题五 并查集]] * 最小生成树 * Kruskal算法 * Prim算法 > [[https://vjudge.net/contest/348266|[kuangbin带你飞]专题八 生成树]] * Tarjan算法 * 割点和桥 * 强连通分量和双联通分量 > [[https://vjudge.net/contest/344526|[kuangbin]图的割点、桥与双连通分支]] * 拓扑排序 * 2-SAT > [[https://vjudge.net/contest/362065|[kuangbin]2-SAT题集]] ==== 4. 回路问题(fyh hxm) ==== * Euler回路 * Hamiltonian回路 ==== 5. 平面图与对偶图(fyh) ==== ==== 6. 无向图的三角形枚举 ==== ==== 7. Graph Realization Problem ==== * Graph Realization Problem * Digraph Realization Problem ==== 8. 图的匹配(wxg hxm) ==== > [[https://vjudge.net/contest/68127|[kuangbin带你飞]专题十 匹配问题]] * 二分图最大匹配及拓展（Hungarian算法） * 二分图最优匹配及拓展（KM算法） > [[https://vjudge.net/contest/360235|[kuangbin]专题39 KM匹配]] * 一般图最大匹配及拓展（带花树算法） ==== 9. 树的问题(fyh hxm wxg) ==== * 树的直径与重心 * 最近公共祖先（LCA问题） * 倍增算法 * Tarjan算法（离线） * 树链剖分 * RMQ算法 * 轻重链剖分 * 长链剖分 > [[https://vjudge.net/contest/370112|[kuangbin]树链剖分]] > > [[https://vjudge.net/contest/221398|【kuangbin带你飞】专题二十五 线段树 LCA 树链剖分]] > > [[https://vjudge.net/contest/360231|[kuangbin]专题34 RMQ练习]] * 树上差分 * 虚树 * Dfs序与欧拉序 * 仙人掌 * 圆方树 ==== 10. 网络流(wxg hxm) ==== > [[https://vjudge.net/contest/363523|[kuangbin带你飞]专题十一 网络流]] * 最大流与最小割（dinic算法） * 费用流及拓展 * 有上向界的网络流 * 网络流各种模型 * 费用流及拓展 * 有上向界的网络流 * 网络流各种模型 ---- ===== 三、动态规划 ===== ==== 1. 背包问题(fyh wxg hxm) ==== * 01背包问题 * 完全背包问题 * 多重背包 * 树上背包问题 ==== 2. 状压DP (fyh) ==== * 旅行商问题 * 子集DP * 插头DP > [[https://vjudge.net/contest/360227|[kuangbin]专题32 插头DP]] ==== 3. 区间DP (fyh wxg) ==== > [[https://vjudge.net/contest/353439|[kuangbin]永不放弃！怒整DP！(区间)]] ==== 4. 数位DP (fyh wxg) ==== > [[https://vjudge.net/contest/348268|[kuangbin]专题十五 数位DP]] > [[https://vjudge.net/contest/353440|[kuangbin]永不放弃！怒整DP！(数位)]] ==== 5. Tree DP(wxg fyh) ==== ==== 6. 概率期望DP(hxm) ==== ==== 7. 递推DP ==== ==== 8. 动态规划优化(fyh wxg) ==== * 斜率优化 > [[https://vjudge.net/contest/353438|[kuangbin]永不放弃！怒整DP！(斜率)]] > > [[https://vjudge.net/contest/100568|[kuangbin带你飞]专题二十 斜率DP]] * 决策单调性优化 * 数据结构优化 * 线段树优化DP * 单调队列优化DP * 四边形不等式优化DP ---- ===== 四、字符串 ===== ==== 1. 哈希(hxm) ==== ==== 2. Trie树 ==== * 01字典树 ==== 3. KMP算法与AC自动机(hxm wxg) ==== > [[https://vjudge.net/contest/348264|[kuangbin带你飞]专题十七 AC自动机]] * 拓展KMP算法 * 最小表示法 ==== 4. 后缀树、后缀数组与后缀自动机(hxm wxg) ==== > [[https://vjudge.net/contest/348267|[kuangbin带你飞]专题十八 后缀数组]] > [[https://vjudge.net/contest/360222|[kuangbin]专题27 后缀自动机]] ==== 5. Manacher算法、回文树算法与回文自动机(hxm wxg fyh) ==== > [[https://vjudge.net/contest/292941|[kuangbin]专题十六 KMP & 扩展KMP & Manacher]] ---- ===== 五、数据结构 ===== > [[https://vjudge.net/contest/239746|[kuangbin带你飞]专题二十四 二分 尺取 单调栈队列]] ==== 1. 栈 ==== * 单调栈 ==== 2. 队列 ==== * 单调队列 ==== 3. 堆和优先队列 ==== ==== 4. 树状数组 ==== ==== 5. 线段树 ==== * 线段树优化建边(fyh) > [[https://vjudge.net/contest/348009|[kuangbin带你飞]专题七 线段树]] ==== 6. 左偏树 ==== ==== 7. 平衡树(wxg) ==== * Splay * Treap * 替罪羊树 > [[https://vjudge.net/contest/324555|[kuangbin]伸展树(splay tree)练习]] ==== 8. 动态树（Link-Cut Tree）(wxg) ==== > [[https://vjudge.net/contest/344948|[kuangbin]专题28 动态树LCT]] ==== 9. 链表 ==== * 块状链表(fyh) ==== 10. 分块与莫队(hxm fyh) ==== > [[https://vjudge.net/contest/345459|[kuangbin] 莫队算法]] * 树上分块 ==== 11. 可持久化数据结构(wxg) ==== * 主席树 * 带修主席树 * 可持久化数组 * 可持久化并查集 * 可持久化Trie * 可持久化Treap > [[https://vjudge.net/contest/368797|[kuangbin]主席树]] > > [[https://vjudge.net/contest/360228|[kuangbin]专题33 划分树专场]] ==== 12. 树套树 ==== ==== 13. KD-Tree(wxg) ==== ---- ===== 六、数学 ===== > [[https://vjudge.net/contest/347119|[kuangbin]数学训练一]] > > [[https://vjudge.net/contest/358770|[kuangbin]数学训练二]] > > [[https://vjudge.net/contest/358771|[kuangbin]数学训练三]] > > [[https://vjudge.net/contest/358772|[kuangbin]数学训练四 数论]] > > [[https://vjudge.net/contest/323477|[kuangbin]数学训练五 数论（续）]] > > [[https://vjudge.net/contest/346751|[kuangbin带你飞]专题十四 基础数论]] ==== 1. 整除与剩余(fyh hxm) ==== * Euclid算法 * 扩展Euclid算法 * 类Euclid算法 * 中国剩余定理及拓展 * Lucas定理及拓展 * 原根 * 二次剩余 * 离散对数 * N次剩余 * 佩尔方程(hxm) ==== 2. 素数与函数(fyh wxg) ==== * 素数判定 * 素数筛法 * 欧拉函数 * 线性筛 * 反演与Mobius反演 * 杜教筛 * Min25筛 > [[https://vjudge.net/contest/360221|[kuangbin]专题24 容斥原理 Mobius 反演]] > > [[https://vjudge.net/contest/323376|[kuangbin]莫比乌斯反演]] ==== 3. 线性代数(fyh hxm) ==== * 矩阵 * 高斯消元 * 矩阵的逆 * 矩阵快速幂 * 行列式 * Matrix-Tree > [[https://vjudge.net/contest/71746|[kuangbin带你飞]专题十九 矩阵]] * 常系数多项式齐次问题 * 线性基 * BM算法 * 拉格朗日数乘法 * KKT条件 ==== 4. 多项式算法(hxm wxg) ==== [[https://vjudge.net/contest/361760|[kuangbin] 专题25 快速 Founier 变换・数论变换・FFT&NTT]] * 多项式乘法 * FFT * NTT * FWT * 多项式求逆 * 多项式快速幂（倍增FFT） * 多项式开方 * 多项式除法 ==== 5. 数值计算 ==== * 数值积分 * 高阶代数方程求根 ==== 6. 概率与期望(hxm) ==== > [[https://vjudge.net/contest/358774|[kuangbin]数学训练六 概率/期望]] > > [[https://vjudge.net/contest/76505|kuangbin带你飞专题二十一 概率&期望]] ==== 7. 组合数学与容斥原理 ==== ==== 8. 其他数学内容 ==== * 快速幂 * Catalan 数 * Fermat定理 * 第一类与第二类Stirling 数(hxm) ==== 9. 生成函数(hxm wxg) ==== > [[https://vjudge.net/contest/360236|[kuangbin]专题40 母函数]] * 指数型生成函数 * 普通型生成函数 ==== 10. 置换群论(fyh) ==== ==== 七、分治算法(wxg) ==== ==== 1. 二分算法 ==== * 整体二分 * wqs二分 ==== 2. 三分算法 ==== ==== 3. 第K大数 ==== ==== 4. 偏序问题（CDQ分治） ==== ==== 5. 点分治(fyh) ==== * 动态点分治 > [[https://vjudge.net/contest/360234|[kuangbin]专题38 树分治]] ---- ===== 八、计算几何（fyh,hxm） ===== > [[https://vjudge.net/contest/348265|[kuangbin带你飞]专题十三 基础计算几何]] > > [[https://vjudge.net/contest/360244|[KuangBin计算几何进阶]] ==== 1. 线段相交问题 ==== ==== 2. 凸多边形面积 ==== ==== 3. 最小圆覆盖 ==== ==== 4. 扫描线 ==== ==== 5. 凸包问题 ==== > [[https://vjudge.net/contest/360238|[kuangbin]计算几何之凸包问题]] ==== 6. 最近点对问题 ==== ==== 7. 圆的交与并 ==== ==== 8. 半平面交 ==== > [[https://vjudge.net/contest/360243|[kuangbin]计算几何之半平面交]] ==== 9. Simpson积分 ==== ==== 10. KD-Tree ==== ==== 11. V图 ==== ---- ===== 九、博弈论问题(wxg) ===== > [[https://vjudge.net/contest/360229|[kuangbin]专题35 博弈论（Ⅰ）]] > [[https://vjudge.net/contest/360230|[kuangbin]专题36 博弈论（Ⅱ）]] ==== 1. 基于动态规划的博弈论问题 ==== * Sg函数 ==== 2. Nim博弈问题 ==== * Sg函数 * 反Nim博弈 ==== 3. Wythoff博弈问题 ==== ==== 4. Surreal Number博弈 ==== ---- ===== 十、其他算法 ===== ==== 1. 朱-刘算法 ==== ==== 2. 无向图最小割 ==== ==== 3. 高精度 ==== ==== 4. 模拟退火 ==== ==== 5. 随机化算法 ==== ==== 6. 倍增算法 ==== ==== 7. bitset压位 ====