专题训练 - 构造 II

[CF1463B] Find The Array

考虑构造出一种情况 $b_i,b_{i+1}$ 之间的约束条件永真，一个自然的想法是令 $b_i$ 为 $2$ 的幂。

既然是 $2$ 的幂次，那就让每一个绝对值里的值尽可能小，所以这里找 $k$ 使得 $2^k \le a_i<2^{k+1}$ 。

此时 $2\sum |a_i-b_i|=\sum(2a_i-2^{k+1})<\sum a_i=S$ 。

题解给出了另一种方法，既然想让这个约束条件永真，只要相邻两个元素有一个 $1$ 也能满足这一点，自然另一个就填对应的 $a_i$ 。

然后， $2\sum_{i=\texttt{odd}}(a_i-1)+2\sum_{i=\texttt{even}} (a_i-1)=2S-2n$ ，所以一定有一个值 $\le S-n<S$ 。

AC Code。

[CF1366D] Two Divisors

首先， $(d_1,d_2)\mid d_1+d_2$ ，所以 $(d_1,d_2)=1$ 是 $(d_1+d_2,a_i)=1$ 成立的必要条件。

进一步地，从算术基本定理的角度考虑，把 $a_i$ 分解后变成 $p_1^{k_1}p_2^{k_2}\dots p_m^{k_m}$ 。

显然 $m=1$ 时，任意一个非 $1$ 的因子 $d$ 都满足 $p_1\mid d$ ，不可能找到 $d_1,d_2$ 满足 $d_1\perp d_2$ 。

当 $m\ge 2$ 时，我们需要找到 $d_1,d_2$ 满足 $d_1\perp d_2$ 并且 $\forall 1\le j\le m, p_j\not\mid d_1+d_2$ 。

当 $p_j\mid d_1$ 时， $p_j\mid d_1+d_2$ 成立当且仅当 $p_j\mid d_2$ ，而又因为 $d_1\perp d_2$ 得知这是不可能的。

因此这就给出了一个构造方法，让每一个 $p_j$ 都是 $d_1$ 或 $d_2$ 的因子即可。

AC Code。

[CF796D] Police Stations

首先，树的性质保证了删掉边的数量 $+1$ 与连通分量数量 $m$ 相等。

设节点数量是 $n$ ，警局数量去重之后是 $p$ ，那么 $m\le p$ 是成立的，因为你不可能把 $p$ 个警局放到多于 $p$ 个连通块里面。

又因为题目保证每一个点到最近警局的距离 $\le d$ ，这里能够给出一个构造方法使得连通块数量达到上界 $p$ ：做一个多源最短路，找到离每一个点最近的警局，这些点就构成了 $p$ 个不同的连通分量。

AC Code。

[CF1450C2] Errich-Tac-Toe (Hard Version)

类似于本文第一题的思想，考虑能不能把可能进行的操作分成 $3$ 种，让它们加起来的操作数量等于 $k$ ，即把 $k$ 个非空白位置按照某种方式划分成三种方案的无交之并，那么最小的那种操作方案的操作数量就满足至多为 $\cfrac{k}{3}$ 。

如果这是一条直线的话，很自然可以想到按照模 $3$ 为 $0,1,2$ 的三种位置分类染色，这样每连续三个格子都会有不同的颜色。

取两个颜色 $A,B$ ，我们只需要保证颜色为 $A$ 的格子要么是空白、要么是 $\texttt{O}$ ；颜色为 $B$ 的格子要么是空白、要么是 $\texttt{X}$ ，就能保证连续三个格子不可能同时是 $\texttt{O}$ 或 $\texttt{X}$ 。

拓展到平面，此时我们按照下标 $i+j$ 模 $3$ 分类染色，这样每连续三个格子都会有不同的颜色。为什么这么想？因为连续的三个格子一定有一个坐标是不变的，另外一个坐标是 $+0,+1,+2$ ，因此这某种程度上也是在直线上的结论。

设 $O_i,X_i$ 表示颜色为 $i$ 的初始 $\texttt{O},\texttt{X}$ 的数量，那么 $\sum_{i=0}^3 O_i+\sum_{i=0}^3 X_i=k$ 。

于是选择 $A,B$ 使得 $O_A+X_B$ 最小，就能保证 $k=\sum_{i=0}^3 O_i+\sum_{i=0}^3 X_i\ge 3(O_A+X_B)$ ，即 $O_A+X_B\le \cfrac{k}{3}$ 。

实际的实现中，我们只需要保证选择的一组 $A,B$ 确实 $\le \cfrac{k}{3}$ 即可，根据上面的阐述一定会存在一组 $A,B$ 满足这一条件。

AC Code。

[CF1217D] Coloring Edges

首先用拓扑排序判掉 DAG 的情形，下面我们关注有环的情形。

如果有环 $v_1,v_2,\dots,v_k,v_1,v_2,\dots$ ，由于这里一共只有 $k$ 个互异的整数，则必然会存在一条边 $(a,b)$ 使得 $a>b$ ，否则根据小于关系的传递性可以推出 $v_1<v_1$ ，不符合小于关系的反自反性。

因此，只要我们满足每一条边 $(a,b)$ 都有 $a<b$ ，就可以断定构造出来的图没有环；类似地，如果满足每条边都有 $a>b$ ，也可以断定构造出来的图没有环。

AC Code。

[CF1485D] Multiples and Power Differences

首先， $a_{i,j}$ 的值比较小，我们可以算出来 $M=\operatorname{lcm}(1,2,\dots,16)=720720$ 备用。

这是连续两个位置，与上面那道连续三个位置的要求有些类似。

我们不妨依然按照每个格子下标 $i+j$ 模 $2$ 染色，颜色为 $0$ 的直接填 $M$ ，颜色为 $1$ 的填 $M+a^{4}_{i,j}$ 即可满足 $a_{i,j}\mid b_{i,j}$ 。

AC Code。

[CF1370E] Binary Subsequence Rotation

首先，特判掉 $s$ 和 $t$ 的 $0/1$ 对应个数不相等的情况，容易看出如果 $0/1$ 个数对应相等，起码可以通过两两交换让 $s=t$ 。

接下来我们观察操作序列的性质，如果我们的操作序列某一部分包含了多个相同的元素，如 $0\textbf{1}1101$ ，它操作之后的结果等价于 $0\textbf{1}01$ ，因为后面两个 $1$ 操作前后都仍然是 $1$ 。同理，操作的开头和末尾如果一样的话，我们可以把开头那个位置删掉。

于是，我们的操作序列已经变成了 $0101\dots 01$ 或者 $1010\dots 10$ 这两种。

接下来我们要构造出一种操作方法，并且证明任何操作步数都不会比这种方案更优。

构造操作方法。

一个常规的思路是，我们可以只关注那些不匹配的位置，把匹配的位置删掉，设剩下的 $s,t$ 的下标为 $1\sim m$ 。

给 $s_i=1,t_i=0$ 的位置赋一个权 $w_i=1$ ； $s_i=0,t_i=1$ 的位置赋一个权 $w_i=-1$ 。

根据一开始的论断，我们可以知道不匹配的位置中， $s$ 的 $0/1$ 数量与 $t$ 的 $0/1$ 数量对应相等，又因为这是不匹配的位置，所以 $s$ 的 $0/1$ 数量与 $t$ 的 $1/0$ 数量对应相等。于是 $\sum_{i=1}^m w_i=0$ 是成立的。

我们可以关注 $S_i=\sum_{j=1}^i w_j$ 的变化，根据上文 $S_m=0$ ，当 $i=1\sim m$ 时，给出下面的方案，其中 $L_0,L_1,L_{-1}\dots$ 是不同的操作序列：
1. 当 $w_i=1$ 时，将当前的 $i$ 放到 $L_{S_i}$ 中；
2. 当 $w_i=-1$ 时，将当前的 $i$ 放到 $L_{S_{i}+1}$ 中，
例如，当 $s=101100$ 时，会有 $L_1=1,2,3,6$ 且 $L_2=4,5$ ，容易看出他们对应的操作序列都是 $10\dots 10$ 。

手玩可以发现每一个操作序列都是 $1010\dots 10$ 或者 $0101\dots 01$ 这样的，即构造出了一种 $\max_{i=1}^m S_i - \min_{j=1}^m S_j$ 次操作的方案。
证明最优性。

与构造不一样的是，此时我们需要关注那些已经匹配的位置，并且给匹配的位置 $i$ 赋一个权 $w_i=0$ 。

令势能 $\Phi=\max_{i=1}^n S_i-\min_{j=1}^n S_j$ ，只需证明每一步势能至多减少 $1$ 即可。
1. 当操作序列是 $0101\dots 01$ 时，我们取两个相邻的操作位置 $i,j$ 并且 $s_i=0, s_j=1$ ，分别枚举 $t_i,t_j$ 的情况，会发现无论 $t_i,t_j$ 是怎么样的，都有：操作前后 $w_i+w_j$ 相等，即不影响 $S_j\sim S_n$ 的值；对于 $S_i\sim S_{j-1}$ ，操作后相当于整体 $+1$ 。
2. 当操作序列是 $1010\dots 10$ 时，我们取两个相邻的操作位置 $i,j$ 并且 $s_i=1,s_j=0$ ，分别枚举 $t_i,t_j$ 的情况，会发现无论 $t_i,t_j$ 是怎么样的，都有：操作前后 $w_i+w_j$ 相等，即不影响 $S_j\sim S_n$ 的值；对于 $S_i\sim S_{j-1}$ ，操作后相等于整体 $-1$ 。
所以，每次操作就是给一些连续的段至多 $\pm 1$ ，并且一次操作中这个加或减的符号是一样的。那么操作次数就一定不少于 $\Phi$ 。

这个代码是非常好写的，但是构造出来操作方案和证明是比较困难的。

AC Code。

[CF1763C] Another Array Problem

对于这种操作比较复杂并且难以简单比较的题目，我们首先要看一下理论最大值能是多少。

符号：无论进行多少次操作，数组中的元素永远是非负数。
最大值：设当前数组最大值为 $M$ ，不妨设当前这一步操作 $a_i>a_j$ ，如果 $a_i-a_j>M$ ，就有 $a_i>M+a_j\ge M$ ，即 $a_i>M$ ，这是不可能的。

如果初始状态下数组中最大值为 $M$ ，根据上面的结论，无论执行多少次操作，都有 $\forall 1\le i\le n, 0\le a_i\le M$ 。

那么如果能构造出一种方案使得所有的元素都达到 $M$ ，就一定是最大的。

如果 $n\ge 4$ ，位置足够，我们总可以在最大值的左边或右边操作两次清空，然后把这边全部变成 $M$ ，再把另一边也全部变成 $M$ 。

如果 $n=2$ ，那么答案是 $\max(a_1+a_2,2|a_1-a_2|)$ ；

如果 $n=3$ ，如果 $M$ 位于 $a_1$ 或者 $a_3$ ，类比 $n\ge 4$ 的情况，可以构造出 $3M$ ；如果 $M=a_2$ ，我们要么不操作，要么操作一次 $(1,2),(1,3),(2,3)$ ，操作之后就有新的 $M'$ 位于 $a_1$ 或 $a_3$ 了，这里可以写一个简单的 DFS 或者直接分类讨论。

AC Code。

[CF715B] Complete The Graph

如果不加边之前最短路已经小于 $L$ ，那么显然是没有解的；相反地，如果令所有未定边的权都是 $1$ ，最短路仍然大于 $L$ ，那么因为此时已经是最短路能达到的最小值了，所以也是没有解的。

否则，一定是有解的：考虑初始状态下未定边的权是 $1$ ，按照某个顺序给每一条未定边 $+1$ ，那么最短路要么不变、要么 $+1$ ，这样重复操作下去，类似于中值定理的感觉，它一定可以取到 $L$ 这个值。

问题在于我们如何给出一种操作方法，使得上文中所谓改变的过程能控制在能接受的有限步内。

感性地来看，每一次要尽量让未定边增加的值多一些。

这会引出另一个问题，就是我们找到的那一条最短路一定经过未定边吗？答案是一定的，考虑反证法，如果不经过，违背了我们一开始提出的有解的条件。

那么增加多少？我们希望让目前这一条路径的长度是 $L$ ，设当前路径的长度是 $L_0$ ，那么只要找一条未定边增加 $L-L_0$ 即可。

这能保证在能接受的有限步内吗？我们每进行一次操作，就会让经过某一条未定边的最短路的最小值 $\ge L$ （所有路径中的最短路，一定是经过某条边的所有路径的最短路），所以下一次找到小于 $L$ 的最短路就一定不会再次经过这一条边，而未定边的数量又是有限的，至多 $m$ 条，那么这样的复杂度就是 $O(mn\log n)$ 。

其实到这个程度就能够通过本题了，但是我们还可以进一步地进行一些优化：未定边的数量可以被缩小，因为我们一开始给所有边赋 $1$ 找到的最短路是小于 $L$ 的，那么我们可以只关心这一个路径上的未定边，把其它的未定边直接赋为 $\infty$ ，这仍然是一个有效的方案，因为有解的分析并不依赖于未定边的数量，它只依赖于是不是存在小于 $L$ 的路径。

那么此时未定边就是点的数量级了，复杂度变成了 $O(n^2\log n)$ 。

AC Code。

[CF2134D] Sliding Tree

最终状态是一条链驱使着我们思考直径相关的概念。

设 $d(T)$ 表示树 $T$ 的直径，那么 $T$ 是一条链的充要条件显然为 $d(T)=n$ 。

那么形式化地题面就是，给定一种变换 $f$ ，问至少多少次变换能使得 $d(T)=n$ 。

设 $T$ 的根是 $f$ 变换的 $b$ ，经过简单分类讨论（此处省略）可以看出 $d(f(T))\le d(T)+1$ 。

那么一定可以让 $d(f(T))=d(T)+1$ 吗？答案是肯定的，考虑 $d(T)\neq n$ 的树 $T$ ，它的直径上一定会有一个节点的度数 $\ge 3$ ，那么我们只要把直径用这个点拉伸开即可让 $d(f(T))=d(T)+1$ 了。

AC Code。