[技巧] 当你考虑到某个算法就可以『秒杀构造』？！
Felix72
·
·
算法·理论
文章名称学的五人组（Badcen，Melor，Kamuamua，Unclered，Heimao，现在已经实质进入解散状态）的风格。
存在这样一类构造题：它的解法看起来高深莫测，难以直接想出来，然而你做完题目一看题解，发现这个构造的思想和某个算法不谋而合——这也难怪，本来自己“发明”这些经典算法的难度就是很高的。如果你对算法本体不敏感，那这类题也将成为你难以攻破的“人类智慧”。因此本文总结一些套用了某些算法思想的构造题，以便在出现其他同类的题目时达到秒杀的效果。
## 最短路
### 例题：[AGC039B Graph Partition](https://www.luogu.com.cn/problem/AT_agc039_b)
> 给定一张 $N$ 个顶点，$M$ 条边的无向连通图。
顶点以 $1\ldots N$ 编号，边以仅包含 $\texttt{0/1}$ 的邻接矩阵的形式给出。
>
> 请判断是否能够将顶点分为 $k$ 个非空集合 $V_1,\ldots,V_k$，使得其满足以下条件。若可以，则最大化 $k$：
> - 对于每条边 $(i,j)$，存在 $1 \le t \le k-1$ 满足 $i \in V_t, j \in V_{t+1}$ 或 $i \in V_{t+1}, j \in V_t$。
容易想到图是二分图，但是接下来似乎不好处理？我们看这个 $V_t$ 和 $V_{t + 1}$ 之间连边的模型，和最短路 $\text{DAG}$ 的结构一致。因此猜想本题构造与 $\text{BFS}$ 算法相关。果不其然，想到这一点之后我们能够轻易证明答案就是从某个点跑出的单源最短路。
## 差分约束
### 例题：[AGC056C 01 Balanced](https://www.luogu.com.cn/problem/AT_agc056_c)
> 考虑构造一个由 `0` 和 `1` 组成的长度为 $ N $ 的字符串 $ s $。其中 $ s $ 需要满足 $ M $ 个条件。第 $ i $ 个条件由整数 $ L_i, R_i $（$ 1 \leq L_i < R_i \leq N $）表示，这意味着在 $ s $ 的第 $ L_i $ 个字符到第 $ R_i $ 个字符之间，包含的 `0` 和 `1` 的数量必须相等。
>
> 请在所有满足条件的 $ s $ 中找出字典序最小的那个。可以证明，在问题的约束下，满足条件的 $ s $ 一定存在。
```0``` 和 ```1``` 的数量必须相等提示我们可以用图论建模刻画数量关系。如果我们把 $0$ 变为 $+1$，$1$ 变为 $-1$，那么这个条件实质告诉我们前缀和数组的两个位置是相等的！另一个限制是前缀和数组之前一定相差 $±1$，即 $-1 \leq s_i - s_{i + 1} \leq 1$。
出现了这么多不等式，我们猜想此题构造和差分约束有关。事实上，把刚才的两个限制拿出来建图跑最短路解差分约束可以直接得到正解。
为什么不会出现 $s_i = s_{i + 1}$ 以及字典序最小如何保证需要对该题进一步的理解证明，但是想到差分约束并手玩转化已经足够让我们通过此题。
## KM 算法
是的你没听错，二分图最大权匹配这个东西都能改一道构造出来。下面这个很刁钻的证明角度可以让进一步让你体会到本文所说技巧的神奇之处。
### 例题：[CF1765J Hero to Zero](https://www.luogu.com.cn/problem/CF1765J)
> 本题没有英雄。我想我们应该把它命名为“归零”。
>
> 给定两个数组 $a$ 和 $b$，每个数组包含 $n$ 个非负整数。
>
> 令 $c$ 为一个 $n \times n$ 的矩阵，其中 $c_{i,j} = |a_i - b_j|$，对于每个 $i \in [1, n]$ 和每个 $j \in [1, n]$。
>
> 你的目标是将矩阵 $c$ 变为零矩阵，即每个元素都恰好为 $0$。为此，你可以任意次、以任意顺序执行以下操作：
>
> - 选择一个整数 $i$，然后将第 $i$ 行的所有元素 $c_{i,j}$（$j \in [1, n]$）都减 $1$。每执行一次该操作，需支付 $1$ 个硬币；
> - 选择一个整数 $j$，然后将第 $j$ 列的所有元素 $c_{i,j}$（$i \in [1, n]$）都减 $1$。每执行一次该操作，需支付 $1$ 个硬币；
> - 选择两个整数 $i$ 和 $j$，然后将 $c_{i,j}$ 减 $1$。每执行一次该操作，需支付 $1$ 个硬币；
> - 选择一个整数 $i$，然后将第 $i$ 行的所有元素 $c_{i,j}$（$j \in [1, n]$）都加 $1$。每执行一次该操作，可获得 $1$ 个硬币；
> - 选择一个整数 $j$，然后将第 $j$ 列的所有元素 $c_{i,j}$（$i \in [1, n]$）都加 $1$。每执行一次该操作，可获得 $1$ 个硬币。
>
> 你需要计算将矩阵 $c$ 变为零矩阵所需的最小硬币数。注意，所有 $c$ 的元素必须在操作后同时为 $0$。
线性规划？不用！我们看这个问题：
- 考虑如下线性规划问题：给 $x, y$ 两数组赋值，满足对于任意 $i, j$，均有 $x_i + y_j \geq w_{i, j}$，要求最小化 $\sum x + \sum y$。
完全不需要线性规划的对偶转化。直接用 KM 算法的正确性就能证明这个最小值取到以 $w$ 作为邻接矩阵的二分图的最大权值匹配。因此对于上面这个问题，做一遍二分图最大权值匹配就行了。
知道这个结论后原问题迎刃而解。
## Hall 定理
### 例题：[CF1519F Chests and Keys](https://www.luogu.com.cn/problem/CF1519F)
> Alice 和 Bob 玩一个游戏。Alice 有 $n$ 个宝箱（第 $i$ 个宝箱里有 $a_i$ 枚金币），还有 $m$ 把钥匙（第 $j$ 把钥匙可以卖给 Bob，售价为 $b_j$ 枚金币）。
>
> 首先，Alice 会在宝箱上加锁。有 $m$ 种类型的锁，第 $j$ 种类型的锁只能用第 $j$ 把钥匙打开。若要在第 $i$ 个宝箱上加第 $j$ 种类型的锁，Alice 需要花费 $c_{i,j}$ 美元。每个宝箱可以加任意数量的不同类型的锁（也可以一个都不加）。
>
> 接着，Bob 可以从 Alice 那里购买任意数量的钥匙（可以一把都不买，也可以全部买下），然后打开他能打开的宝箱（如果他拥有打开该宝箱所有锁的钥匙，则可以打开该宝箱）。Bob 的收益等于他打开的所有宝箱中的金币总数减去他购买钥匙所花费的金币总数。如果 Bob 的收益严格大于零（即收益为正），则他赢得游戏。否则，Alice 获胜。
>
> Alice 想要在一些宝箱上加锁，使得无论 Bob 购买哪些钥匙，她都能获胜（即 Bob 无法获得正收益）。当然，她希望花在加锁上的美元数尽可能少。请你帮她判断是否有可能获胜，如果可以，最少需要花费多少美元加锁。
[这个题](https://www.luogu.com.cn/problem/CF1519F)并不是构造题，但是和本文思想比较类似。
“无论 Bob 购买哪些钥匙，她都能获胜”形如，稍微转化一下就是“无论开了哪些箱子，买钥匙的钱都比奖励多”。我们发现其形如**一堆必要条件**，和 $\text{Hall}$ 定理的形式极为相似。
因此我们可以直接用 $\text{Hall}$ 定理，把原限制转化为以下限制：
- 给定了二分图，有至多 $4(n + m)$ 个点（把每个金币视为一个点）。一开始没有边，连边需要代价；
- 要求连边后图存在最大匹配。
数据范围很小，并且左/右部本质不同的点最多只有 $6$ 个，可以直接状压匹配情况。
---
通过上面几个例子，我们可以看出这类通过经典算法构造出的“$\text{ad-hoc}$ 原题”通常是及其巧妙的，如果不往特定的方向思考，很容易走偏。因此我们以后做到一道拥有神秘限制的题目时，不妨先想一想题目的限制是否提示我们思考某一个特定算法。
另一些经典的例子是模拟费用流，用线段树实现网络流的思想，但是太过经典就不写了。
如果有其他这样的题目，可以评论或私信我添加。