NOI知识点总结

OI&ACM, 总结
  1. 1 图
  2. 2 树
  3. 3 算法
  4. 4 字符串
  5. 5 数学

1 图

  1. 最短路
  2. kruskal树
  3. 网络流
  • 最大流&最小割(Dinic)
  • 费用流(SPFA)
  1. 缩环、强连通分量(Tarjan)
  2. 差分约束(SPFA)
  3. 拓扑排序(Top sort)
  4. 二分图匹配(最大流)

2 树

  1. 带权并查集
  2. 线段树(二维)
  3. 树链剖分、树套树
  4. Splay、SBT、Treap
  5. 动态树
  6. ☆主席树(可持续化数据结构)(注意空间)
  7. 哈夫曼树

3 算法

  1. ☆DP
  • ☆优化：单调队列、斜率、矩阵
  • ☆树形
  • 状压
  • 区间
  • 数位
  • ※插头
  1. A* IDA*
  2. 三分
  3. ☆分块
  4. ※莫队算法
  5. ※模拟退火

4 字符串

  1. Hash
  2. KMP + Tire --> AC自动机
  3. 后缀数组

5 数学

  1. 博弈论
  • 转移图
  • Nim游戏
  1. 组合数学(burnside引理)
  2. 莫比乌斯反演
  3. 计算几何(凸包)
  4. 矩阵(线性代数)
  5. 概率、数学期望