TODO - RogerRordo/ACM GitHub Wiki

  1. 二分/
  2. 排序
    1. 快排
    2. 堆排
    3. 计数排序
    4. 基数排序
    5. 桶排
  3. 搜索
    1. DFS/
    2. BFS
      1. 普通BFS/
      2. 双向BFS
    3. 记忆化搜索
    4. 启发式搜索
      1. 爬山算法
      2. 模拟退火
      3. 蚁群算法
      4. 遗传算法
  4. DP
    1. 背包（九讲）
      1. 01背包
      2. 完全背包
      3. 多重背包
      4. 混合背包（前三种）
      5. 二维费用背包
      6. 分组背包
      7. 有依赖的背包
    2. 最长不下降子序列
    3. 最长公共子序列/
    4. 插头DP
    5. 树形DP/
    6. 矩阵乘法优化
    7. 四边形不等式优化
    8. 单调队列优化
    9. 斜率优化
  5. 图
    1. 拓扑排序 O(V+E)
    2. 割点和桥
    3. 图的同构
    4. 最短路
      1. Dijkstra
        1. Dijkstra O(V^2 +E)
        2. Dijkstra+堆 O(ElogE +V)
      2. Floyd O(V^3 +E)
      3. SPFA
        1. SPFA O(VE +V^2)=O(kE)
        2. SPFA+SLF+LLL O(VE +V^2)=O(kE)
      4. 差分约束系统
      5. 第k短路
    5. 欧拉回路
      1. 普通欧拉回路
      2. 混合图欧拉回路_iSAP
    6. 哈密顿回路
    7. 匹配
      1. 二分图匹配
        1. 最大匹配_匈牙利 O(VE)
        2. 最大匹配_HK
        3. 最优匹配_KM
      2. 一般图匹配
        1. 带花树开花
    8. 强连通分量_Tarjan O(V+E)
    9. 2-SAT
    10. 网络流
      1. 最大流
        1. Ford-Fulkerson
        2. Edmonds Karp
        3. iSAP
          1. iSAP有BFS非递归+gap+cur O(V^2*E)
          2. iSAP无BFS递归+gap+cur O(V^2*E)
        4. Dinic
      2. 费用流
        1. 普通费用流
        2. ZKW费用流
      3. 上下界网络流
      4. 无向图最小割
        1. Stoer-Wagner
    11. 完美消除序列
    12. 弦图判定
    13. 最大团
    14. 极大团计数
    15. 01分数规划
  6. 树
    1. 哈夫曼树/
    2. 最小生成树
      1. Prim
        1. Prim邻矩 O(V^2)
        2. Prim
        3. Prim邻矩+堆 O(V^2)
        4. Prim+堆
      2. Kruskal O(ElogE +αE)
      3. 单度限制最小生成树
    3. 最小树形图
    4. 最优比例生成树
    5. 树的同构
    6. 树的直径
      1. 树的直径_BFS O(N)
      2. 树的直径_树形DP
    7. LCA&RMQ
      1. LCA_Tarjan O(αN+Q)
      2. RMQ_ST O(NlogN)~O(1)
      3. LCA-RMQ_ST/
      4. RMQ-LCA_Tarjan/
      5. RMQ-LCA_±1RMQ
      6. LCA-±1RMQ
    8. 树分治
      1. 树链剖分
      2. 点分治
      3. 边分治
    9. 虚树
    10. prufer编码
  7. 字符串
    1. 字符串Hash
    2. KMP
    3. 扩展KMP
    4. 环串的最小表示
    5. 后缀数组
    6. 最长重复字串
    7. 最长公共子串
    8. 最长回文子串_Manacher
    9. 多模匹配_AC自动机 O(∑P_i+T)
    10. 后缀自动机
  8. 高级数据结构
    1. 块状链表
    2. 并查集
    3. 堆
      1. 二叉堆
        1. 手写二叉堆
      2. 斐波那契堆
      3. 左偏树
      4. 配对堆
    4. 树状数组
      1. 区间和改点求段_树状数组 O(NlogN+QlogN)
      2. 区间和改段求点_树状数组 O(NlogN+QlogN)
      3. 区间和改段求段_树状数组
      4. 二维树状数组
    5. 线段树
      1. 区间和_线段树 O(NlogN+QlogN)
    6. 平衡树
      1. 二项堆
      2. 平衡树
      3. Treap
      4. SBT
      5. Splay树
    7. 动态树
    8. 后缀树
    9. k-d Tree
    10. 复合数据结构
      1. 区间k大无修改_主席树 O(NlogN+QlogN)
      2. 区间k大有修改_树状数组套主席树
      3. 线段树套线段树
      4. 线段树套平衡树
      5. 平衡树套线段树
  9. 数学
    1. 高精度
      1. FFT
      2. 高除单
      3. 高除高
    2. 矩阵乘法(矩阵快速幂)
    3. 矩阵的逆
    4. 高斯消元
    5. GCD_欧几里得/
    6. 扩展欧几里得
    7. 中国剩余定理
    8. 原根
    9. 平方剩余
    10. 离散对数
    11. N次剩余
    12. 线性筛素数 O(N)
    13. Miller-Rabin素数测试
    14. 欧拉函数
    15. 莫比乌斯反演
    16. Romberg数值积分
    17. 一元高次方程实根 O(N^3*S)
    18. Lucas定理
    19. 群论
    20. 拉格朗日乘子法
    21. 线性规划_单纯形法
    22. 辛普森积分
    23. 模线性方程组
    24. BSGS
      1. 普通BSGS
      2. 扩展BSGS
  10. 几何
    1. 最小圆覆盖 O(N)
    2. 半平面交
    3. 三维凸包
    4. 曼哈顿凸包
    5. pick定理
    6. 最小矩形覆盖
    7. 圆的面积并
    8. 多边形的面积并
    9. 多边形的核
  11. 博弈
  12. 其他
    1. 莫队
    2. 斐波那契进制转换
    3. 幻方构造
    4. N皇后构造
    5. 骑士周游
    6. 最大子矩阵和
    7. 矩形切割
    8. CDQ分治
    9. 开栈