目录

团队技能树

图论

知识点 Pantw Withinlover Gary
最短路 Dijkstra
SPFA
线段树优化建图
生成树 Prim
Kruskal
回路 欧拉回路
哈密顿回路
平面图 欧拉定理
平面图判定
连通分量 有向图 强连通分量
无向图 割点和桥
点双连通分量
边双连通分量
路径问题 K 短路
差分约束系统
生成树 次小生成树
最优比率生成树
拓扑排序
2-SAT(注意复杂度)
稳定婚姻系统
环空间
三元环计数
LGV Lemma
最小点基

网络流

知识点 Pantw Withinlover Gary
定理 最大匹配与最小边覆盖
最大独立集与最小点覆盖
最大流最小割
König 定理:二分图最大匹配与最小点覆盖
二分图最小割与最小点权覆盖
最大流 Dinic(注意特殊图复杂度)
有上下界的最大流
最小割 最小割
平面图最小割
最小点权覆盖集与最大点权独立集
最大权闭合子图
0/1 分数规划
全局最小割
费用流 SPFA 费用流 / zkw 费用流
最小费用可行流
消圈定理
LP 对偶费用流
二分图 最大匹配 匈牙利算法(注意复杂度)
最大流算法
覆盖集和独立集
DAG 的链与反链
一般图最大匹配
带权二分图匹配 KM 算法(注意复杂度)
霍尔定理

字符串

知识点 Pantw Withinlover Gary
Trie
AC自动机
KMP KMP
扩展 KMP
后缀结构 后缀数组
SAM
广义 SAM
后缀树
SA-IS
回文串 Manacher
PAM
Border 理论 Border Series 基础 Border 理论
基本子串字典
Palindrome Series
有限状态自动机
Huffman 编码
字符串哈希
Lyndon 分解
最小表示法

FFT 与多项式

知识点 Pantw Withinlover Gary
FFT FFT
NTT
任意模数 FFT
多项式 多项式乘法
多项式除法 / 取余
多项式求逆
多项式一顿操作
常系数齐次线性递推 常系数齐次线性递推优化矩阵快速幂
BM 求最短递推式
扩展 BM 求最短递推式
位运算卷积 子集卷积
FWT
生成函数 普通生成函数
指数型生成函数
拉格朗日插值
分治 FFT

数论

知识点 Pantw Withinlover Gary
素性判断 Miller-Rabin(注意效率)
Pollard-Rho(注意效率)
离散变换 同余方程 大步小步
扩展大步小步
中国剩余定理
扩展中国剩余定理
二次剩余
三次剩余
N 次剩余
任意模数 N 次剩余
欧几里得 扩展欧几里德
二元一次不定方程求解
类欧几里得
置换群 Burnside 引理
Pólya 定理
反演 Mobius 反演
二项式反演
Stirling 反演
Lagrange 反演
筛法 线筛积性函数
杜教筛
洲阁筛
min_25 筛
矩阵 高斯消元 异或方程组
求行列式
辗转相除法高斯消元
特征值与特征方程
矩阵的逆
排列组合 Stirling 数
Lucas 定理
扩展 Lucas 定理
容斥原理 递推容斥系数计算
min-max 容斥
Fibonacci 数列 相关性质
皮萨诺周期
博弈论 Nim 游戏 各种 Nim 游戏有待补充
SG 函数 / SG 定理
纳什均衡
威佐夫博弈
不平等博弈 / Surreal Number
杂项 威尔逊定理
鸽笼原理
Ramsey 定理
棋盘多项式
Catalan 数

数据结构

知识点 Pantw Withinlover Gary
点分治 点分治
动态点分治
平衡树 Treap
Splay
替罪羊树
动态树 树链剖分
LCT
树分块 基于 DFS 序列
真正的树上分块
生成树计数 基尔霍夫定理(矩阵树定理)
Best 定理
内向环
Huffman 树
笛卡尔树
左偏树 / 可并堆
虚树
基环树
斯坦纳树
树套树
树上启发式合并(DSU on tree)
Prufer 序列
K-D Tree
线段树 李超线段树
区间 min-max 操作
仙人掌 仙人掌基础
动态仙人掌
可持久化结构 可持久化权值线段树(主席树)
可持久化并查集
可持久化平衡树
可持久化 Trie
线性基 线性基求并
线性基求交
块状链表

动态规划

知识点 Pantw Withinlover Gary
数位 DP
插头 DP
背包 DP 可逆背包
子树合并类背包(及其时间复杂度证明)
单调性 DP 优化 单调栈优化(注意正确性)
分治 DP(注意时间复杂度)
斜率优化
四边形不等式

计算几何

知识点 Pantw Withinlover Gary
半平面交
多边形
多面体
凸包的分治法
旋转卡壳
增量法
随机增量
平面解析几何及其应用
向量
点积及其应用
叉积及其应用
凸多边形的交
离散化与扫描
圆反演
三维圆交
动态凸包

杂项

知识点 Pantw Withinlover Gary
二分算法 整体二分
带权二分
0/1 分数规划
分治算法 线段树分治
CDQ 分治
莫队算法 普通莫队
带修改莫队
树上莫队 基于 DFS 序的树上莫队
真正的树上莫队
二进制集合枚举 子集枚举
超集枚举
位运算 bitset 及其应用
位运算匹配字符串
自适应 Simpson 积分
拟阵
随机算法(爬山法 / 模拟退火 / 遗传算法)
pb_ds