OI Note 传送中心

发表于 分类于 ， 阅读次数：
算法竞赛大型攻略 by command_block 
已写作：82500 字（14%）        更新日期：2025.4.30

前言

  • 食用说明
  • 自序

数据结构

  • 1.1 二叉数据结构
    • 1.1.1 线段树
    • 1.1.2 平衡树
    • 1.1.3 K-Dimension Tree
  • 1.2 数据结构的调度
    • 1.2.1 CDQ 分治
    • 1.2.2 二进制分组
    • 1.2.3 线段树分治
    • 1.2.4 整体二分
    • 1.2.5 二区间合并（猫树分治）
  • 1.3 树上数据结构
    • 1.3.1 树的序列结构【全dfs序、换根】
    • 1.3.2 静态链剖分
    • 1.3.3 树分治
    • 1.3.4 动态树
  • 1.4 分块与平衡
    • 1.4.1 根号分块
    • 1.4.2 莫队
    • 1.4.3 根号分治和自然根号

图论

  • 2.1 基础算法
    • 2.1.1 最短路【差分约束，同余最短路】
    • 2.1.2 最小生成树【Kruskal 重构树】
    • 2.1.3 连通性与可达性【2-SAT】
    • 2.1.4 其他基础算法【拓扑排序，欧拉回路】
  • 2.2 树
    • 2.2.1 最近公共祖先【树上差分，全dfs序】
    • 2.2.2 树的重心
    • 2.2.3 树的直径
    • 2.2.4 虚树
  • 2.3 再论连通性与可达性
    • 2.3.1 广义圆方树
    • 2.3.2 支配树
    • 2.3.3 耳分解
  • 2.4 网络流
    • 2.4.1 网络流算法
    • 2.4.2 网络流和二分图经典模型
    • 2.4.3 模拟费用流

动态规划

  • 经典模型【DAG，记忆化搜索；区间 DP，排列 DP，树上 DP，状态压缩 DP，数位 DP】

  • 动态规划的优化【数据结构优化，矩阵表示，矩阵快速幂，动态 DP，斜率优化，决策单调性，WQS 二分】

数论

  • 整数与同余
    • 4.1.1 基本概念
    • 4.1.2 乘法逆元
    • 4.1.3 线性同余方程组
    • 4.1.4 组合数取模
    • 4.1.5 质因数分解
    • 4.1.6 离散对数与原根
    • 4.1.7 二次剩余
    • 4.1.8 杂项
    • 习题
  • 数论函数求和（上） | 数论函数求和（下）
    • 4.2.1 基本概念
    • 4.2.2 莫比乌斯反演
    • 4.2.3 整除
    • 4.2.4 常见积性函数
    • 4.2.5 高维变换
    • 4.2.6 杜教筛
    • 4.2.7 贝尔级数
    • 4.2.8 Powerful Number
    • 4.2.9 扩展埃氏筛
    • 4.2.10 多元积性函数
    • 习题

组合数学

  • 组合问题选讲

  • 博弈论

    • 8.1.1 基本概念
    • 8.1.2 SG 函数与 SG 和
    • 8.1.3 常见模型
    • 8.1.4 不平等博弈与超现实数

多项式

  • 多项式的计算（上） | 多项式的计算（下）
    • 6.1.1 多项式乘法
    • 6.1.2 多项式初等函数
    • 6.1.3 分治 FFT
    • 6.1.4 求值与插值
    • 6.1.5 拉格朗日反演
    • 6.1.6 转置原理
    • 6.1.7 多项式复合
    • 6.1.8 一元多项式的其他常见算法
    • 6.1.9 位运算卷积与集合幂级数
    • 6.1.10 多元多项式
  • 生成函数引入
    • 6.2.1 基本概念
    • 6.2.2 二项式系数
    • 6.2.3 简单组合恒等式 / 求和问题
    • 习题
  • 组合符号化（上） | 组合符号化（下）
    • 6.3.1 DP 中的卷积
    • 6.3.2 解析组合
    • 6.3.3 图计数选讲
    • 6.3.4 概率生成函数
    • 6.3.5 多元生成函数
    • 习题
  • 多项式和递推
    • 6.4.1 线性递推
    • 6.4.2 整式递推与 D-finite
    • 6.4.3 二维递推
    • （Todo：习题）

字符串

  • 从匹配到自动机
    • 7.1.1 KMP 算法【Border，Z 函数，失配树】
    • 7.1.2 AC 自动机
  • 后缀自动机
    • 7.2.1 后缀自动机的建立【利用后缀自动机构建后缀树】
    • 7.2.2 广义后缀自动机
    • 7.2.3 对称压缩后缀自动机
  • Border 与回文串
    • 7.3.1 再论 Border
    • 7.3.2 回文自动机
    • 7.3.3 回文 Border
  • 最小后缀
    • 7.4.1 潜在最小后缀
    • 7.4.2 Lyndon 串
  • Runs 与本原平方串
    • 7.5.1 The Runs Theorem
    • 7.5.2 本原平方串

字数统计：

1
2
3
4
5
6
7
8
数论函数求和（上）    8000
数论函数求和（下）    10700
多项式的计算（上）    14300
多项式的计算（下）    12700
生成函数引入         8600
组合符号化（上）      14500
组合符号化（下）      7100
多项式和递推         9300