0%

Outline

发表于 2022-01-23 更新于 2022-05-07 分类于纲要

纲要

随便列一下吧。

一、数据结构

基础数据结构
- 线段树
  - zkw 线段树写得很潦草。。。
  - 扫描线 P5490 P1856
  - 动态开点线段树 CF803G P3960
  - 线段树合并 P4556
  - 线段树分裂 P5494
  - 线段树分治 P5787
  - 线段树优化建图 CF786B
  - 李超线段树 P4097
- 树状数组
  - 树状数组上二分（倍增）P6619
- ST 表
进阶数据结构
- 可并堆
  - 左偏树 P3377
- 平衡树 P6136
  - Splay
  - FHQ-Treap
- 可持久化数据结构
  - 可持久化线段树与主席树（可持久化权值线段树）P3834
  - 可持久化Trie
  - 可持久化可并堆（左偏树）
  - 可持久化平衡树（FHQ-Treap）P3835
- 树套树
  - 线段树套线段树 P3380
  - 线段树套平衡树
  - 树状数组套主席树
- 动态树
  - LCT P3390
- K-D 树 P4357
根号算法
- 分块
  - 操作分块
  - 根号分治
  - 根号重构
  - 静态询问分块
  - 动态带修分块
- 莫队
  - 普通莫队 P1494
  - 回滚莫队
  - 带修莫队
  - 莫队二次离线
一些技巧
- 珂朵莉树
- 均摊科技 CF1638E

二、数学

数论
- 裴蜀定理、欧几里得算法
- 中国剩余定理 P1495
- Lucas 定理 P3807
- 欧拉定理
  - 费马小定理
  - 乘法逆元 $O(\log p)$
- 线性求逆元 P3811
- Miller-Rabin（同在 P4718）
- Pollard-rho P4718
- BSGS P3846 P4195
- 阶与原根（见本博客 Basis 一文）
- 数论分块 UVA11526 P2261
- 狄利克雷卷积与莫比乌斯反演自己写的一点东西
- 杜教筛 P4213
- 贝尔级数 U214268
- 狄利克雷生成函数（DGF）
- PN 筛 PN
- Min_25 筛（下划线不要打错。。。）
- whzzt 筛
- 二次剩余 P5491
组合计数。。。
- 基础组合恒等式
- 组合结构符号化
- 斯特林数
- 容斥
- 生成函数
  - OGF，EGF
  - 多元生成函数
- 伯努利数
代数
- 多项式算法
  - 拉格朗日插值 P4781
  - FFT，NTT P3803
  - MTT（不会）
  - FMT，FWT P4717
  - 多项式全家桶 Polynomial Industry
  - 其他多项式操作（不会）
  - 常系数齐次线性递推（EI 的一种新的线性递推计算方法）
- 高斯消元 P4035
- 线性基 P3812
博弈论
- SG 函数
- 非公平博弈
杂项（高等数学、近世代数、线性代数）
- 概率期望
  - 鞅、停时定理与势能函数
- 群论
- 微积分
  - 辛普森方法
- 线性规划
  - 单纯形算法

三、图论

Tarjan
- 割边，割点
- e-DCC（无向图边双连通分量）
- v-DCC（无向图点双连通分量）
- SCC（有向图强连通分量） P3387
- 2-SAT
- 圆方树
二分图
- 二分图最大匹配 P3386
  - 增广路算法
  - 最大流建模
- 二分图最大带权匹配
  - 匈牙利算法
  - 费用流建模
- 二分图最小点覆盖
- 二分图最大独立集
- DAG 最小边覆盖
生成树
- Boruvka 算法
- Kruskal 重构树
- wqs 二分
- 最小斯坦纳树
- 矩阵树定理
- 最小树形图
  - 朱-刘算法
  - DMST 算法
最短路
- 负环 P3385
- 差分约束 P1993
- k 短路
- 最短路建模
网络流
- 最大流 P3376，最小割，费用流 P3381
- 上下界网络流
- 最大权闭合子图
- 平面图最小割 P4001
- 最小割树
- 全局最小割
弦图
其他
- 欧拉路与哈密顿路
- 基环树
- 树的直径
- 树的重心
- 支配树
- 全局最小割
- 最小割树
- 一般图最大匹配
  - 带花树算法
- Prufer 序列
- Burnside 引理与 Polya 定理

四、动态规划

线性 DP
- 分组 DP P3188
- 背包 P5289
区间 DP P5336
概率期望 DP P6835
树形 DP P2607
DAG 上 DP P4316
数位 DP P2657
数据结构优化 DP
- 线性数据结构优化 P2254
- 线段树优化 P6647
- 可并堆优化 P1552
- 分治优化
状压 DP
- 插头 DP P5056
斜率优化 P3195
四边形不等式优化 Quadrangle
矩阵表示 DP
- 矩阵快速幂 P3390
- 数据结构优化
生成函数优化 DP P4389

五、计算几何

计算几何基础
- 向量、点积、正弦定理、余弦定理、平面几何基础
- 线段、射线、直线相交判定，求交点
- 圆与直线交点，圆与圆交点
凸包、半平面交
- 二维凸包
- 求半平面交
- 判断点是否在凸包/半平面交内
- 旋转卡壳
- 凸包的闵可夫斯基和
- *动态凸包
杂项
- *圆反演
- 平面最近点对
- 最小圆覆盖
- 三角剖分
- *三维凸包

六、字符串

Hash
Trie
KMP P3375
- Ex KMP P5410
AC 自动机 P3808
后缀数组 P3809
后缀自动机 P3804
Manacher P3805
回文自动机
Lyndon Word
Runs

七、杂项

一些技巧
- 基础类
  - 边带权、扩展域、可撤销（并查集技巧）
  - 三元环计数 P1989
  - 指针动态分配内存（可以参照长链剖分的代码）
  - 动态 DP
  - 贪心。。。
  - STL
    - set P3792
    - map 与 unorded_map
    - bitset
    - algorithm
      - unique
    - priority_queue
      - 懒惰删除法（一般 Dijkstra 的板子应该都用的是这种方法，吧？）
  - 小学数学基础愿者上钩
- 分治类
  - 三分法 P3382
  - 分数规划 P4377
  - 二维分治
  - CDQ 分治 P3157
  - 整体二分
  - 分治转移斜率优化
  - 树分治
    - 点分治
    - 点分树
- 树类
  - 树链剖分 P3384
  - 启发式合并 CF741D
  - 长链剖分 CF1009F
  - 虚树 P2495
- 倍增类
  - 倍增答案
  - 环上倍增 P4155
- 骗分类（非常重要）
  - 模拟退火 P3959
  - 随机化技巧
- 理论基础类
  - 时间复杂度分析（主定理，但是定积分更重要。。。） Master Theorem
- 技术类
  - 对拍
  - 卡常 Constant Skill
  - GDB（附在 NOI Linux 使用里）
  - Linux 使用 NOI Linux
特殊题型
- 提交答案题
- 交互题
- 构造题