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 库
2020-2021/teams/mian/testpage.txt · 最后更改: 2020/08/04 22:18 由 grapelemonade
