2020-2021:teams:farmer_john:knowledge_tree
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:knowledge_tree [2020/08/11 21:30] 2sozx [FFT 与多项式] |
2020-2021:teams:farmer_john:knowledge_tree [2020/08/11 22:08] (当前版本) 2sozx [杂项] |
||
|---|---|---|---|
| 行 91: | 行 91: | ||
| ^ 知识点 ^^^ 2sozx ^ JJLeo ^ Bazoka13 ^ | ^ 知识点 ^^^ 2sozx ^ JJLeo ^ Bazoka13 ^ | ||
| - | | 素性判断 | Miller-Rabin（注意效率） || Y | | Y | | + | | 素性判断 | Miller-Rabin（注意效率） || √ | √（java） | | |
| - | | ::: | Pollard-Rho（注意效率） || Y | | | | + | | ::: | Pollard-Rho（注意效率） || √ | | | |
| - | | 离散变换 | 同余方程 | 大步小步 | Y | Y | Y | | + | | 离散变换 | 同余方程 | 大步小步 | √ | | | |
| - | | ::: | ::: | 扩展大步小步 | | Y | | | + | | ::: | ::: | 扩展大步小步 | √ | | | |
| - | | ::: | ::: | 中国剩余定理 | Y | Y | Y | | + | | ::: | ::: | 中国剩余定理 | | | √ | |
| - | | ::: | ::: | 扩展中国剩余定理 | | Y | | | + | | ::: | ::: | 扩展中国剩余定理 | | | √ | |
| - | | ::: | 二次剩余 || | | | | + | | ::: | 二次剩余 || √ | | | |
| - | | ::: | 三次剩余 || | | | | + | | ::: | 三次剩余 || √ | | | |
| - | | ::: | N 次剩余 || | - | | | + | | ::: | N 次剩余 || √ | | | |
| - | | ::: | 任意模数 N 次剩余 || - | - | - | | + | | ::: | 任意模数 N 次剩余 || √ | | | |
| - | | 欧几里得 | 扩展欧几里德 || Y | Y | Y | | + | | 欧几里得 | 扩展欧几里德 || | | √ | |
| - | | ::: | 二元一次不定方程求解 || Y | Y | Y | | + | | ::: | 类欧几里得 || √ | | | |
| - | | ::: | 类欧几里得 || Y | | Y | | + | | 置换群 | Burnside 引理 || √ | √ | √ | |
| - | | 置换群 | Burnside 引理 || | | | | + | | ::: | Pólya 定理 || √ | √ | √ | |
| - | | ::: | Pólya 定理 || | | | | + | | 反演 | Mobius 反演 || √ | √ | | |
| - | | 反演 | Mobius 反演 || | 看一次忘一次 | | | + | | ::: | 二项式反演 || ？ | ？ | ？ | |
| - | | ::: | 二项式反演 || | | | | + | | ::: | Stirling 反演 || ？ | ？ | ？ | |
| - | | ::: | Stirling 反演 || | | | | + | | ::: | Lagrange 反演 || ？ | ？ | ？ | |
| - | | ::: | Lagrange 反演 || | | | | + | | 筛法 | 线筛积性函数 || | √ | | |
| - | | 筛法 | 线筛积性函数 || Y | Y | | | + | | ::: | 杜教筛 || √ | √ | √ | |
| - | | ::: | 杜教筛 || Y | Y | | | + | | ::: | 洲阁筛 || √ | √ | √ | |
| - | | ::: | 洲阁筛 || | | | | + | | ::: | min_25 筛 || √ | √ | √ | |
| - | | ::: | min_25 筛 || | | | | + | | 矩阵 | 高斯消元 | 异或方程组 | | √ | | |
| - | | 矩阵 | 高斯消元 | 异或方程组 | Y | Y | Y | | + | | ::: | ::: | 求行列式 | | √ | | |
| - | | ::: | ::: | 求行列式 | | 学过 | | | + | | ::: | ::: | 辗转相除法高斯消元 | | √ | | |
| - | | ::: | ::: | 辗转相除法高斯消元 | | | | | + | | ::: | 特征值与特征方程 || | | √ | |
| - | | ::: | 特征值与特征方程 || | 学过 | | | + | | ::: | 矩阵的逆 || √ | | | |
| - | | ::: | 矩阵的逆 || | Y | | | + | | 排列组合 | Stirling 数 || √ | √ | √ | |
| - | | 排列组合 | Stirling 数 || | | | | + | | ::: | 扩展 Lucas 定理 || √ | √ | √ | |
| - | | ::: | Lucas 定理 || Y | Y | Y | | + | | 容斥原理 | min-max 容斥 || | | √ | |
| - | | ::: | 扩展 Lucas 定理 || | | Y | | + | | Fibonacci 数列 | 相关性质 || √ | √ | √ | |
| - | | 容斥原理 | 递推容斥系数计算 || | Y | | | + | | ::: | 皮萨诺周期 || √ | | | |
| - | | ::: | min-max 容斥 || | | Y | | + | | 博弈论 | Nim 游戏 | 各种 Nim 游戏有待补充 | | | √ | |
| - | | Fibonacci 数列 | 相关性质 || | | | | + | | ::: | SG 函数 / SG 定理 || （题） | | | |
| - | | ::: | 皮萨诺周期 || | | | | + | | ::: | 纳什均衡 || （题） | | | |
| - | | 博弈论 | Nim 游戏 | 各种 Nim 游戏有待补充 | Y | Y | Y | | + | | ::: | 威佐夫博弈 || （题） | | | |
| - | | ::: | SG 函数 / SG 定理 || | Y | | | + | | ::: | 不平等博弈 / Surreal Number || （题） | | | |
| - | | ::: | 纳什均衡 || | | | | + | | 杂项 | 威尔逊定理 || √ | | | |
| - | | ::: | 威佐夫博弈 || | | | | + | | ::: | Ramsey 定理 || | (内容) | | |
| - | | ::: | 不平等博弈 / Surreal Number || | | | | + | | ::: | 棋盘多项式 || ？ | ？ | ？ | |
| - | | 杂项 | 威尔逊定理 || | | | | + | | ::: | Catalan 数 || √ | | | |
| - | | ::: | 鸽笼原理 || Y | Y | Y | | + | |
| - | | ::: | Ramsey 定理 || | | | | + | |
| - | | ::: | 棋盘多项式 || | | | | + | |
| - | | ::: | Catalan 数 || | | | | + | |
| ===== 数据结构 ===== | ===== 数据结构 ===== | ||
| ^ 知识点 ^^^ 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.1597152642.txt.gz · 最后更改: 2020/08/11 21:30 由 2sozx
