2020-2021:teams:i_dont_know_png:skill_tree
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:skill_tree [2020/05/09 14:36] potassium |
2020-2021:teams:i_dont_know_png:skill_tree [2020/05/25 01:38] (当前版本) nikkukun add some skills |
||
|---|---|---|---|
| 行 5: | 行 5: | ||
| ^ 知识点 ^^^ potassium ^ qxforever ^ nikkukun ^ | ^ 知识点 ^^^ potassium ^ qxforever ^ nikkukun ^ | ||
| - | | 拓扑排序 ||| Y | Y | Y | | + | | 最短路 | Dijkstra || Y | Y | Y | |
| - | | 最短路 | Dijstra || Y | Y | Y | | + | |
| | ::: | SPFA || Y | Y | Y | | | ::: | SPFA || Y | Y | Y | | ||
| | ::: | 线段树优化建图 || Y | Y | Y | | | ::: | 线段树优化建图 || Y | Y | Y | | ||
| 行 15: | 行 14: | ||
| | 平面图 | 欧拉定理 || 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 | 忘了 | | + | | ::: | ::: | 边双连通分量 | Y（什么没板子，那没事了） | Y | Y | |
| - | | 路径问题 | K 短路 || | | | | + | | 路径问题 | K 短路 || | | Y | |
| | ::: | 差分约束系统 || Y | | Y | | | ::: | 差分约束系统 || Y | | Y | | ||
| | 生成树 | 次小生成树 || | | Y | | | 生成树 | 次小生成树 || | | Y | | ||
| - | | ::: | 最优比率生成树 || | | Y | | + | | ::: | 最优比率生成树 || Y | | Y | |
| + | | 拓扑排序 ||| Y | Y | Y | | ||
| | 2-SAT（注意复杂度） ||| Y | Y | Y | | | 2-SAT（注意复杂度） ||| Y | Y | Y | | ||
| - | | 稳定婚姻系统 ||| | | | | + | | 稳定婚姻系统 ||| Y | | | |
| | 环空间 ||| | | Y | | | 环空间 ||| | | Y | | ||
| - | | 三元环计数 ||| | | | | + | | 三元环计数 ||| Y | | Y | |
| - | | LVG Lemma ||| | | | | + | | LGV Lemma ||| Y | | Y | |
| + | | 最小点基 ||| | | | | ||
| ===== 网络流 ===== | ===== 网络流 ===== | ||
| 行 62: | 行 64: | ||
| | Trie ||| Y | Y | Y | | | Trie ||| Y | Y | Y | | ||
| | AC自动机 ||| Y | Y | Y | | | AC自动机 ||| Y | Y | Y | | ||
| - | | KMP | KMP || Y | Y | Y（需要复习） | | + | | KMP | KMP || Y | Y | Y | |
| | ::: | 扩展 KMP || Y | Y | | | | ::: | 扩展 KMP || Y | Y | | | ||
| - | | ::: | Border 理论 || | | | | + | | 后缀结构 | 后缀数组 || Y | | Y | |
| - | | 后缀结构 | 后缀数组 || Y | | Y（需要复习） | | + | | ::: | SAM || Y | | Y | |
| - | | ::: | SAM || Y | | Y（需要复习） | | + | | ::: | 广义 SAM || NNNNNNNNNNNNN | | Y | |
| - | | ::: | 广义 SAM || NNNNNNNNNNNNN | | Y（需要复习） | | + | |
| | ::: | 后缀树 || | | | | | ::: | 后缀树 || | | | | ||
| | ::: | SA-IS || | | | | | ::: | SA-IS || | | | | ||
| | 回文串 | Manacher || Y | | Y（需要复习） | | | 回文串 | Manacher || Y | | Y（需要复习） | | ||
| - | | ::: | PAM || Y | | Y（需要复习） | | + | | ::: | PAM || Y | | Y | |
| + | | Border 理论 | Border Series | 基础 Border 理论 | | | Y（不太会） | | ||
| + | | ::: | ::: | 基本子串字典 | | | | | ||
| + | | ::: | Palindrome Series || | | Y（不太会） | | ||
| | 有限状态自动机 ||| Y | | 去年暑训有做过一个 DFA 的题 | | | 有限状态自动机 ||| Y | | 去年暑训有做过一个 DFA 的题 | | ||
| | Huffman 编码 ||| Y | Y | Y | | | Huffman 编码 ||| Y | Y | Y | | ||
| | 字符串哈希 ||| Y | Y | Y | | | 字符串哈希 ||| Y | Y | Y | | ||
| - | | Lyndon 分解 ||| Y（需要复习） | | | | + | | Lyndon 分解 ||| Y（需要复习） | | Y（知道是个啥东西，没板子） | |
| - | | 最小表示法 ||| | | | | + | | 最小表示法 ||| | | Y（会用后缀数组做） | |
| ===== FFT 与多项式 ===== | ===== FFT 与多项式 ===== | ||
| 行 83: | 行 87: | ||
| | FFT | FFT || Y | Y | Y | | | FFT | FFT || Y | Y | Y | | ||
| | ::: | NTT || | Y | Y | | | ::: | NTT || | Y | Y | | ||
| - | | ::: | MTT || | Y | Y | | + | | ::: | 任意模数 FFT || Y | Y | Y | |
| | 多项式 | 多项式乘法 || Y | | Y | | | 多项式 | 多项式乘法 || Y | | Y | | ||
| | ::: | 多项式除法 / 取余 || Y | | Y | | | ::: | 多项式除法 / 取余 || Y | | Y | | ||
| 行 101: | 行 105: | ||
| ^ 知识点 ^^^ potassium ^ qxforever ^ nikkukun ^ | ^ 知识点 ^^^ potassium ^ qxforever ^ nikkukun ^ | ||
| - | | 素性判断 | Miller-Robin（注意效率） || Y | Y | Y | | + | | 素性判断 | Miller-Rabin（注意效率） || Y | Y | Y | |
| | ::: | Pollard-Rho（注意效率） || Y | Y | Y | | | ::: | Pollard-Rho（注意效率） || Y | Y | Y | | ||
| | 离散变换 | 同余方程 | 大步小步 | Y | Y | Y | | | 离散变换 | 同余方程 | 大步小步 | Y | Y | Y | | ||
| 行 109: | 行 113: | ||
| | ::: | 二次剩余 || Y | Y | Y | | | ::: | 二次剩余 || Y | Y | Y | | ||
| | ::: | 三次剩余 || Y | | | | | ::: | 三次剩余 || Y | | | | ||
| + | | ::: | N 次剩余 || Y | - | Y | | ||
| + | | ::: | 任意模数 N 次剩余 || - | - | - | | ||
| | 欧几里得 | 扩展欧几里德 || Y | Y | Y | | | 欧几里得 | 扩展欧几里德 || Y | Y | Y | | ||
| | ::: | 二元一次不定方程求解 || Y | Y | Y（需要复习） | | | ::: | 二元一次不定方程求解 || Y | Y | Y（需要复习） | | ||
| 行 117: | 行 123: | ||
| | ::: | 二项式反演 || | | | | | ::: | 二项式反演 || | | | | ||
| | ::: | Stirling 反演 || | | | | | ::: | Stirling 反演 || | | | | ||
| + | | ::: | Lagrange 反演 || | | | | ||
| | 筛法 | 线筛积性函数 || Y | Y | Y | | | 筛法 | 线筛积性函数 || Y | Y | Y | | ||
| | ::: | 杜教筛 || Y | | Y | | | ::: | 杜教筛 || Y | | Y | | ||
| | ::: | 洲阁筛 || | | | | | ::: | 洲阁筛 || | | | | ||
| | ::: | min_25 筛 || Y | | Y（需要复习） | | | ::: | min_25 筛 || Y | | Y（需要复习） | | ||
| - | | 矩阵 | 高斯消元 | 异或方程组 | Y || Y | | + | | 矩阵 | 高斯消元 | 异或方程组 | Y | | Y | |
| | ::: | ::: | 求行列式 | | | | | | ::: | ::: | 求行列式 | | | | | ||
| | ::: | ::: | 辗转相除法高斯消元 | | | Y | | | ::: | ::: | 辗转相除法高斯消元 | | | Y | | ||
| 行 164: | 行 171: | ||
| | ::: | 虚树 || | Y | Y | | | ::: | 虚树 || | Y | Y | | ||
| | ::: | 基环树 || Y | | Y | | | ::: | 基环树 || Y | | Y | | ||
| + | | ::: | 斯坦纳树 || - | - | Y（需要复习） | | ||
| | ::: | 树套树 || | Y | 并不熟练 | | | ::: | 树套树 || | Y | 并不熟练 | | ||
| | ::: | 树上启发式合并（DSU on tree） || Y | Y | Y | | | ::: | 树上启发式合并（DSU on tree） || Y | Y | Y | | ||
2020-2021/teams/i_dont_know_png/skill_tree.1589006209.txt.gz · 最后更改: 2020/05/09 14:36 由 potassium
