构造题

· · 个人记录

学不会的构造

调整法

关键：调整，然后观察到某个值往某个方向一直运动，可以在证明调整一定能结束。

不知道哪里的题：

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

|a_{i,j}| \leq 100

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

THUPC 母亲节的礼物

观察出题人给你的诡异条件到底有什么用

十分厌恶的一类题，通常是逆向出题的产物。或者出题人做到某个地方做不下去了，就编了个条件强行做。只有你恰好和出题人想到同一个方向才能做出来。

应对手段就是猜测这个条件要如何用。

CF1355F Guess Divisors Count

CF1495C Garden of the Sun

51nod 小Y的数论题

题意：给定 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。

鸽巢原理

有两个序列 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。

k \leq 10^5, n = 20

做法：构造一条 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 即可。

必要条件恰好是充分的

51nod 小 C 的多边形

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，求解最短路即可。

增量法

拉出来一个整体，然后合并到前面已经构造好的部分。

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

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

增量的不一定是一个元素！

小范围讨论

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

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 总是很小，那我们直接在它比较小的时候大暴力，就可以规避掉一切讨论。

缩放条件

通过一些不等价的变换，直接解决更强的问题，可能更容易。

给定一张图，每个顶点的度数都是偶数 k，要求删掉若干条边使得每个顶点度数都是 2。

既然每个顶点度数都是偶数，那么可以求出一条欧拉回路。然后把每条边定向，一个点入度和出度都是 \frac{k}{2}。

接下来给每个顶点定一个前驱，拆成入和出之后，相当于一张二分图，每个顶点度数都是 k。此时根据 hall 定理，可以发现完美匹配存在。就得到了答案。

直接构造

最困难的构造题，完全没有任何依据的凭空构造。

一个 n 个点的完全图，选出若干个边不相交的三元环使得剩下的边的个数不超过 n-1。

选 i+j+k \mod n = 0 的三元环即可。

观察限制条件，细致分析问题

相对来说比较会做的构造题。

1494F Delete The Edges

见做题记录。

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。

先满足某一限制，然后尝试在这个基础上考虑其他限制

CF1383D Rearrange

问题转化

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

逆向思维

1500 C Matrix Sorting

杂题

1491G Switch and Flip

1491F Magnets

1442E Black, White and Grey Tree

CF1404D Game of Pairs

CF1442E Black, White and Grey Tree