2020-2021:teams:farmer_john:knowledge_tree
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:knowledge_tree [2020/08/11 21:45] 2sozx [数论] |
2020-2021:teams:farmer_john:knowledge_tree [2020/08/11 22:08] (当前版本) 2sozx [杂项] |
||
|---|---|---|---|
| 行 136: | 行 136: | ||
| ^ 知识点 ^^^ 2sozx ^ JJLeo ^ Bazoka13 ^ | ^ 知识点 ^^^ 2sozx ^ JJLeo ^ Bazoka13 ^ | ||
| - | | 树 | 点分治 | 点分治 | Y | Y | Y | | + | | 树 | 点分治 | 点分治 | | √ | | |
| - | | ::: | ::: | 动态点分治 | Y | Y | | | + | | ::: | ::: | 动态点分治 | √ | | | |
| - | | ::: | 平衡树 | Treap | Y | Y | Y | | + | | ::: | 平衡树 | Treap | √ | √ | √ | |
| - | | ::: | ::: | FHQ Treap | | | | | + | | ::: | ::: | FHQ Treap | √ | √ | √ | |
| - | | ::: | ::: | Splay | Y | Y | Y | | + | | ::: | ::: | Splay | √ | √ | √ | |
| - | | ::: | ::: | 替罪羊树 | | Y | | | + | | ::: | ::: | 替罪羊树 | √ | √ | √ | |
| - | | ::: | 动态树 | 树链剖分 | Y | Y | Y | | + | | ::: | 动态树 | 树链剖分 | | √ | | |
| - | | ::: | ::: | LCT | Y | Y | | | + | | ::: | ::: | LCT | | √ | | |
| - | | ::: | 树分块 | 基于 DFS 序列 | | 忘了 | | | + | | ::: | 树分块 | 基于 DFS 序列 | （题） | | | |
| | ::: | ::: | 真正的树上分块 | | | | | | ::: | ::: | 真正的树上分块 | | | | | ||
| - | | ::: | 生成树计数 | 基尔霍夫定理（矩阵树定理） | | Y | | | + | | ::: | 生成树计数 | 基尔霍夫定理（矩阵树定理） | | √ | | |
| - | | ::: | ::: | Best 定理 | | | | | + | | ::: | 笛卡尔树 || | | √ | |
| - | | ::: | Huffman 树 || Y | Y | | | + | | ::: | 左偏树 / 可并堆 || | √ | | |
| - | | ::: | 笛卡尔树 || | | | | + | | ::: | 虚树 || | √ | | |
| - | | ::: | 左偏树 / 可并堆 || | Y | | | + | | ::: | 基环树 || | （题） | | |
| - | | ::: | 虚树 || | Y | | | + | | ::: | 斯坦纳树 || | | √ | |
| - | | ::: | 基环树 || | Y | | | + | | ::: | 树上启发式合并（DSU on tree） || | √ | | |
| - | | ::: | 斯坦纳树 || - | - | | | + | | ::: | Prufer 序列 || √ | √ | √ | |
| - | | ::: | 树套树 || | Y | | | + | | ::: | K-D Tree || √ | √ | √ | |
| - | | ::: | 树上启发式合并（DSU on tree） || | Y | | | + | | 线段树 | 李超线段树 || | | √ | |
| - | | ::: | Prufer 序列 || | | | | + | | ::: | 区间 min-max 操作 || √ | | | |
| - | | ::: | K-D Tree || | Y | | | + | | 仙人掌 | 仙人掌基础 || | √ | | |
| - | | 线段树 | 李超线段树 || | | y（会板子） | | + | | ::: | 动态仙人掌 || | √ | | |
| - | | ::: | 区间 min-max 操作 || | | | | + | | 可持久化结构 | 带修主席树 || | | √ | |
| - | | 仙人掌 | 仙人掌基础 || | Y | | | + | | ::: | 可持久化并查集 || | √ | | |
| - | | ::: | 动态仙人掌 || | | | | + | | ::: | 可持久化平衡树 || | √ | | |
| - | | 可持久化结构 | 可持久化权值线段树（主席树） || Y | Y | Y | | + | | 线性基 | 线性基求交 || √ | √ | √ | |
| - | | ::: | 可持久化并查集 || | Y | | | + | | 块状链表 ||| √（题） | | | |
| - | | ::: | 可持久化平衡树 || | Y | | | + | |
| - | | ::: | 可持久化 Trie || Y | Y | | | + | |
| - | | 线性基 | 线性基求并 || | Y | | | + | |
| - | | ::: | 线性基求交 || | | | | + | |
| - | | 块状链表 ||| Y | | | | + | |
| ===== 动态规划 ===== | ===== 动态规划 ===== | ||
| ^ 知识点 ^^^ 2sozx ^ JJLeo ^ Bazoka13 ^ | ^ 知识点 ^^^ 2sozx ^ JJLeo ^ Bazoka13 ^ | ||
| - | | 数位 DP ||| Y | Y | Y | | + | | 数位 DP ||| √ | √ | √ | |
| - | | 插头 DP ||| | | | | + | | 插头 DP ||| √ | √ | √ | |
| - | | 背包 DP | 可逆背包 || | | | | + | | 背包 DP | 可逆背包 || √ | √ | √ | |
| - | | ::: | 子树合并类背包（及其时间复杂度证明） || | Y | | | + | | ::: | 子树合并类背包（及其时间复杂度证明） || | √ | | |
| - | | 单调性 DP 优化 | 单调栈优化（注意正确性） || | Y | | | + | | 单调性 DP 优化 | 单调栈优化（注意正确性） || √ | √ | √ | |
| - | | ::: | 分治 DP（注意时间复杂度） || Y | | | | + | | ::: | 分治 DP（注意时间复杂度） || √ | √ | √ | |
| - | | ::: | 斜率优化 || Y | Y | Y | | + | | ::: | 斜率优化 || √ | √ | √ | |
| - | | ::: | 四边形不等式 || | | | | + | | ::: | 四边形不等式 || √ | √ | √ | |
| ===== 计算几何 ===== | ===== 计算几何 ===== | ||
| ^ 知识点 ^^^ 2sozx ^ JJLeo ^ Bazoka13 ^ | ^ 知识点 ^^^ 2sozx ^ JJLeo ^ Bazoka13 ^ | ||
| - | | 半平面交 ||| | Y | Y | | + | | 半平面交 ||| | | √ | |
| - | | 多边形 ||| | | Y | | + | | 多边形 ||| | | √ | |
| - | | 多面体 ||| | | | | + | | 多面体 ||| | | √ | |
| - | | 凸包的分治法 ||| | | Y | | + | | 凸包的分治法 ||| | | √ | |
| - | | 旋转卡壳 ||| | Y | Y | | + | | 旋转卡壳 ||| | | √ | |
| - | | 增量法 ||| | | Y | | + | | 增量法 ||| | | √ | |
| - | | 随机增量 ||| | | Y | | + | | 随机增量 ||| | | √ | |
| - | | 平面解析几何及其应用 ||| | | | | + | | 向量 ||| | | √ | |
| - | | 向量 ||| Y | | Y | | + | | 点积及其应用 ||| | | √ | |
| - | | 点积及其应用 ||| Y | | Y | | + | | 叉积及其应用 ||| | | √ | |
| - | | 叉积及其应用 ||| Y | | Y | | + | | 凸多边形的交 ||| | | √ | |
| - | | 凸多边形的交 ||| | Y | Y | | + | | 离散化与扫描 ||| | | √ | |
| - | | 离散化与扫描 ||| Y | Y | Y | | + | | 圆反演 ||| | | √ | |
| - | | 圆反演 ||| | | Y | | + | | 动态凸包 ||| | | √ | |
| - | | 动态凸包 ||| | Y | Y | | + | | 圆的交与并 ||| | | √ | |
| ===== 杂项 ===== | ===== 杂项 ===== | ||
| ^ 知识点 ^^^ 2sozx ^ JJLeo ^ Bazoka13 ^ | ^ 知识点 ^^^ 2sozx ^ JJLeo ^ Bazoka13 ^ | ||
| - | | 二分算法 | 整体二分 || Y | | | | + | | 二分算法 | 整体二分 || √ | √ | √ | |
| - | | ::: | 带权二分 || | Y | | | + | | ::: | 带权二分 || | √ | | |
| - | | ::: | 0/1 分数规划 || Y | | Y | | + | | ::: | 0/1 分数规划 || √（题） | | | |
| - | | 分治算法 | 线段树分治 || Y | Y | Y | | + | | 分治算法 | 线段树分治 || | √ | | |
| - | | ::: | CDQ 分治 || Y | Y | | | + | | ::: | CDQ 分治 || √（题） | | | |
| - | | 莫队算法 | 普通莫队 || Y | Y | Y | | + | | 莫队算法 | 带修改莫队 || √ | √ | √ | |
| - | | ::: | 带修改莫队 || | Y | | | + | | ::: | 树上莫队 | 基于 DFS 序的树上莫队 | √ | √ | | |
| - | | ::: | 树上莫队 | 基于 DFS 序的树上莫队 | | Y | | | + | | ::: | ::: | 真正的树上莫队 | ？ | ？ | ？ | |
| - | | ::: | ::: | 真正的树上莫队 | | | | | + | | 位运算 | 压位大法 || √ | √ | √ | |
| - | | 二进制集合枚举 | 子集枚举 || Y | Y | Y | | + | | ::: | shift-and/shift-or || √ | √ | √ | |
| - | | ::: | 超集枚举 || Y | | Y | | + | | 自适应 Simpson 积分 ||| | √ | | |
| - | | 位运算 | bitset 及其应用 || Y | Y | Y | | + | | 拟阵 ||| √ | | | |
| - | | ::: | 位运算匹配字符串 || | Y | | | + | | 随机算法（爬山法 / 模拟退火 / 遗传算法） ||| 爬 | 摸 | 遗 | |
| - | | 自适应 Simpson 积分 ||| | Y | | | + | | pb_ds ||| | | √ | |
| - | | 拟阵 ||| | | | | + | |
| - | | 随机算法（爬山法 / 模拟退火 / 遗传算法） ||| | | | | + | |
| - | | pb_ds ||| | | y（还行） | | + | |
2020-2021/teams/farmer_john/knowledge_tree.1597153525.txt.gz · 最后更改: 2020/08/11 21:45 由 2sozx
