Warning: session_start(): open(/tmp/sess_8cde76878488d272b350f56c55fb34be, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Writing /data/wiki/data/cache/8/878e000dca5c08fe55e62fff31fad8b7.captchaip failed

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
2020-2021:teams:mian:testpage

知识点目录

数据结构

基础数据结构

☐ 数组
☐ 散列表
☐ 链表
☐ 双向链表
☐ 队列
☐ 双端队列
☐ 栈
☐ 单调队列
☐ 单调栈

分块数据结构

☐ 块状数组
☐ 块状链表

树

☐ 并查集
☐ 带权并查集
☐ 堆
☐ 树状数组
☐ 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 库