2018-team4-modules-index

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

1. 动态规划

2. 莫队算法

3. 数据结构

    * 3.1 Hash (HDU p16 字符串、矩阵Hash)
    * 3.2 [wiki:2018-team4-modules-ST ST] 无修改的区间最大值查询
    * 3.3 [wiki:2018-team4-modules-左偏树 左偏树] 可以合并的堆
    * 3.4 平衡树
       * 3.4.1 [wiki:2018-team4-modules-Treap Treap] 
       * 3.4.2 [wiki:2018-team4-modules-非旋Treap 非旋Treap] 
       * 3.4.3 [wiki:2018-team4-modules-替罪羊树 替罪羊树] 达到一定条件后重建子树
    * 3.5 线段树
        * 3.5.1 [wiki:2018-team4-modules-普通线段树 普通线段树] 区间操作最大、求和
        * 3.5.2 [wiki:2018-team4-modules-可持久化线段树 可持久化线段树] 区间修改，区间查询
        * 3.5.3 [wiki:2018-team4-modules-线段树合并 线段树合并]
    * 3.6 [wiki:2018-team4-modules-树链剖分 树链剖分]树链剖分
    * 3.7 [wiki:2018-team4-modules-Splay Splay]
    * 3.8 [wiki:2018-team4-modules-LCT LCT] link-cut-tree
    * 3.9 TopTree (HDU P.20) 在LCT的基础上可以进行子树修改与查询
    * 3.10 [wiki:2018-team4-modules-并查集 并查集]
        * 3.10.1 可持久化并查集 (ZJU P.24) 可查询历史版本
    * 3.11 [wiki:2018-team4-modules-KDTree KDTree] 平面最远/最近点、k远点、二维区间权和

4. 树

    * 4.1 生成树
        * 4.1.1 最小生成树
        * 4.1.2 [wiki:2018-team4-modules-最小方差生成树 最小方差生成树]
        * 4.1.3 [wiki:2018-team4-modules-生成树计数 生成树计数](矩阵树定理)
    * 4.2 [wiki:2018-team4-modules-支配树 支配树]
    * 4.3 [wiki:2018-team4-modules-虚树 虚树]
    * 4.4 [wiki:2018-team4-modules-点分治 点分治]
    * 4.5 树上倍增lca

5. 图

    * 5.1 最短路
        * 5.1.1 dijkstra
        * 5.1.2 SPFA
    * 5.2 有环图
        * 5.2.1 [wiki:2018-team4-modules-有向图极大强连通分量(Tarjan) 有向图极大强连通分量(Tarjan)]
        * 5.2.2 [wiki:2018-team4-modules-有向图极大强连通分量(Kosaraju) 有向图极大强连通分量(Kosaraju)]
        * 5.2.3 点双联通分量
        * 5.2.4 边双联通分量
        * 5.2.5 [wiki:2018-team4-modules-割点 割点]
        * 5.2.6 桥
    * 5.3 匈牙利算法
    * 5.4 [wiki:2018-team4-modules-完美消除序列 完美消除序列]
    * 5.5 网络流
        * 5.5.1 [wiki:2018-team4-modules-最大流/最小割 最大流/最小割]
        * 5.5.2 [wiki:2018-team4-modules-费用流 最小/大费用最大流]
        * 5.5.3 [wiki:2018-team4-modules-最大费用可行流 最大费用可行流]
        * 5.5.4 [wiki:2018-team4-modules-无原汇上下界可行流 无原汇上下界可行流]
        * 5.5.5 [wiki:2018-team4-modules-有原汇上下界费用流 有原汇上下界费用流]
    * 5.6 [wiki:2018-team4-modules-一般图最大匹配 一般图最大匹配]
    * 5.7 2-SAT
        * 5.7.1 判定是否存在解
        * 5.7.2 求任意一组解
        * 5.7.3 [wiki:2018-team4-modules-求字典序最小解 求字典序最小解]
    * 5.8 [wiki:2018-team4-modules-查分约束系统 查分约束系统]
    * 5.9 [wiki:2018-team4-modules-Hall定理 Hall定理]
    * 5.10 最小树形图
    * 5.11[http://10.71.10.90:81/svn/filedetails.php?repname=acmsvn&path=%2Fmodule%2F%E5%9B%BE%E8%AE%BA_%E5%8C%B9%E9%85%8D%2F%E4%BA%8C%E5%88%86%E5%9B%BE%E6%9C%80%E4%BD%B3%E5%8C%B9%E9%85%8D%28kuhn_munkras%E9%82%BB%E6%8E%A5%E9%98%B5%E5%BD%A2%E5%BC%8F%29.cpp 二分图最佳匹配 KM算法]

6. 博弈论

7. 数学
    * 7.1 [wiki:2018-team4-modules-线性递推逆元 线性递推逆元]
    * 7.2 [wiki:2018-team4-modules-线性筛质数 线性筛质数]
    * 7.3 组合数取模
        * 7.1.1 [wiki:2018-team4-modules-Lucas定理 Lucas定理]
        * 7.1.2 P是质数的幂
    * 7.4 中国剩余定理
    * 7.5 高斯消元
        * 7.5.1 线性方程求解
        * 7.5.2 行列式
    * 7.6 康托展开
    * 7.7 线性基
    * 7.8 多项式
        * 7.8.1 快速傅里叶变换(FFT)
        * 7.8.2 快速数论变换1(NTT)
        * 7.8.3 [wiki:2018-team4-modules-快速数论变换2(NTT) 快速数论变换2(NTT)]
        * 7.8.4 多项式求幂
        * 7.8.5 多项式求exp
        * 7.8.6 多项式求逆元
        * 7.8.7 拉格朗日反演
    * 7.9 二项式反演
    * 7.10 数列
        * 7.10.1 [wiki:2018-team4-modules/BM Berlekamp-Massey]给前n项求递推式
    * 7.11 [wiki:2018-team4-modules-拉格朗日插值 拉格朗日插值]

8. 字符串匹配

    * 8.1 [wiki:2018-team4-modules-kmp kmp]
    * 8.2 [wiki:2018-team4-modules-AC自动机 AC自动机]
    * 8.3 [wiki:2018-team4-modules-Trie Trie]
    * 8.4 自动机
       * 8.4.1 [wiki:2018-team4-modules-后缀自动机 后缀自动机]
       * 8.4.2 [wiki:2018-team4-modules-回文自动机 回文自动机]
    * 8.5 [wiki:2018-team4-modules-后缀数组 后缀数组]

9. 随机化

10. 计算几何

 * 10.1 [http://10.71.10.90:81/svn/filedetails.php?repname=acmsvn&path=%2Fmodule%2F%E5%87%A0%E4%BD%95%2Fgeo.cpp geo2d] (ZJU p19) 码短易用c风格，有线段和多边形、凸包相关的大多数东西以及多边形切割、圆与线段交、费马点
 * 10.2 [http://10.71.10.90:81/svn/filedetails.php?repname=acmsvn&path=%2Fmodule%2F%E5%87%A0%E4%BD%95%2Fgeo3d.cpp geo3d] (ZJU p24) 风格同上，3d版本，主要是线段点和平面，比[http://10.71.10.90:81/svn/filedetails.php?repname=acmsvn&path=%2Fmodule%2F%E5%87%A0%E4%BD%95%2F%E4%B8%89%E7%BB%B4%E5%87%A0%E4%BD%95.cpp P28]要好用 
 * 10.3 [http://10.71.10.90:81/svn/filedetails.php?repname=acmsvn&path=%2Fmodule%2F%E5%87%A0%E4%BD%95%2Fgeo%28%E7%8C%9B%E7%8A%B8%E4%B9%9F%E9%92%BB%E5%9C%B0%29.cpp geo猛犸] (ZJU p7) 相对cpp一点，处理圆比较方便，有内接外切最小圆覆盖；~~三维凸包simple~~；
 * 10.4 geoHDU (HDU p89) 二次方程，旋转，多边形交圆
 * 10.5 几何公式 (ZJU p5)
 * 10.6 半平面交 (HDU p84)
 * 10.7 三维凸包pro (HDU p86) 你甚至可以求表面积体积重心
 * 10.8 [http://10.71.10.90:81/svn/filedetails.php?repname=acmsvn&path=%2Fmodule%2F%E5%87%A0%E4%BD%95%2F%E4%BB%BB%E6%84%8F%E7%BB%B4%E7%A9%BA%E9%97%B4%E6%9C%80%E8%BF%91%E7%82%B9%E5%AF%B9.cpp 任意维空间最近点对] (ZJU p38)
 * 10.9 [http://10.71.10.90:81/svn/filedetails.php?repname=acmsvn&path=%2Fmodule%2F%E5%87%A0%E4%BD%95%2F%E7%BD%91%E6%A0%BC%28pick%29.cpp 网格(pick)] (ZJU p45)
 * 10.10 [http://10.71.10.90:81/svn/filedetails.php?repname=acmsvn&path=%2Fmodule%2F%E5%87%A0%E4%BD%95%2F%E5%9C%86%E5%B9%B6.cpp K圆并] (ZJU p42 ~~HDU p93~~)
 * 10.11 曼哈顿（空间下的）凸包 (HDU p93)
 * 10.12 平面图求域及点定位 (HDU p94)
 * 10.13 Farmland （给一个平面图，找边数为k且内部不包含其他点的简单多边形的个数）待写
 * 10.14 [wiki:2018-team4-modules-旋转卡壳 旋转卡壳]

11. 黑科技与杂项

    * 11.1 [wiki:2018-team4-modules-读入优化 读入优化]
    * 11.2 输出优化

12. Java

1. 动态规划

2. 莫队算法

3. 数据结构

4. 树

5. 图

6. 博弈论

7. 数学

8. 字符串匹配

9. 随机化

10. 计算几何

  • 10.1 geo2d (ZJU p19) 码短易用c风格，有线段和多边形、凸包相关的大多数东西以及多边形切割、圆与线段交、费马点
  • 10.2 geo3d (ZJU p24) 风格同上，3d版本，主要是线段点和平面，比P28要好用
  • 10.3 geo猛犸 (ZJU p7) 相对cpp一点，处理圆比较方便，有内接外切最小圆覆盖；三维凸包simple；
  • 10.4 geoHDU (HDU p89) 二次方程，旋转，多边形交圆
  • 10.5 几何公式 (ZJU p5)
  • 10.6 半平面交 (HDU p84)
  • 10.7 三维凸包pro (HDU p86) 你甚至可以求表面积体积重心
  • 10.8 任意维空间最近点对 (ZJU p38)
  • 10.9 网格(pick) (ZJU p45)
  • 10.10 K圆并 (ZJU p42 HDU p93)
  • 10.11 曼哈顿（空间下的）凸包 (HDU p93)
  • 10.12 平面图求域及点定位 (HDU p94)
  • 10.13 Farmland （给一个平面图，找边数为k且内部不包含其他点的简单多边形的个数）待写
  • 10.14 旋转卡壳

11. 黑科技与杂项

12. Java