OI 知识点汇总

OI 知识点总结（并不

算法基础

贪心

局部最优 = 全局最优

• P1080 国王游戏
• P2123 皇后游戏 √

二分

适用于有单调性的问题

01 分数规划

类似最小化/最大化 $\frac{\sum_e e.a}{\sum_e e.b}$ 的问题

二分一个答案 ans，看是否任意情况下都满足 $\frac{\sum_e e.a}{\sum_e e.b}\ge ans$

移项可得 $\sum_e e.a-e.b\cdot ans\ge 0$，可通过贪心策略判断

若满足，则二分的 ans 大于等于最终要求的 ans；反之亦然

• P1642 规划
• P6074 最小路径
• LOJ149 01 分数规划
• P3288 方伯伯运椰子 √

倍增

使用 $log$ 的空间代价把时间降为 $log$

倍增降低时间复杂度

• P1081 开车旅行 √
• P1084 疫情控制 √
• P5648 Mivik 的神力 √

倍增处理静态 RMQ 问题

• P3865 ST 表
• P2471 降雨量

搜索

朴素暴力

• P1219 八皇后 √
• P3958 奶酪 √

A*

带估价函数的启发式暴力

• P2324 骑士精神
• P1379 八数码难题 √

迭代加深

对于不确定深度的搜索，每次加深迭代层数

• UVA12558 埃及分数

分治

• COCI 2014-2015 #2 norma √

线段树分治

把询问对应到线段树上的时间区间

• P5787 模板 √
• CF813F Bipartite Checking √

---

图论

最小生成树

图中权值和最小的子树

• P2820 局域网
• POJ2395 Out of Hay

次小生成树

基本思路是建出任意一个最小生成树，随后对于一条权值最小的非树边将其加入到树中，并删去新形成的环上权值最大的边

• P4180 严格次小生成树 √

最短路

	Floyd	SPFA	Dijkstra	Johnson
解决问题	全源最短路	单源最短路	单源最短路	全源最短路
限制	无负环	任意	无负边	无负环
时间复杂度	$O(n^3)$	$O(nm)$	$O(m\log m)$	$O(nm\log m)$

• P1144 最短路计数
• P6833 雷雨 √

Kruskal 重构树

模拟 Kruskal 建最小生成树过程建出一棵树，任意两点之间在最小生成树上边权的最小/最大值为两点 LCA 的权值

• LOJ137 最小瓶颈路
• P4768 规程 √

斯坦纳树

一类连通性的状压 DP

• P6192 模板
• P4294 游览计划 √

最小树形图

有向图最小生成树，使用朱刘算法

• P4716 模板

差分约束

处理一系列 $x_i$ 之间的（带 bias 的）不等关系

• P3275 糖果 √
• P2474 天平

K 短路

首先建出最短路树，然后对于每一条非树边将选择它后的权值加入到可并堆中，用大根堆维护当前最短路，重复 K 次；其中要使用可持久化可并堆来合并可选的非树边，时间复杂度 $O((n + K) \log m)$

• P2483 魔法猪学院 √
• HDU5960 Subsequence √

2-SAT

将每个条件拆成两个点然后用图论方式解决

• P4782 模板 √
• HDU3062 Party

欧拉路径/回路

先行条件：图连通

	欧拉路径	欧拉回路
无向图	只有两个点或没有点度数为奇数，其他点度数全为偶数	全部点的度数都为偶数
有向图	有一个点 出度 = 入度 + 1 且存在另一个点 入度 = 出度 + 1 ，其他点全部入度等于出度；或全部点都满足 入度 = 出度	全部点都满足 入度 = 出度

• LOJ10106 单词游戏 √
• P1341 无序字母对

哈密顿路径/回路

哈密顿路径添加一个超级点向所有点连边即转化为哈密顿回路

数据范围较小时，哈密顿回路可以用 $O(n^2\cdot2^n)$ 的状压 dp 解决；数据范围稍大可以用玄学优化 dfs，每次对一个点选择有效出边最多的出点优先 dfs，能在比较短的时间内找出图中的哈密顿回路（如果没有哈密顿回路时间复杂度依然为 $n!$）

• POJ2288 Islands and Bridges

网络流

最大流 = 最小割

最小费用最大流只需要在原来的基础上优先选择费用总和最小的进行增广

• 网络流 24 题
• P3159 交换棋子 √

点分治

每次找到重心然后分治，$O(n\log n)$

• P3806 模板 √
• P5311 成都七中 √

---

动态规划

把问题转换为多个性质类似的子问题

背包问题

01 背包

• P1048 采药 √

完全背包

• P1616 疯狂的采药

多重背包

把每个物品的数量二进制拆分即可

• POJ1276 Cash Machine

分组背包

• P1757 通天之分组背包

有依赖的背包

将（选取父节点，选 K 个子节点）作为一个组中的元素，套用分组背包

• P1064 金明的预算方案

区间 dp

$dp_{l,r}，枚举中点转移，复杂度 $O(n^3)$

• P5189 ZUMA √
• POJ3178 Roping the Field √

树形 dp

• P1352 没有上司的舞会 √
• P2014 选课 √

换根 dp

• P4228 榕树之心 √

状压 dp

• P2704 炮兵阵地 √
• P1879 Corn Fields G √

数位 dp

• P2657 windy 数 √
• P3413 萌数 √
• P4127 同类分布 √

插头 dp

本质是对长为 (m + 1) 的轮廓线进行 dp

• P5056 模板 √
• P5074 Eat the Trees √

动态 dp

进行带修 dp 时维护 dp 矩阵

• P4719 模板 √

---

字符串

KMP

对于原字符串求出了每一个前缀的最长 border，可以在 O(n + m) 的时间内匹配字符串

• P3375 模板 √
• P4173 残缺的字符串 √

AC 自动机

多字符串的 KMP

• P3121 Censoring G √
• P2292 L 语言 √
• P2414 阿狸的打字机 √

字符串哈希

• P3167 通配符匹配 √
• P4503 企鹅 QQ √

后缀自动机

• P3804 模板
• CF700E Cool Slogans √
• P3975 弦论 √
• CF1037H Security √

广义后缀自动机

• P6139 模板 √
• P3966 单词 √

Manacher

• P3805 模板 √

回文自动机

• P4555 最长双回文串 √
• P3649 回文串 √

---

数学

拓展欧拉定理

$$ a^b\equiv\begin{cases} a^b, &\gcd(a, p)=1\\ a^{b\mod \varphi(p)}, &\gcd(a, p)\ne 1\land b\ge \varphi(p)\\ a^{b\mod \varphi(p)+\varphi(p)}, &otherwise \end{cases}\pmod p $$

• P4139 上帝与集合的正确用法 √

BSGS

根号暴力

• P2485 计算器

Lucas 定理

当 $p\in \mathbb{P}$ 时，有 $\binom{n}{m}\equiv \binom{n\mod p}{m\mod p}\cdot \binom{\lfloor n/p\rfloor}{\lfloor m/p\rfloor}\pmod p$

• P3807 模板 √
• P4345 超能粒子炮·改 √
• P2480 古代猪文 √

（拓展）中国剩余定理

• P4777 模板 √
• P4774 屠龙勇士 √

莫比乌斯反演

• SP5971 LCM Sum √
• P1829 Crash的数字表格 √
• P3768 简单的数学题 √
• P6271 一个人的数论 √

杜教筛

要求积性函数 $f$ 的前缀和时，若有一积性函数 $g$，使得 $g$ 和 $f*g$ 的前缀和都可以快速计算，那么可以通过公式

$$
S(n)=\sum_{i=1}^n (f*g)(i)-\sum_{i=1}^n g(i)S(\left\lfloor\frac{n}{i}\right\rfloor)
$$

加上 unordered_map 缓存来快速求得

• P4213 模板 √
• Codewars Count Empty Triangles √

FFT

• P3803 模板 √
• CF528D Fuzzy Search √
• COCI 2016-2017 #3 meksikanac √

min-max 容斥

$$
min(S)=\sum_{s\subset S}(-1)^{|s| -1}min(s)
$$

max 同理

• 联训 晚辈的游戏 √
• HDU4336 Card Collector √

组合数学

第一类斯特林数

把 $n$ 个元素分配到 $m$ 个环中的方案数

$S(n, m) = S(n - 1, m - 1)+(n - 1)\cdot S(n - 1, m)$

• P5408 求单行 √

第二类斯特林数

把 $n$ 个元素分配到 $m$ 个集合中的方案数

$S(n, m) = S(n - 1, m - 1)+m\cdot S(n - 1, m)$

• P5395 求单行

方案计数

Burnside 引理

本质不同的方案总数 = 每种置换下不动点的方案总数的平均值

• P1446 Cards √

Polya 定理

实际上就是 Burnside 引理的部分延伸

• P4980 模板 √
• P4128 有色图 √
• P4727 图的同构记数 √

---

博弈

当前情况但凡有一种行动能转移到必败态，就是必胜态；否则就是必败态

• P2197 nim 游戏 √
• CF1147C Thanos Nim √
• SP23881 God of Nim √

---

数据结构

并查集

• COCI 2014-2015 #2 suma √

二叉堆

• P3378 模板

（可持久化）左偏树

• P3377 模板 √
• P2483 魔法猪学院 √

分块

• CF455D Serega and Fun √
• Codewars Naive subarray √

树状数组

• P3374 模板 1 √
• P3368 模板 2 √

线段树

• P3372 模板 1 √
• P3373 模板 2 √
• P2572 序列操作 √

平衡树

Treap、Splay、替罪羊树…

其中貌似只有 FHQ-Treap 可以可持久化

• P3224 永无乡 √
• P4008 文本编辑器 √

主席树

• P3834 模板 √
• P3402 可持久化并查集 √
• P2617 Dynamic Rankings √

KD-Tree

• P4169 SJY摆棋子 √
• P4390 Mokia 摩基亚 √
• P2479 捉迷藏

ODT

• CF896C Willem, Chtholly and Seniorious √
• P4344 脑洞治疗仪 √

Link Cut Tree

• P3690 模板 √
• P4332 三叉神经树 √
• P3203 弹飞绵羊 √
• P3703 树点涂色 √

---

计算几何

凸包

• POJ1873 The Fortified Forest √
• POJ3178 Roping the Field √

自适应辛普森积分法

• BZOJ2178 圆的面积并 √

半平面交

• P4196 模板 √
• POJ1755 Triathlon √

圆的反演

• HDU6158 The Designer √