CVBB ACM Team

这是本文档旧的修订版！

一、基础算法

模拟(Yuki)
递归与搜索
1. 深度优先搜索(Yuki)
2. 广度优先搜索(Yuki)
3. 启发式搜索(~~Yuki~~)
4. 迭代加深搜索(Yuki)
5. Min-Max搜索
6. Alpha-beta剪枝
7. 记忆化搜索(Yuki)
8. Meet_In_the_middle(Yuki)
排序算法
1. 插入排序(Yuki)
2. 归并排序(Yuki)
3. 快速排序(Yuki)
4. 桶排序(Yuki)
5. 用数据结构排序(Yuki)
贪心算法
1. Huffman编码及Huffman树
  1. K叉Huffman树
2. 区间覆盖问题及拓展(Yuki)
3. 思维性贪心
差分思想(Yuki)

二、图论

  1.图的存储
      a)邻接表（链式前向星）(Yuki)
      b)邻接矩阵(Yuki)
  2.图的路径问题
      a)Floyd算法(Yuki)
      b)BellMan-Ford算法及其优化(Yuki)
      c)Dijkstra算法(Yuki)
      d)K短路问题(Yuki)
      e)差分约束系统(<del>Yuki</del>)
  3.图的连通性
      a)并查集(Yuki)
      b)最小生成树
          i.Kruskal算法(Yuki)
          ii.Prim算法(Yuki)
      c)Tarjan算法
          i.割点和桥(Yuki)
          ii.强连通分量和双联通分量(Yuki)
      d)拓扑排序(Yuki)
      e)2-SAT
  4.回路问题
      a)Euler回路(Yuki)
      b)Hamiltonian回路
  5.平面图与对偶图
  6.无向图的三角形枚举
  7.Graph Realization Problem
      a)Graph Realization Problem
      b)Digraph Realization Problem
  8.V图
  9.图的匹配
      a)二分图最大匹配及拓展（Hungarian算法）(Yuki)
      b)二分图最优匹配及拓展（KM算法）(Yuki)
      c)一般图最大匹配及拓展（带花树算法）
  10.树的问题
      a)树的直径与重心(Yuki)
      b)最近公共祖先（LCA问题）
          i.倍增算法(Yuki)
          ii.Tarjan算法（离线）(<del>Yuki</del>)
          iii.树链剖分(Yuki)
          iv.RMQ算法(Yuki)
      c)树链剖分
          i.轻重链剖分(Yuki)
          ii.长链剖分
      d)树上差分(Yuki)
      e)虚树
      f)Dfs序与全Dfs序(Yuki)
  11.网络流
      a)最大流与最小割（dinic算法）(Yuki)
      b)费用流及拓展(Yuki)
      c)有上向界的网络流(Yuki)
      d)网络流各种模型(<del>Yuki</del>)

三、动态规划

  1.背包问题
      a)01背包问题(Yuki)
      b)完全背包问题(Yuki)
      c)多重背包(Yuki)
      d)树上背包问题(<del>Yuki</del>)
  2.状压DP
      a)旅行商问题
      b)子集DP(Yuki)
      c)插头DP(<del>Yuki</del>)
  3.区间DP(Yuki)
  4.数位DP(Yuki)
  5.Tree DP(<del>Yuki</del>)
  6.概率期望DP(Yuki)
  7.递推DP(Yuki)
  8.动态规划优化
      a)斜率优化(<del>Yuki</del>)
      b)决策单调性优化(<del>Yuki</del>)
      c)数据结构优化
          i.线段树优化DP(Yuki)
          ii.单调队列优化DP(Yuki)
          iii.四边形不等式优化DP(<del>Yuki</del>)

四、字符串

  1.哈希(Yuki)
  2.Trie树
      a)01字典树(<del>Yuki</del>)
  3.KMP算法与AC自动机(<del>Yuki</del>)
      a)拓展KMP算法(<del>Yuki</del>)
      b)最小表示法(<del>Yuki</del>)
  4.后缀树、后缀数据与后缀自动机(<del>Yuki</del>)
  5.Manacher算法、回文树算法与回文自动机(<del>Yuki</del>)

五、数据结构

  1.栈
      a)单调栈(Yuki)
  2.队列
      a)单调队列(Yuki)
  3.堆和优先队列(Yuki)
  4.树状数组(Yuki)
  5.线段树(Yuki)
      a)线段树优化建边(Yuki)
  6.左偏树
  7.平衡树
      a)Splay(Yuki)
      b)Treap(Yuki)
      c)替罪羊树(Yuki)
  8.动态树（Link-Cut Tree）(<del>Yuki</del>)
  9.链表
      a)块状链表
  10.分块与莫队(<del>Yuki</del>)
      a)树上分块(<del>Yuki</del>)
  11.可持久化数据结构
      a)主席树(Yuki)
          i.带修主席树(<del>Yuki</del>)
      b)可持久化数组(Yuki)
      c)可持久化并查集(<del>Yuki</del>)
      d)可持久化Trie(<del>Yuki</del>)
      e)可持久化Treap(<del>Yuki</del>)
  12.树套树(<del>Yuki</del>)

六、数学

  1.整除与剩余
      a)Euclid算法(Yuki)
          i.扩展Euclid算法(Yuki)
          ii.类Euclid算法
      b)中国剩余定理及拓展(<del>Yuki</del>)
      c)Lucas定理及拓展(<del>Yuki</del>)
      d)原根(<del>Yuki</del>)
      e)二次剩余
      f)离散对数
      g)N次剩余
  2.素数与函数
      a)素数判定(Yuki)
      b)素数筛法(Yuki)
      c)欧拉函数(Yuki)
      d)线性筛(<del>Yuki</del>)
      e)反演与Mobius反演(<del>Yuki</del>)
      f)杜教筛(<del>Yuki</del>)
      g)Min25筛
  3.线性代数
      a)矩阵
          i.高斯消元(<del>Yuki</del>)
          ii.矩阵的逆(<del>Yuki</del>)
          iii.矩阵快速幂(Yuki)
          iv.行列式(<del>Yuki</del>)
          v.Matrix-Tree
      b)常系数多项式齐次问题
      c)线性基
      d)BM算法
  4.多项式算法
      a)多项式乘法
          i.FFT(<del>Yuki</del>)
          ii.NTT(<del>Yuki</del>)
          iii.FWT
      b)多项式求逆(<del>Yuki</del>)
      c)多项式快速幂（倍增FFT）(<del>Yuki</del>)
      d)多项式开方
      e)多项式除法
  5.数值计算
      a)数值积分
      b)高阶代数方程求根
  6.概率与期望
  7.组合数学与容斥原理(<del>Yuki</del>)
  8.其他数学内容
      a)快速幂(Yuki)
      b)Catalan 数(Yuki)
      c)Fermat定理
      d)第一类与第二类Stirling 数(Yuki)
  9.生成函数
      a)指数型生成函数(<del>Yuki</del>)
      b)普通型生成函数(<del>Yuki</del>)
  10.置换群论

七、分治算法

  1.二分算法(Yuki)
      a)整体二分(Yuki)
  2.三分算法(Yuki)
  3.第K大数(Yuki)
  4.偏序问题（CDQ分治）(<del>Yuki</del>)
  5.点分治(Yuki)

八、计算几何

  1.线段相交问题(<del>Yuki</del>)
  2.凸多边形面积(<del>Yuki</del>)
  3.最小圆覆盖(<del>Yuki</del>)
  4.扫描线(<del>Yuki</del>)
  5.凸包问题(<del>Yuki</del>)
  6.最近点对问题(<del>Yuki</del>)
  7.圆的交与并
  8.半平面交(<del>Yuki</del>)
  9.Simpson积分
  10.KD-Tree(<del>Yuki</del>)

九、博弈论问题

  1.基于动态规划的博弈论问题(<del>Yuki</del>)
  2.Nim博弈问题
      a)Sg函数(<del>Yuki</del>)
      b)反Nim博弈(<del>Yuki</del>)
  3.Wythoff博弈问题(<del>Yuki</del>)
  4.Surreal Number博弈

十、其他算法

  1.朱-刘算法
  2.无向图最小割
  3.高精度(Yuki)
  4.模拟退火
  5.随机化算法
  6.倍增算法(Yuki)
  7.bitset压位

CVBB ACM Team

用户工具

站点工具

页面工具