zcmimi's blog

数据结构

    • 单调栈
  • 队列

    • 单调队列
    • 优先队列
    • 双端队列
    • 二叉堆
    • 可并堆
      • 左偏树
      • 配对堆
      • 斐波那契堆
  • 并查集

    • 路径压缩
    • 按秩合并
    • 可持久化并查集
  • 线段树

    • 区间加
    • 区间乘
    • 主席树
    • 标记永久化
  • 树状数组

    • 区间加单点查
    • 区间加区间查
  • st表(rmq)

  • 平衡树
    • treap
    • fhqtreap
    • splay
    • SBT
    • 替罪羊树
  • kd-tree
  • link-cut tree
  • 树套树
    • 线段树套平衡树
    • 线段树套线段树
  • 笛卡尔树

字符串

  • kmp
    • exkmp
  • hash
  • trie
  • AC自动机
    • fail树
  • 后缀数组SA
  • 后缀树SAM
  • manacher
  • 回文自动机

数论

  • 快速幂 & 慢速乘
  • 质数
    • 暴力判断
    • miller-rabbin
    • 筛质数
      • 埃筛
      • 欧拉筛
    • 分解质因数
  • gcd
    • exgcd
  • 费马小定理
  • 逆元
    • 线性求逆元
    • 费马小定理求逆元
    • exgcd求逆元
  • crt
    • excrt
  • 矩阵
    • 矩阵乘法
    • 矩阵快速幂
    • 矩阵求逆
  • 行列式
  • 组合数
    • 杨辉三角
    • lucas
      • exlucas
  • bsgs
    • exbsgs
  • 欧拉函数
    • 线性筛欧拉函数
    • 欧拉定理
  • 狄利克雷卷积
  • 莫比乌斯函数
    • 莫比乌斯反演
  • 概率和期望
  • 高斯消元
  • 线性基
  • 数列
    • 斐波那契数列
    • 卡特林数
    • 斯特林数
      • 第一类斯特林数
      • 第二类斯特林数
  • Polya定理
  • 置换群
  • 原根
  • 快速傅里叶变换(FFT)

    • 离散傅里叶变换(DFT)
    • 离散傅里叶逆变换(IDFT)
    • 快速数论变换(NTT)
    • 快速傅里叶变换的优化版(FNTT)
    • 快速沃尔什变换(FWT)
    • 任意模数FFT(MTT)
    • 快速莫比乌斯变化(FMT)
  • 拉格朗日

    • 拉格朗日插值
    • 拉格朗日乘子法
    • 拉格朗日四平方和定理
  • 线性规划 </details>

动态规划

  • 线性dp
  • 背包dp
    • 01背包
    • 完全背包
    • 多重背包
      • 二进制优化多重背包
  • 区间dp
  • 状压dp
  • 树形dp
    • 基环树dp
  • DAG上dp
  • 多维dp
  • 期望dp
  • 数位dp
  • 动态dp
  • dp的优化
    • 数据结构优化dp
      • 线段树优化dp
      • 单调队列优化dp
    • 斜率优化
    • 决策单调性

树论

  • 生成树
  • LCA
    • 树链剖分
      • 树链剖分换根
    • 倍增
    • tarjan离线
  • 虚树
  • 基环树
  • 树链剖分
    • 重链剖分
    • 实链剖分
    • 长链剖分
  • dfs序
    • 欧拉序
  • 树分治
    • 点分治
      • 树的直径
      • 树的重心
    • 动态点分治
    • 静态链分治
  • 树上倍增
  • 树分块
  • link-cut tree
  • top tree
  • zip tree

图论

  • 最短路
    • spfa
      • 判断负环
      • 堆优化
    • dijkstra
      • 堆优化
      • 线段树优化
    • floyed
      • 倍增floyed
    • k短路
    • 差分约束
  • tarjan
    • 强连通分量(缩点)
    • 双连通分量
    • 割点,割边,桥
    • 2-sat
  • 拓扑排序
  • 二分图
    • 匈牙利
    • 网络流
    • KM
  • 网络流

    • 最大流(最小割)
      • dinic
      • isap
    • 最小费用最大流
      • spfa费用流
      • zkw费用流
    • 有上下界的网络流
    • 数据结构优化网络流
    • 分数规划
  • 欧拉图

  • 区间图与弦图
  • 平面图与对偶图
  • 最小树形图
  • 仙人掌
    • 动态仙人掌

STL

  • map
    • unordered_map
  • set
    • multiset
  • stack
  • queue
  • deque
  • priority_queue
  • vector
  • list
  • bitset

搜索

  • dfs
  • bfs
    • 双向bfs
  • A*
  • IDA*
  • DLX
  • 记忆化搜索
  • 剪枝
  • 模拟退火
  • 爬山算法
  • 随机化

计算几何

  • 向量
    • 点积
    • 叉积
  • 凸包
  • 旋转卡壳
  • 扫描线 </details>

其他算法与思想

  • 二分

    • 三分
    • 整体二分
    • 01分数规划
  • 倍增

  • 贪心
  • 枚举
  • 暴力
  • 模拟
  • 分治
    • cdq分治
    • 线段树分治
  • 离散化
  • meet in the middle
  • 排序
    • 快速排序
    • 归并排序
      • 求逆序对
    • 桶排
    • 基数排序
    • 计数排序
    • 堆排序
  • 分块
  • 随机化
  • 前缀和
    • 二维前缀和
  • 高精度
    • 压位
  • 递推
    • 矩阵加速递推
  • 位运算
  • 莫队
    • 树上莫队
    • 带修莫队
  • 打表
  • 老司机树
OI知识点思维导图
comment评论
Search
search