To Do List

提高算法

DP

• 线性 DP
• 区间 DP
  • 四边形不等式优化
• 划分 DP
• 简单优化
  • 单调队列
  • 单调栈
  • 其他数据结构（线段树等）
• 期望 DP
• 状压 DP
  • 枚举子集的复杂度是\(O(3^n)\)
  • 熟记各种位运算

  for(int S0 = S; S0; S0 = (S0 - 1) & S) {
    S1 = S0 ^ S;
    // S为原集合，S0为S的所有非空子集，S1为S0以S为全集时的补集
  }

• 计数 DP
• 数位 DP

字符串

• KMP
• 字典树（Trie）
• 哈希（Hash）
• AC 自动机

数据结构

• 线段树
• 树状数组
• 平衡树
• 分块

树上问题

• 树的直径
• 树的重心
  • 定义：最大的子树节点数最少
  • 求法：钦定点1为根，然后每个点为根的情况的所有子树就是以1为根时的子树和它之外的所有节点构成的子树
• 树上求 LCA（倍增或树链剖分皆可）
• 树上差分
• 基环树
• 树链剖分

图上问题

• Tarjan 和缩点 DP
  • 有向图/无向图Tarjan，割点，桥，点/边双联通分量
• 最小生成树
• 最短路问题
  • Floyd
  • Dijkstra
  • Bellman-Ford / SPFA
    • SPFA求负环
• 二分图匹配
• 差分约束

数学

• gcd 和 exgcd
• 乘法逆元
• 矩阵快速幂
• 组合计数与容斥原理
• 概率与期望
• 中国剩余定理
• 高斯消元
• 博弈论基本模型及SG函数

其他

• 搜索
• 贪心
• 二分
• STL

To Do List

原文：https://www.cnblogs.com/henry-1202/p/11342201.html