====== 知识点目录 ====== ===== 数据结构 ===== ==== 基础数据结构 ==== * ☐ 数组 * ☐ 散列表 * ☐ 链表 * ☐ 双向链表 * ☐ 队列 * ☐ 双端队列 * ☐ 栈 * ☐ 单调队列 * ☐ 单调栈 ==== 分块数据结构 ==== * ☐ 块状数组 * ☐ 块状链表 ==== 树 ==== * ☐ 并查集 * ☐ 带权并查集 * ☐ 堆 * ☐ 树状数组 * ☐ 01-Trie * ☐ DFS 序 * ☐ Prufer 序列 * LCA * ☐ 倍增 LCA * ☐ Tarjan LCA * ☐ Huffman 树 * ☐ 笛卡尔树 * ☐ 左偏树 * ☐ 虚树 * ☐ 基环树 * ☐ 斯坦纳树 * ☐ 树上启发式合并 * ☐ K-D Tree * 线段树 * ☐ 基本线段树 * ☐ 李超线段树 * ☐ 区间 min-max 操作 * 树套树 * ☐ 线段树套线段树 * ☐ 线段树套平衡树 * ☐ 平衡树套线段树 * 点分治 * ☐ 静态点分治 * ☐ 动态点分治 * ☐ 边分治 * 平衡树 * ☐ Treap 随机平衡二叉树 * ☐ Splay 伸展树 * ☐ 替罪羊树 * ☐ AVL * ☐ 红黑树 * 动态树 * ☐ LCT * 树链剖分 * ☐ 重链剖分 * ☐ 长链剖分 * 树分块 * ☐ DFS 序分块 * ☐ 真树上分块 * 仙人掌 * ☐ 基础仙人掌 * ☐ 动态仙人掌 ==== 可持久化数据结构 ==== * ☐ 可持久化线段树（主席树） * ☐ 可持久化平衡树 * ☐ 可持久化 Trie ===== 图论 ===== ==== 最短路 ==== * ☐ Dijkstra * ☐ SPFA * ☐ Floyd * ☐ K 短路 * ☐ 线段树优化最短路 ==== 生成树 ==== * ☐ Prim * ☐ Kruskal * ☐ 次小生成树 * ☐ 最优比率生成树 ==== 回路 ==== * ☐ 欧拉回路 * ☐ 哈密顿回路 ==== 平面图 ==== * ☐ 欧拉定理（拓扑） * ☐ 平面图判定 ==== 连通分量 ==== * ☐ 连通分量 * ☐ 强连通分量 * ☐ 割点 * ☐ 桥边 * ☐ 点双连通分量 * ☐ 边双连通分量 ==== 网络流 ==== * ☐ 最大匹配 / 最小边覆盖 * ☐ 最大独立集 / 最小点覆盖 * ☐ 最大流 / 最小割 * ☐ König 定理 * ☐ 二分图最小割与最小点权覆盖 * 最大流 * ☐ Dinic（注意特殊图复杂度） * ☐ 数据结构优化 Dinic * ☐ Edmonds-Karp * ☐ O(VE) 最大流 * ☐ 有上下界最大流 * 最小割 * ☐ 最小割 * ☐ 平面图最小割 * ☐ 最小点权覆盖集 / 最大点券独立集 * ☐ 最大权闭合子图 * ☐ 0/1 分数规划 * ☐ 全局最小割 * 费用流 * ☐ SPFA 费用流 * ☐ zkw 费用流 * ☐ 最小费用可行流 * ☐ 消圈定理 * ☐ LP 对偶费用流 * 二分图 * ☐ 匈牙利算法 * ☐ 最大流算法 * ☐ Hopcroft-Karp 算法 * ☐ 覆盖集和独立集 * ☐ DAG 的链与反链 * ☐ 带权二分图匹配（KM 算法）（注意复杂度） * ☐ 霍尔定理 * ☐ 一般图最大权匹配（带花树） ==== 杂项 ==== * ☐ 拓扑排序 * ☐ 2-SAT（复杂度需注意） * ☐ 差分约束 * ☐ 稳定婚姻系统 * ☐ 环空间 * ☐ 三元环计数 * ☐ LGV Lemma * ☐ 最小点基 ===== 字符串 ===== ==== 匹配问题 ==== * ☐ KMP * ☐ 扩展 KMP * ☐ Trie * ☐ Aho-Corasick 自动机 ==== 后缀结构 ==== * ☐ 后缀数组 * ☐ 后缀树 * ☐ 后缀自动机（SAM） * ☐ 广义后缀自动机 * ☐ SA-IS ==== 回文串 ==== * ☐ manacher * ☐ PAM * ☐ 回文自动机 ==== 杂项 ==== * ☐ 基本 Border 理论 * ☐ 基本字串字典 * ☐ 回文串序列 * ☐ DFA（有限状态自动机） * ☐ Huffman 编码 * ☐ 字符串哈希 * ☐ Lyndon 分解 * ☐ 最小表示法 ===== 动态规划 ===== * ☐ 背包 DP * ☐ 区间 DP * ☐ DAG DP * ☐ 状压 DP * ☐ 数位 DP * ☐ 插头 DP * ☐ 可逆背包 DP * ☐ 子树合并类背包 DP * ☐ 单调优化 DP * ☐ 分治 DP * ☐ 斜率优化 * ☐ 四边形不等式 ===== 数论 ===== ==== 基础 ==== * ☐ GCD, LCM * ☐ 欧几里得算法 * ☐ 更相减损术（适用于大整数） * ☐ 快速幂 * ☐ 乘法逆元 * ☐ 裴蜀定理 * ☐ Eratosthenes 筛法 * ☐ Euler 筛法 ==== 线性递推 ==== * ☐ Fibonacci 数列（性质） * ☐ 皮萨诺周期 * ☐ Berlekamp-Massey 求最短递推式 * ☐ 拓展 BM * ☐ 矩阵快速幂加速递推 ==== 定理 ==== * ☐ 费马小定理 * ☐ 降幂大法 * ☐ 威尔逊定理 ==== 素性判断 ==== * ☐ Miller-Rabin * ☐ Pollard-Rho ==== 同余方程 ==== * ☐ BSGS * ☐ exBSGS * ☐ CRT * ☐ exCRT * ☐ Pell 方程 ==== 不定方程 ==== * ☐ 拓展欧几里得算法 * ☐ 二元一次不定方程 * ☐ 类欧几里得问题 ==== 剩余类 ==== * ☐ 二次剩余 * ☐ 三次剩余 * ☐ N 次剩余 * ☐ 任意模数 N 次剩余 ==== 反演 ==== * ☐ Mobius 反演 * ☐ 二项式反演 * ☐ Stirling 反演 * ☐ Lagrange 反演 ==== 筛法 ==== * ☐ 预处理积性函数 * ☐ 杜教筛 * ☐ 洲阁筛 * ☐ min_25 筛 ===== 组合数学 ===== ==== 置换群 ==== * ☐ Burnside 引理 * ☐ Pólya 定理 ==== 排列组合 ==== * ☐ Stirling 数 * ☐ Catalan 数 * ☐ Bell 数 * ☐ Bernoulli 数 * ☐ Lucas 定理 * ☐ 拓展 Lucas 定理 ==== 容斥原理 ==== * ☐ 递推容斥系数己算 * ☐ min-max 容斥 ==== 生成树计数 ==== * ☐ 基尔霍夫定理（矩阵树定理） * ☐ Best 定理 * ☐ 内向环 ==== 杂项 ==== * ☐ 鸽笼原理 * ☐ Ramsey 定理 * ☐ Cantor 展开 * ☐ 棋盘多项式 * ☐ Prufer 序列相关计数 ===== 多项式相关 ===== ==== 傅里叶 ==== * ☐ FFT * ☐ NTT * ☐ 任意模数 NTT * ☐ 子集卷积 * ☐ FWT * ☐ 分治 FFT ==== 多项式 ==== * ☐ 多项式除法 * ☐ 多项式求余 * ☐ 多项式求逆 * ☐ 多项式 exp * ☐ 多项式 ln * ☐ 多项式开根 * ☐ 多项式三角函数 * ☐ 多项式反三角函数 ==== 生成函数 ==== * ☐ 普通生成函数 * ☐ 指数型生成函数 * ☐ 二元生成函数 ==== 杂项 ==== * ☐ 多项式快速多点求值 * ☐ 拉格朗日插值 * ☐ 快速插值 ===== 计算几何 ===== * ☐ 半平面交 * ☐ 多边形 * ☐ 多面体 * ☐ 凸包的分治法 * ☐ 旋转卡壳 * ☐ 增量法 * ☐ 随机增量 * ☐ 平面解析几何及其应用 * ☐ 向量 * ☐ 点积及其应用 * ☐ 叉积及其应用 * ☐ Pick 定理 * ☐ 三角剖分 * ☐ 平面最近点对 * ☐ 凸多边形的交 * ☐ 离散化与扫描 * ☐ 圆反演 * ☐ 三维圆交 * ☐ 动态凸包 ===== 其他数学 ===== ==== 线性代数 ==== * ☐ 向量 * ☐ 矩阵 * ☐ 矩阵快速幂 * ☐ 高斯消元 * ☐ 行列式 * ☐ 线性基 * ☐ 线性基求并 * ☐ 线性基求交 * ☐ 矩阵微积分 ==== 博弈论 ==== * ☐ SG 定理 / SG 函数 * ☐ 纳什均衡 * ☐ 威佐夫博弈 * ☐ Surreal Number ==== 数值算法 ==== * ☐ 自适应 Simpson 积分 * ☐ 爬山法 * ☐ 模拟退火 * ☐ 遗传算法 ===== 杂项 ===== ==== 二分 ==== * ☐ 整体二分 * ☐ 带权二分 * ☐ 斜率二分 ==== 分治 ==== * ☐ 线段树分治 * ☐ CDQ 分治 ==== 莫队 ==== * ☐ 普通莫队 * ☐ 带修莫队 ==== 二进制集合枚举 ==== * ☐ 子集枚举 * ☐ 超集枚举 ==== 位运算 ==== * ☐ bitset * ☐ lowbit * ☐ popcount * ☐ ctz * ☐ clz ==== 贪心 ==== * ☐ 拟阵 ===== C++ 标准库 ===== ===== Policy Based Data Structure 库 =====