2020-2021:teams:looking_up_at_the_starry_sky:skil_tree
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:looking_up_at_the_starry_sky:skil_tree [2020/12/08 19:26] x342333349 [数据结构] |
2020-2021:teams:looking_up_at_the_starry_sky:skil_tree [2020/12/09 13:31] (当前版本) x342333349 [字符串] |
||
|---|---|---|---|
| 行 5: | 行 5: | ||
| ^ 知识点 ^^^ ws_zzyer ^ shy ^ Immortal.S ^ | ^ 知识点 ^^^ ws_zzyer ^ shy ^ Immortal.S ^ | ||
| - | | 最短路 | Dijkstra || | | | | + | | 最短路 | Dijkstra || 1 | | 1 | |
| - | | ::: | SPFA || | | | | + | | ::: | SPFA || 1 | | 1 | |
| - | | ::: | 线段树优化建图 || | | | | + | | ::: | 线段树优化建图 || 1 | | | |
| - | | 生成树 | Prim || | | | | + | | 生成树 | Prim || 1 | | 1 | |
| - | | ::: | Kruskal || | | | | + | | ::: | Kruskal || 1 | | 1 | |
| - | | 回路 | 欧拉回路 || | | | | + | | 回路 | 欧拉回路 || 1 | | | |
| - | | ::: | 哈密顿回路 || | | | | + | | ::: | 哈密顿回路 || 0 | | | |
| - | | 平面图 | 欧拉定理 || | | | | + | | 平面图 | 欧拉定理 || 0 | | | |
| - | | ::: | 平面图判定 || | | | | + | | ::: | 平面图判定 || 0 | | | |
| - | | 连通分量 | 有向图 | 强连通分量 | | | | | + | | 连通分量 | 有向图 | 强连通分量 | 1 | | 1 | |
| - | | ::: | 无向图 | 割点和桥 | | | | | + | | ::: | 无向图 | 割点和桥 | 1 | | 1 | |
| - | | ::: | ::: | 点双连通分量 | | | | | + | | ::: | ::: | 点双连通分量 | 1 | | | |
| - | | ::: | ::: | 边双连通分量 | | | | | + | | ::: | ::: | 边双连通分量 | 1 | | | |
| - | | 路径问题 | K 短路 || | | | | + | | 路径问题 | K 短路 || 0.5 | | | |
| - | | ::: | 差分约束系统 || | | | | + | | ::: | 差分约束系统 || 1 | | | |
| - | | 生成树 | 次小生成树 || | | | | + | | 生成树 | 次小生成树 || 1 | | | |
| - | | ::: | 最优比率生成树 || | | | | + | | ::: | 最优比率生成树 || 1 | | | |
| - | | 拓扑排序 ||| | | | | + | | 拓扑排序 ||| 1 | | 1 | |
| - | | 2-SAT（注意复杂度） ||| | | | | + | | 2-SAT（注意复杂度） ||| 1 | | | |
| - | | 稳定婚姻系统 ||| | | | | + | | 稳定婚姻系统 ||| 0 | | | |
| - | | 环空间 ||| | | | | + | | 环空间 ||| 0 | | | |
| - | | 三元环计数 ||| | | | | + | | 三元环计数 ||| 1 | | | |
| - | | LGV Lemma ||| | | | | + | | LGV Lemma ||| 0.5 | | | |
| - | | 最小点基 ||| | | | | + | | 最小点基 ||| 0 | | | |
| 行 34: | 行 34: | ||
| ^ 知识点 ^^^ ws_zzyer ^ shy ^ Immortal.S ^ | ^ 知识点 ^^^ ws_zzyer ^ shy ^ Immortal.S ^ | ||
| - | | 定理 | 最大匹配与最小边覆盖 || | | | | + | | 定理 | 最大匹配与最小边覆盖 || 1 | | | |
| - | | ::: | 最大独立集与最小点覆盖 || | | | | + | | ::: | 最大独立集与最小点覆盖 || 1 | | | |
| - | | ::: | 最大流最小割 || | | | | + | | ::: | 最大流最小割 || 1 | | | |
| - | | ::: | König 定理：二分图最大匹配与最小点覆盖 || | | | | + | | ::: | König 定理：二分图最大匹配与最小点覆盖 || 1 | | | |
| - | | ::: | 二分图最小割与最小点权覆盖 || | | | | + | | ::: | 二分图最小割与最小点权覆盖 || 1 | | | |
| - | | 最大流 | Dinic（注意特殊图复杂度） || | | | | + | | 最大流 | Dinic（注意特殊图复杂度） || 1 | | | |
| - | | ::: | 有上下界的最大流 || | | | | + | | ::: | 有上下界的最大流 || 0.5 | | | |
| - | | 最小割 | 最小割 || | | | | + | | 最小割 | 最小割 || 1 | | | |
| - | | ::: | 平面图最小割 || | | | | + | | ::: | 平面图最小割 || 1 | | | |
| - | | ::: | 最小点权覆盖集与最大点权独立集 || | | | | + | | ::: | 最小点权覆盖集与最大点权独立集 || 1 | | | |
| - | | ::: | 最大权闭合子图 || | | | | + | | ::: | 最大权闭合子图 || 1 | | | |
| - | | ::: | 0/1 分数规划 | | | | | | + | | ::: | 0/1 分数规划 | 最大密度子图 | 0 | | | |
| - | | ::: | 全局最小割 || | | | | + | | ::: | 全局最小割 || 0.5 | | | |
| - | | 费用流 | SPFA 费用流 / zkw 费用流 || | | | | + | | 费用流 | SPFA 费用流 / zkw 费用流 || 0 | | | |
| - | | ::: | 最小费用可行流 || | | | | + | | ::: | 最小费用可行流 || 0.5 | | | |
| - | | ::: | 消圈定理 || | | | | + | | ::: | 消圈定理 || 0 | | | |
| - | | ::: | LP 对偶费用流 || | | | | + | | ::: | LP 对偶费用流 || 0 | | | |
| - | | 二分图 | 最大匹配 | | | | | | + | | 二分图 | 最大匹配 | 匈牙利算法（注意复杂度） | 1 | | | |
| - | | ::: | ::: | | | | | | + | | ::: | ::: | 最大流算法 | 1 | | | |
| - | | ::: | ::: | | | | | | + | | ::: | ::: | 覆盖集和独立集 | | | | |
| - | | ::: | ::: | | | | | | + | | ::: | ::: | DAG 的链与反链 | 0 | | | |
| - | | ::: | ::: | | | | | | + | | ::: | ::: | 一般图最大匹配 | 0 | | | |
| - | | ::: | 带权二分图匹配 | | | | | | + | | ::: | 带权二分图匹配 | KM 算法（注意复杂度） | 1 | | | |
| - | | ::: | 霍尔定理 || | | | | + | | ::: | 霍尔定理 || 1 | | | |
| ===== 字符串 ===== | ===== 字符串 ===== | ||
| ^ 知识点 ^^^ ws_zzyer ^ shy ^ Immortal.S ^ | ^ 知识点 ^^^ ws_zzyer ^ shy ^ Immortal.S ^ | ||
| - | | Trie ||| | | | | + | | Trie ||| 1 | | | |
| - | | AC自动机 ||| | | | | + | | AC自动机 ||| 1 | | | |
| - | | KMP | KMP || | | | | + | | KMP | KMP || 1 | | 1 | |
| - | | ::: | 扩展 KMP || | | | | + | | ::: | 扩展 KMP || 0.5 | | | |
| - | | 后缀结构 | 后缀数组 || | | | | + | | 后缀结构 | 后缀数组 || 1 | | 1 | |
| - | | ::: | SAM || | | | | + | | ::: | SAM || 1 | | | |
| - | | ::: | 广义 SAM || | | | | + | | ::: | 广义 SAM || 1 | | | |
| - | | ::: | 后缀树 || | | | | + | | ::: | 后缀树 || 0 | | | |
| - | | ::: | SA-IS || | | | | + | | ::: | SA-IS || 0 | | | |
| - | | 回文串 | Manacher || | | | | + | | 回文串 | Manacher || 1 | | 1 | |
| - | | ::: | PAM || | | | | + | | ::: | PAM || 1 | | | |
| - | | Border 理论 | | | | | | | + | | Border 理论 | Border Series | 基础 Border 理论 | 0.5 | | | |
| - | | ::: | ::: | | | | | | + | | ::: | ::: | 基本子串字典 | | | | |
| - | | ::: | || | | | | + | | ::: | Palindrome Series || 0 | | | |
| - | | 有限状态自动机 ||| | | | | + | | 有限状态自动机 ||| 0.5 | | | |
| - | | Huffman 编码 ||| | | | | + | | Huffman 编码 ||| 1 | | | |
| - | | 字符串哈希 ||| | | | | + | | 字符串哈希 ||| 1 | | | |
| - | | Lyndon 分解 ||| | | | | + | | Lyndon 分解 ||| 1 | | | |
| - | | 最小表示法 ||| | | | | + | | 最小表示法 ||| 1 | | | |
| ===== FFT 与多项式 ===== | ===== FFT 与多项式 ===== | ||
| ^ 知识点 ^^^ ws_zzyer ^ shy ^ Immortal.S ^ | ^ 知识点 ^^^ ws_zzyer ^ shy ^ Immortal.S ^ | ||
| - | | FFT | FFT || | | | | + | | FFT | FFT || 1 | | | |
| - | | ::: | NTT || | | | | + | | ::: | NTT || 1 | | | |
| - | | ::: | 任意模数 FFT || | | | | + | | ::: | 任意模数 FFT || 1 | | | |
| - | | 多项式 | 多项式乘法 || | | | | + | | 多项式 | 多项式乘法 || 1 | | | |
| - | | ::: | 多项式除法 / 取余 || | | | | + | | ::: | 多项式除法 / 取余 || 1 | | | |
| - | | ::: | 多项式求逆 || | | | | + | | ::: | 多项式求逆 || 1 | | | |
| - | | ::: | 多项式一顿操作 || | | | | + | | ::: | 多项式一顿操作 || 0 | | | |
| - | | 常系数齐次线性递推 | 常系数齐次线性递推优化矩阵快速幂 || | | | | + | | 常系数齐次线性递推 | 常系数齐次线性递推优化矩阵快速幂 || 0 | | | |
| - | | ::: | BM 求最短递推式 || | | | | + | | ::: | BM 求最短递推式 || 0 | | | |
| - | | ::: | 扩展 BM 求最短递推式 || | | | | + | | ::: | 扩展 BM 求最短递推式 || 0 | | | |
| - | | 位运算卷积 | 子集卷积 || | | | | + | | 位运算卷积 | 子集卷积 || 1 | | | |
| - | | ::: | FWT || | | | | + | | ::: | FWT || 1 | | | |
| - | | 生成函数 | 普通生成函数 || | | | | + | | 生成函数 | 普通生成函数 || 1 | | | |
| - | | ::: | 指数型生成函数 || | | | | + | | ::: | 指数型生成函数 || 1 | | | |
| - | | 拉格朗日插值 ||| | | | | + | | 拉格朗日插值 ||| 1 | | | |
| - | | 分治 FFT ||| | | | | + | | 分治 FFT ||| 1 | | | |
| ===== 数论 ===== | ===== 数论 ===== | ||
| 行 154: | 行 154: | ||
| ^ 知识点 ^^^ ws_zzyer ^ shy ^ Immortal.S ^ | ^ 知识点 ^^^ ws_zzyer ^ shy ^ Immortal.S ^ | ||
| - | | 树 | 点分治 | 点分治 | | | | | + | | 树 | 点分治 | 点分治 | | | 1 | |
| | ::: | ::: | 动态点分治 | | | | | | ::: | ::: | 动态点分治 | | | | | ||
| | ::: | 平衡树 | Treap | | | | | | ::: | 平衡树 | Treap | | | | | ||
| - | | ::: | ::: | Splay | | | | | + | | ::: | ::: | Splay | | | | |
| | ::: | ::: | 替罪羊树 | | | | | | ::: | ::: | 替罪羊树 | | | | | ||
| | ::: | 动态树 | 树链剖分 | | | | | | ::: | 动态树 | 树链剖分 | | | | | ||
| 行 180: | 行 180: | ||
| | 仙人掌 | 仙人掌基础 || | | | | | 仙人掌 | 仙人掌基础 || | | | | ||
| | ::: | 动态仙人掌 || | | | | | ::: | 动态仙人掌 || | | | | ||
| - | | 可持久化结构 | 可持久化权值线段树（主席树） || | | | | + | | 可持久化结构 | 可持久化权值线段树（主席树） || | | 1 | |
| | ::: | 可持久化并查集 || | | | | | ::: | 可持久化并查集 || | | | | ||
| | ::: | 可持久化平衡树 || | | | | | ::: | 可持久化平衡树 || | | | | ||
| 行 203: | 行 203: | ||
| ^ 知识点 ^^^ ws_zzyer ^ shy ^ Immortal.S ^ | ^ 知识点 ^^^ ws_zzyer ^ shy ^ Immortal.S ^ | ||
| - | | 半平面交 ||| 这是大师的舞台-> | ? | <-这是大师的舞台 | | + | | 半平面交 ||| | | | |
| - | | 多边形 ||| | Y | | | + | | 多边形 ||| | | | |
| | 多面体 ||| | | | | | 多面体 ||| | | | | ||
| - | | 凸包的分治法 ||| | Y | | | + | | 凸包的分治法 ||| | | | |
| - | | 旋转卡壳 ||| | Y | | | + | | 旋转卡壳 ||| | | | |
| - | | 增量法 ||| | Y | | | + | | 增量法 ||| | | | |
| - | | 随机增量 ||| | Y | | | + | | 随机增量 ||| | | | |
| - | | 平面解析几何及其应用 ||| | Y | | | + | | 平面解析几何及其应用 ||| | | | |
| - | | 向量 ||| | Y | | | + | | 向量 ||| | | | |
| - | | 点积及其应用 ||| | Y | | | + | | 点积及其应用 ||| | | | |
| - | | 叉积及其应用 ||| | Y | | | + | | 叉积及其应用 ||| | | | |
| - | | 凸多边形的交 ||| | Y | | | + | | 凸多边形的交 ||| | | | |
| | 离散化与扫描 ||| | | | | | 离散化与扫描 ||| | | | | ||
| | 圆反演 ||| | | | | | 圆反演 ||| | | | | ||
| 行 225: | 行 225: | ||
| | 二分算法 | 整体二分 || | | | | | 二分算法 | 整体二分 || | | | | ||
| | ::: | 带权二分 || | | | | | ::: | 带权二分 || | | | | ||
| - | | ::: | 0/1 分数规划 || | | | | + | | ::: | 0/1 分数规划 || | | 1 | |
| | 分治算法 | 线段树分治 || | | | | | 分治算法 | 线段树分治 || | | | | ||
| | ::: | CDQ 分治 || | | | | | ::: | CDQ 分治 || | | | | ||
| - | | 莫队算法 | 普通莫队 || | | | | + | | 莫队算法 | 普通莫队 || | | 1 | |
| | ::: | 带修改莫队 || | | | | | ::: | 带修改莫队 || | | | | ||
| - | | ::: | 树上莫队 | | | | | | + | | ::: | 树上莫队 | 基于 DFS 序的树上莫队 | | | | |
| - | | ::: | ::: | | | | | | + | | ::: | ::: | 真正的树上莫队 | | | | |
| | 二进制集合枚举 | 子集枚举 || | | | | | 二进制集合枚举 | 子集枚举 || | | | | ||
| | ::: | 超集枚举 || | | | | | ::: | 超集枚举 || | | | | ||
2020-2021/teams/looking_up_at_the_starry_sky/skil_tree.1607426813.txt.gz · 最后更改: 2020/12/08 19:26 由 x342333349
