2020-2021:teams:i_dont_know_png:skill_tree
团队技能树
图论
| 知识点 | potassium | qxforever | nikkukun |
| 最短路 | Dijkstra | Y | Y | Y |
| SPFA | Y | Y | Y |
| 线段树优化建图 | Y | Y | Y |
| 生成树 | Prim | Y | | |
| Kruskal | Y | Y | Y |
| 回路 | 欧拉回路 | Y | Y | Y |
| 哈密顿回路 | Y | Y | Y |
| 平面图 | 欧拉定理 | Y | | Y |
| 平面图判定 | Y | | Y |
| 连通分量 | 有向图 | 强连通分量 | Y | Y | Y |
| 无向图 | 割点和桥 | Y | Y | Y |
| 点双连通分量 | Y | Y | Y |
| 边双连通分量 | Y（什么没板子，那没事了） | Y | Y |
| 路径问题 | K 短路 | | | Y |
| 差分约束系统 | Y | | Y |
| 生成树 | 次小生成树 | | | Y |
| 最优比率生成树 | Y | | Y |
| 拓扑排序 | Y | Y | Y |
| 2-SAT（注意复杂度） | Y | Y | Y |
| 稳定婚姻系统 | Y | | |
| 环空间 | | | Y |
| 三元环计数 | Y | | Y |
| LGV Lemma | Y | | Y |
| 最小点基 | | | |
网络流
| 知识点 | potassium | qxforever | nikkukun |
| 定理 | 最大匹配与最小边覆盖 | Y | | 忘了 |
| 最大独立集与最小点覆盖 | Y | | 忘了 |
| 最大流最小割 | Y | Y | Y |
| König 定理：二分图最大匹配与最小点覆盖 | | | 忘了 |
| 二分图最小割与最小点权覆盖 | | | 忘了 |
| 最大流 | Dinic（注意特殊图复杂度） | Y | Y | Y |
| 有上下界的最大流 | Y | | |
| 最小割 | 最小割 | Y | Y | Y |
| 平面图最小割 | | | Y |
| 最小点权覆盖集与最大点权独立集 | | | 忘了 |
| 最大权闭合子图 | 忘了 | | 忘了 |
| 0/1 分数规划 | 最大密度子图 | 忘了 | | Y |
| 全局最小割 | | | |
| 费用流 | SPFA 费用流 / zkw 费用流 | Y | Y | Y |
| 最小费用可行流 | | | |
| 消圈定理 | | | |
| LP 对偶费用流 | | | |
| 二分图 | 最大匹配 | 匈牙利算法（注意复杂度） | Y | Y | Y |
| 最大流算法 | Y | Y | Y |
| 覆盖集和独立集 | | | 忘了 |
| DAG 的链与反链 | | | 忘了 |
| 一般图最大匹配 | | | |
| 带权二分图匹配 | KM 算法（注意复杂度） | | | Y |
| 霍尔定理 | | Y | Y |
字符串
| 知识点 | potassium | qxforever | nikkukun |
| Trie | Y | Y | Y |
| AC自动机 | Y | Y | Y |
| KMP | KMP | Y | Y | Y |
| 扩展 KMP | Y | Y | |
| 后缀结构 | 后缀数组 | Y | | Y |
| SAM | Y | | Y |
| 广义 SAM | NNNNNNNNNNNNN | | Y |
| 后缀树 | | | |
| SA-IS | | | |
| 回文串 | Manacher | Y | | Y（需要复习） |
| PAM | Y | | Y |
| Border 理论 | Border Series | 基础 Border 理论 | | | Y（不太会） |
| 基本子串字典 | | | |
| Palindrome Series | | | Y（不太会） |
| 有限状态自动机 | Y | | 去年暑训有做过一个 DFA 的题 |
| Huffman 编码 | Y | Y | Y |
| 字符串哈希 | Y | Y | Y |
| Lyndon 分解 | Y（需要复习） | | Y（知道是个啥东西，没板子） |
| 最小表示法 | | | Y（会用后缀数组做） |
FFT 与多项式
| 知识点 | potassium | qxforever | nikkukun |
| FFT | FFT | Y | Y | Y |
| NTT | | Y | Y |
| 任意模数 FFT | Y | Y | Y |
| 多项式 | 多项式乘法 | Y | | Y |
| 多项式除法 / 取余 | Y | | Y |
| 多项式求逆 | Y | | Y |
| 多项式一顿操作 | | | Y |
| 常系数齐次线性递推 | 常系数齐次线性递推优化矩阵快速幂 | | | Y（需要复习） |
| BM 求最短递推式 | | | |
| 扩展 BM 求最短递推式 | | | |
| 位运算卷积 | 子集卷积 | Y | | |
| FWT | Y | | Y |
| 生成函数 | 普通生成函数 | 不太会 | | Y |
| 指数型生成函数 | | | Y（需要复习） |
| 拉格朗日插值 | Y（有板子一切好说） | | Y |
| 分治 FFT | Y | Y | Y |
数论
| 知识点 | potassium | qxforever | nikkukun |
| 素性判断 | Miller-Rabin（注意效率） | Y | Y | Y |
| Pollard-Rho（注意效率） | Y | Y | Y |
| 离散变换 | 同余方程 | 大步小步 | Y | Y | Y |
| 扩展大步小步 | Y | Y | 忘了 |
| 中国剩余定理 | Y | Y | Y（需要复习） |
| 扩展中国剩余定理 | Y | Y | Y（需要复习） |
| 二次剩余 | Y | Y | Y |
| 三次剩余 | Y | | |
| N 次剩余 | Y | - | Y |
| 任意模数 N 次剩余 | - | - | - |
| 欧几里得 | 扩展欧几里德 | Y | Y | Y |
| 二元一次不定方程求解 | Y | Y | Y（需要复习） |
| 类欧几里得 | Y | | Y（有板子就能写） |
| 置换群 | Burnside 引理 | | 只能最裸的 | Y |
| Pólya 定理 | | 只能最裸的 | Y |
| 反演 | Mobius 反演 | Y | | Y |
| 二项式反演 | | | |
| Stirling 反演 | | | |
| Lagrange 反演 | | | |
| 筛法 | 线筛积性函数 | Y | Y | Y |
| 杜教筛 | Y | | Y |
| 洲阁筛 | | | |
| min_25 筛 | Y | | Y（需要复习） |
| 矩阵 | 高斯消元 | 异或方程组 | Y | | Y |
| 求行列式 | | | |
| 辗转相除法高斯消元 | | | Y |
| 特征值与特征方程 | | | 忘了 |
| 矩阵的逆 | | | 知道，但没写过 |
| 排列组合 | Stirling 数 | Y | | |
| Lucas 定理 | Y | Y | Y |
| 扩展 Lucas 定理 | Y | | |
| 容斥原理 | 递推容斥系数计算 | 啥玩意啊.jpg | | Y |
| min-max 容斥 | | | Y |
| Fibonacci 数列 | 相关性质 | Y | | Y |
| 皮萨诺周期 | | | Y |
| 博弈论 | Nim 游戏 | 各种 Nim 游戏有待补充 | Y | Y | Y（指基础 Nim 游戏） |
| SG 函数 / SG 定理 | Y | Y | Y |
| 纳什均衡 | Y | | |
| 威佐夫博弈 | | | |
| 不平等博弈 / Surreal Number | Y | | |
| 杂项 | 威尔逊定理 | | | Y |
| 鸽笼原理 | Y | Y | Y |
| Ramsey 定理 | | | |
| 棋盘多项式 | | | |
| Catalan 数 | Y | | Y（但是不了解具体性质） |
数据结构
| 知识点 | potassium | qxforever | nikkukun |
| 树 | 点分治 | 点分治 | Y | Y | Y |
| 动态点分治 | | | |
| 平衡树 | Treap | Y | Y | Y |
| Splay | Y | | |
| 替罪羊树 | | | Y |
| 动态树 | 树链剖分 | Y | Y | Y |
| LCT | Y | | |
| 树分块 | 基于 DFS 序列 | Y | Y | Y |
| 真正的树上分块 | | | |
| 生成树计数 | 基尔霍夫定理（矩阵树定理） | Y | Y | |
| Best 定理 | | | |
| 内向环 | | | |
| Huffman 树 | Y | | Y |
| 笛卡尔树 | Y | | Y |
| 左偏树 / 可并堆 | Y（曾经） | | |
| 虚树 | | Y | Y |
| 基环树 | Y | | Y |
| 斯坦纳树 | - | - | Y（需要复习） |
| 树套树 | | Y | 并不熟练 |
| 树上启发式合并（DSU on tree） | Y | Y | Y |
| Prufer 序列 | Y（需要复习） | | Y |
| K-D Tree | | | |
| 线段树 | 李超线段树 | Y | | Y（需要整理板子） |
| 区间 min-max 操作 | Y | | Y（需要复习） |
| 仙人掌 | 仙人掌基础 | | | Y（需要重看边双连通分量） |
| 动态仙人掌 | | | |
| 可持久化结构 | 可持久化权值线段树（主席树） | Y | Y | |
| 可持久化并查集 | Y | | |
| 可持久化平衡树 | Y | | Y（需要复习） |
| 可持久化 Trie | | | |
| 线性基 | 线性基求并 | Y | | Y |
| 线性基求交 | Y | | Y |
| 块状链表 | | | |
动态规划
| 知识点 | potassium | qxforever | nikkukun |
| 数位 DP | 不太会 | | Y（需要复习） |
| 插头 DP | Y（一点点） | | |
| 背包 DP | 可逆背包 | Y | | Y |
| 子树合并类背包（及其时间复杂度证明） | Y | | Y（需要复习） |
| 单调性 DP 优化 | 单调栈优化（注意正确性） | Y | | |
| 分治 DP（注意时间复杂度） | Y | | Y |
| 斜率优化 | Y（需要复习） | | Y（需要复习） |
| 四边形不等式 | Y（需要复习） | | Y（需要复习） |
计算几何
| 知识点 | potassium | qxforever | nikkukun |
| 半平面交 | 这是大师的舞台→ | ? | ←这是大师的舞台 |
| 多边形 | | Y | |
| 多面体 | | | |
| 凸包的分治法 | | Y | |
| 旋转卡壳 | | Y | |
| 增量法 | | Y | |
| 随机增量 | | Y | |
| 平面解析几何及其应用 | | Y | |
| 向量 | | Y | |
| 点积及其应用 | | Y | |
| 叉积及其应用 | | Y | |
| 凸多边形的交 | | Y | |
| 离散化与扫描 | | | |
| 圆反演 | | | |
| 三维圆交 | | | |
| 动态凸包 | | | |
杂项
| 知识点 | potassium | qxforever | nikkukun |
| 二分算法 | 整体二分 | | | Y |
| 带权二分 | | | Y |
| 0/1 分数规划 | Y | Y | Y |
| 分治算法 | 线段树分治 | Y | Y | Y |
| CDQ 分治 | Y | | |
| 莫队算法 | 普通莫队 | Y | Y | Y |
| 带修改莫队 | | Y | Y |
| 树上莫队 | 基于 DFS 序的树上莫队 | | Y | Y |
| 真正的树上莫队 | | | |
| 二进制集合枚举 | 子集枚举 | Y | | Y |
| 超集枚举 | Y（现学现卖） | | Y |
| 位运算 | bitset 及其应用 | Y | Y | Y |
| 位运算匹配字符串 | | | |
| 自适应 Simpson 积分 | Y（不熟练） | | Y |
| 拟阵 | | | |
| 随机算法（爬山法 / 模拟退火 / 遗传算法） | 模拟退火 | 模拟退火 | Y（模拟退火） |
| pb_ds | | 会用 rb_tree | |
2020-2021/teams/i_dont_know_png/skill_tree.txt · 最后更改: 2020/05/25 01:38 由 nikkukun
