NOI知识点总结

  1. 1 图
  2. 2 树
  3. 3 算法
  4. 4 字符串
  5. 5 数学

NOI知识点

1 图

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

2 树

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

3 算法

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

4 字符串

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

5 数学

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