复习 #2：构造题的思考方式

EternalAlexander · 2022-08-28 14:23:10 · 个人记录

很多之间很熟练的技巧现在都不记得了。

有的人上上周都还不会写最短路，哈哈。

构造题并没有结论或模板之类的东西，只能采用例题来进行说明

归纳法

最常用的构造方法之一，通过提出构造对象的某个特殊的单元，解决规模更小的问题，然后将提出的单元合并回去得到原问题的解。

给定一有向图，将点染成黑白两种颜色，要求黑色点之间不能有连边，任意白点到最近黑点的距离 \leq 2。

考虑归纳构造，任取点 u，将 u 和 u 指向的所有节点删去，对新得到的点集构造答案。然后考虑：得到的点集中，是否存在一个点，满足它指向 u， 且它的颜色为黑色。如果没有，可以把 u 染成黑色，否则将 u 染成白色。

可以检验，加入 u 以及它指向的节点后，依然满足题目限制。

CF1517C：给定一个 n 行 n 列的下三角区域，主对角线上已经填了 1 \sim n 的一个排列，你需要将其他格子也填上 [1,n] 之间的数字，满足数字 i 出现次数恰好为 i，且所有出现位置形成了一个联通块。

注意到数 1 的出现位置已经确定了，将对角线中 1 上方的位置的下方一个格子填上和它相同的数，1 下方的位置的左侧一个格子填上和它相同的数。这样，我们将问题归纳为了大小为 n - 1 的子问题。

NOIP2020 T3 移球游戏

根据题目条件，我们知道这样的一个问题是可以解决的：有 n +1 根柱子和 n 种颜色，前 n 根柱子上恰有 m 个球，每种颜色的球恰有 m 个，最后一根柱子是空的。目标是使得所有柱子上的球颜色相同。

考虑利用最后一根柱子将问题归纳为大小为 n - 1 的子问题（也就是，将使得某一根柱子上的球颜色相同，然后就可以删去这根柱子）。

大致的做法是，考虑把所有颜色 c 堆到空柱子上。称一开始的空柱子为待命柱。对于柱子 i（称为当前柱），若它上面有 x 个颜色为 c 的球，我们随便从另一个柱子（称为临时柱）上取 x 个球放到待命柱顶部，然后取出柱子 i 的所有球，若它是颜色 c，则把它放到临时柱顶部，否则放到待命柱顶部（可以发现这样恰好可以放完）。然后把待命柱顶部的所有非颜色 c 的球放到当前柱中，再把临时柱顶端所有颜色 c 的球放到待命柱顶部。复杂度 O(n^2m)，进行一定的常数优化即可通过。

对限制条件的分析

分析题目所给出的限制条件，并尝试构造以满足题目要求。

CF1383D Rearrange

考虑构造一矩阵满足最大值的限制：

CF1510J Japanese Game

考虑一个 profile 的 mask 是什么形式。

定义一个 profile 的自由度 f：从左往右贪心地摆完，右边会剩下多大的空间。（即，n - \sum_{i=1}^k L_i - (k - 1)）

我们考虑某一段，把它左边的段尽可能向左放，它右边的段尽可能向右放，它会有一个可以移动的区间，而有一部分格子是它无论如何移动都会覆盖到的，这一部分就是 mask。

形式化地，从左往右贪心地把每段摆在尽可能左的位置，若它的长度是 L，那么它右边 L - f 的长度是 mask。

若我们已知 f，考虑构造一个 profile。我们是知道所有长度 >f 的段（会产生 mask）的长度的。我们只需要用一些长度 \leq f 的段来把它们对齐到合适的位置。

首先如果两段之间的空隙必须 \geq f。如果是 f + 1 那么当然不用填，如果是 f + 2，可以发现是没有解的。否则，如果 f > 2，你可以用 1 和 2 填起来。

根据上述条件，找出一个合法的 f 构造即可。注意特殊处理 f = 0 和 f = 1。

1494F Delete The Edges

需要讨论的情况较多，因此略去分类讨论的过程。

注意到操作之后能消除的边一定是一个菊花图。枚举菊花心 x，删去一些从它到其它点的边，一定要剩下一条从它开始的欧拉路径。

注意到删去连向偶度点的边是不优的，不妨先把到奇点的边删了，这样一定能最小化奇数点的个数。

如果存在边（非孤立点）的连通块个数 =1，并且没有奇数点或者奇数点只有 2 个且包含 x，那可以直接构造答案。

如果存在边的连通块数 = 2，一定要连回去一条边（而且你知道这条边是什么）。此时若有奇数点，讨论一下发现一定不合法。否则连那条边，可以直接构造答案。

对于其他情况，讨论知一定不合法。

[USACO21FEB] Minimizing Edges P

设 A_u = \min \{O_u,E_u\}，B_u = \max \{O_u,E_u\}。拉一棵 bfs 树出来，显然节点 u 的深度等于 A_u。

最短路树的限制是很强的，非树边只能连接相邻两层。考虑怎样满足 A 和 B 的限制。A 的限制容易处理，每个点一定要向前一层连一条边。接下来主要考虑如何构造图满足 B 的限制。

称 B_u = A_u + 1 的点为关键点。若一个点 u 不是关键点，则一定向一个满足 B_v = B_u - 1 的点 v 连边。否则，它可以由上述方式满足限制，或者由一条连接同一层两个关键点的边来满足限制。

考虑按层依次构造答案，对于一层的每个点 u ，若：前一层存在尚未满足限制的点 v 使得 B_v = B_u + 1，则从 u 向 v 连边，满足 v 的限制。否则，若存在点 v 使得 B_u = B_v + 1，则向 v 连边，满足 u 的限制。否则随意连一条合法的边。（为什么正确？对答案贡献均为 1，而之前层只能由当前层匹配，当前层还可能由后面消除，可行决策集合严格包含）

做完之后，对每一层考虑尚未满足限制的点，其中关键点有 c_1 个，非关键点有 c_2 个，一条边可以满足两个关键点的合法性（也可以是一个，连一个自环），而对于非关键点，只能向前一层/后一层连一条边来保证合法（因为是由一个存在的图构造出来的，一定可以这样做）。增加的边数为 \lceil \frac{c_1}{2} \rceil + c2。

给定 a,b,c,M，求一组 x,y,z 满足 0 < x,y,z < M 且 x^a + y^b \equiv z^c \mod M。其中 a,b,c 两两互质。

考虑一下那个互质要怎么用。

（以下运算未说明均在模 P 意义下进行）考虑构造成如下形式：2^{k ab} + 2^{k ab} = 2^{k ab + 1}，然后可取 x = 2^{ka},y = 2^{kb}, z = 2^{(kab+1)/c}

也就是求一个 k 使得 kab + 1 \equiv 0 \mod c，因为 a,b,c 两两互质，可以使用扩展欧几里得算法解出一组合法答案。

但是当 P = 2^c 时我们的 x,y,z 可能是 0，这时需要特殊处理。若 a > 1 取 x = \frac{m}{2}, y = z = 1,b > 1 类似，否则 c > 1 取 x = y = z = \frac{m}{2}，再否则 a=b=c=1，取 x = y = 1, z = 2。

必要与充分条件

有些题目需要你判断能否构造出答案。此时一般可以得到一个较为明显的必要条件，而往往这个条件同时也是充分的，我们只需对于符合这个条件的情况进行构造。

以及，对于一些需要求出最优解的题目，存在一个显然的上界。而这个上界或许是可以构造出来的，我们只需给出一个合法的构造。这类题目通常会让你输出方案，而不是求解答案，因为后者往往是容易的。若是这样，则需考虑一下是不是这类题目。

1444D Rectangular Polyline

首先必要条件：横竖的线段都必须能划分为两个长度相等的集合，且横竖线段个数相等。

然后我们来构造方案：横竖线段中，取第一个集合为正，第二个集合为负，然后先随意两两匹配，得到一些向量，并且我们知道这些向量的和为 0。

考虑用它们围成一个凸多边形，然后如果我们先走 x 后走 y 的话，第一象限和第三象限的向量的行走路线在凸多边形外，二四在形内。

也就是说只有在形内的二四象限的向量的轨迹可能相交，要是其中某一个象限不存在就好了。仔细想想是可以做到的，我们把横竖线段排序后匹配，自然二/四象限中会有一个不存在。

CF1450E Capitalism

首先这张图一定是二分图。

既然是最大减去最小，我们只关心它们之间的相对大小关系，那么不妨定一个 0，我们先枚举节点 s 的权值为 0。

考虑其它的元素，它们的权值最大能是多少呢？考虑对于无向边，自然 d_u \leq d_v + 1，d_v \leq d_u + 1 是必要条件。对于有向边，d_v \leq d_u +1，d_u \leq d_v -1 。因此，如果对于 (u,v,0)，我们连边 u \leftrightarrow v，边权 1；对于 (u,v,1)，我们连边 u \rightarrow v，边权 1，v \rightarrow u，边权 0，此时 u 的权值一定不大于 s 到 u 的最短路长度（如果存在负权回路，自然不存在任何合适的权值）。

同时，如果将到节点 u 的最短路径长度作为其权值，我们发现这恰好满足题目给定的限制。对于 (u,v,0)，显然 d_u \leq d_v + 1，由于是二分图 d_u 和 d_v 奇偶性不同，因此 d_u \neq d_v。若 d_u = d_v -1 或 d_u = d_v + 1 都是符合题意的，若 d_u < d_v - 1，不满足 d_v \leq d_u + 1，矛盾。(u,v,1) 的情况类似。

因此枚举 s，求解最短路即可。

CF1442E Black, White and Grey Tree

考虑只有黑点和白点的情况，显然可以把颜色相同的联通块缩起来，得到一棵黑白相间的树。

先考察一条长度为 n，黑白相间的链，此时容易观察到它需要 \lfloor \frac{n}{2} \rfloor + 1 次操作。对于一棵树，考察它的直径，若其长度为 x，显然操作次数的下界是 \lfloor \frac{x}{2} \rfloor + 1，而这个下界是可以构造得到的（每次删去颜色相同的叶子）。

对于灰点的处理不在这次讨论的主题内，这里略去。

缩放条件/增强问题

和不等式证明中的放缩很类似，有时直接解决更强的问题，反而会更加简单。

有两个序列 A 和 B 长度为 n，元素均为 [1,n] 之间的整数。现要求从 A 和 B 中各选一个（非空）集合使得它们的和相等。

做法：考虑在 A 和 B 中选两个连续段来达成要求。也就是 SA_i - SA_j = SB_k - SB_l，所以 SA_i - SB_k = SA_j - SB_l。假设 SA_n > SB_n，对每个 SA_x 我们找到最大的 SB_y \leq SA_x，如果这两个相等直接找到了答案，接下来我们认为它们不相等。因为 \forall i B_i \leq n，所以 SA_x - SB_y \leq n。因为有 n+1 个这样的 x，[1,n] 只有 n 个数，一定有两个相同。

计数构造

这一类问题是，需要你构造一个组合对象，使得它的某个计数问题的答案恰好为题目给定的某个参数。常用的手段是：二进制拆分/贪心选取最大可选的决策等。

CF1396E Distance Matching

待更新。

构造一个（有向）简单图，使得它的哈密顿路径数量恰好为 k。

构造一条 18 个点的链，每个点像前面一个点和后面所有点连边。这样从倒数第 i 个点走到最后的方案数就是 2^i，把 k 二进制拆分后，从源点向为二进制中为 1 的位置连边。

构造一个 n \leq 20, m \leq 120 的二分图（允许重边），使得完美匹配数量恰好为 k。 (k \leq 10^9)

和上题类似地，连一条红边可以让方案数多 2^i。但是这个题里面二进制拆分可能不够用，可以三进制拆分。

构造一个长度 \leq 10^5 串使得其本质不同子串数量为 k (k \leq 10^9)。

构造类似 \texttt{aaabbccccdee} 这种串。假设每种字符有 \{a_1,a_2 \ldots a_k\} 个，本质不同子串数量是 \binom{n+1}{2} - \sum \binom{a_i}{2}，选取 \binom{n+1}{2} \geq k 的最小 n 然后贪心地选取最大的 a_i 即可。

调整法

通过调整使得当前状态靠近满足题意的状态，观察到某个值往某个方向一直运动，即可以在证明调整一定能结束。

有一个 n \times n 的矩阵，每次可以将一行或者一列的符号取反，请进行若干次调整使得所有行和所有列非负。

做法：每次找不合法的行或者列操作，然后所有元素的和一定是增大的，因此一定可以调整结束。

THUPC 母亲节的礼物

待更新。

范围讨论

有的题看起来大部分情况答案是显然的，但是比较小的情况中会出现一些讨论不清楚的东西，可以考虑对小范围暴力处理。

CF1461F Mathematical Expression

除了 +-* 之外的情况都比较简单，只考虑全体符号都合法的情况。

当然不会用 -，那么什么时候 +，什么时候 * 呢？

也就是划分为若干段，最大化每段乘积之和。

考虑 0，如果某一段包含 0 且长度大于 1，不如把它分为 0 前后的两段。

因此我们可以原序列从 0 处分成若干个不包含 0 的段，分别做。

一般来说我们是希望全部乘起来，这样明显大很多。但是有些乘积比较小的情况，可能在 1 附近摆 + 反而更优。

先把一段开头和结尾的 1 去掉（当然全是 +）。考虑其他数的乘积，如果比较大的话，就直接全部乘起来。否则，我们知道不是 1 的位置是很少的，并且最大答案也是很小的。我们可以 dp，注意分段的末尾只可能是一个不是 1 的位置，最多只有 \log w 个，暴力 dp 就可以了。

CF1493E Enormous XOR

如果 L 和 R 最高位不同，似乎可以使用 011 \ldots 110 和 100 \ldots 000 构造得到上界，但是当 L 和 R 极小的情况下确有些讨论不清楚的情况。

如果 L 和 R 最高位相同，当然要让最高位是 1，那么 S(L) 就只能选 0 或者 1 了。如果 [L,R] 这个区间比较大的话，0 和 1 都可以取到（长度超过 4 就可以了），那答案就相当于是 R \operatorname{bitor} 1但是很小的时候又有一堆讨论不清楚的大情况。

发现讨论不清楚的时候 R - L 总是很小，那我们直接在它比较小的时候大暴力，就可以规避掉一切讨论。

问题转化

并不仅限于构造性问题的方法，很多问题都是，在进行若干步转化之后，转化为某个更强/更弱/等价的问题，进而通过转化后的问题的方法来解决原问题。

CF1503D Flip the Cards

注意到，对于两张牌，如果 \max(a_1,b_1) < \min(a_2,b_2)，这两张牌无论怎么摆都不合法。略加考虑即可发现每张牌的两个数字必须一个小于等于 n，另一个大于 n。

设 f(i) 表示，数字 i 那张牌另一面的数字。考虑称较小面向上的牌为一类牌，否则为二类牌。也就是要将牌分为一类和二类，然后显然把二类放在一类后面，同时要求在一类和二类中，他们较小的一面 x 上升时，f(x) 都是下降的。

因此原问题至少是：将 f(1 ... n) 划分为两个下降子序列。同时，任何一种划分方案，都对应着原问题的一种分类方案。

接下来我们只需最小化答案。也就是，对于每一个 x，把它划分进某一个子序列会付出 1 的代价。

考虑：对于某一个位置，如果它前面的最小的 f(x) 都比后面最大的 f(x) 大，那么这两段问题是独立的。考虑对每一段独立求解。注意到在每一段中，考虑一个数，若你可以把它划分进第一个和第二个子序列中，你一定要将它划分进栈顶较小的那个。因为在它之后，一定存在一个数大于前缀最小值（较小的栈顶和自己），如果自己放到了另一个栈中，后面那个元素就无法划分了。因此若认为两序列无区别，划分方案是唯一的。

二选一构造

很无聊，出这种题简直是有毛病

CF1439B Graph Subset Problem

CF1404D Game of Pairs