专题训练 - 构造 I

[CF1930C] Lexicographically Largest

对于 $a_i$，它能够贡献给 $b$ 的数 $c_i$ 的范围是 $a_i+1\le c_i\le a_i+i$。

如果我们对于 $c_i$ 的所有取值，都能构造出一个顺序满足这样的取值，那么答案就是把 $a_i+i$ 排个序，然后从大到小依次填。如果有重复的数字，比如 $5,5,5$，那么我们就填 $5,4,3$，以此类推。

问题是，我们怎么证明 $c_i$ 的所有取值总能构造出一个顺序满足条件呢？

不妨从 $n$ 小的情况入手。$n=1,2$ 显然可以，然后我们尝试数学归纳法。

当 $n=k$ 可以时，对于 $n=k+1$，显然 $a_{k+1}$ 插入任何一种前 $k$ 个元素的顺序时，不会改变前 $k$ 个元素的值，因此 $c_{k+1}$ 可以是 $a_{k+1}+k+1\sim a_{k+1}+1$ 的任意一个值，同时前 $k$ 个数根据归纳假设也可以，所以结论得证。

AC Code。

[CF1506D] Epic Transformation

一个自然的想法是用同一个元素不停地消掉别人。如果最终 $x$ 剩下了 $\ge 2$ 个，那么考虑把配对 $(y,z),y\neq x,z\neq x$ 变成 $(x,y)$ 与 $(x,z)$，答案一定更优，于是当 $x$ 足够多时，一定是用 $x$ 不停地消别人。

问题是，具体是多少叫做足够多？设 $x$ 是出现次数最多的元素，它出现了 $S$ 次，那么我们只用 $x$ 消剩下的元素，这要求 $n-S\le S$ 即 $2S \ge n$。于是我们证明出了 $2S\ge n$ 时，答案就是 $n-2(n-S)=2S-n$。

接下来的问题是，如果 $S$ 不足够大呢？

当 $2S<n$ 时，一个比较自然的猜想是，尽量拿最多的两个人去匹配。

我们来模拟这一过程，由于 $2S\le n-1$，所以起码有两个不同的元素，它们的出现次数是 $c_1\ge c_2\ge c_3\ge \dots\ge c_k$，满足 $\sum c_i=n$，并且 $c_1\ge c_2\ge 1$（否则无法继续操作），那么进行一次操作之后 $c_1'\gets c_1-1$，$c_2'\gets c_2-1$，$c_i'\gets c_i(i\ge 3)$此时 $n'=\sum c_i'=n-2$。

操作之后，出现次数最大值 $S'$ 只有可能是 $c_1'$ 或 $c_3'$，我们来分别讨论，看此时是否仍然满足 $2S'<n'$。

1. 若 $S'=c_1'$，说明 $c_1-1\ge c_3$，此时 $2S'=2(c_1-1)=2S-2<n-2=n'$；

2. 若 $S'=c_3'$，说明 $c_1-1< c_3$ 即 $c_3\ge c_1$，又因为 $c_3\le c_1$，所以一定是 $c_3=c_1$，就有 $c_1=c_2=c_3$。

   又因为 $c_1\ge 1$，于是 $c_1+c_2+c_3=3c_1=3S\le n$，于是 $2S'=2c_1=2S\le \cfrac{2}{3}n$。

   如果 $\cfrac{2}{3}n\ge n-2$，有 $n\le 6$，此时可以手玩所有情况，验证只要有 $2S<n$ 就能推出下文给出的结论。

   由此，几乎所有情况都满足 $2S'<n'$ 仍然成立。

也就是说，不断重复这个操作，直到 $c_1\ge c_2\ge 1$ 不成立，也就是说 $c_2=0$，此时 $c_1$ 只能为 $0$ 或 $1$，若 $c_1\ge 2$ 那么上一步 $n=c_1+2$，有 $2S=2c_1\ge c_1+2$，落入了 $2S\ge n$ 的情况。

所以我们证明出来了 $2S<n$ 时一定可以两两相消直到剩下 $n\bmod 2$ 个元素。

AC Code。

[CF1375C] Element Extermination

逆向思考，最后一步一定是两个元素 $x,y$ 并且满足 $x< y$，我们随便选择一个元素让序列只剩一个。

观察这个操作的定义，然后再关注，既然最后两个元素的时候，$x$ 是开头，$y$ 是结尾，那么它们与一开始的开头和结尾有什么关系？

对于 $a_1$，它只能删右边或者被右边删掉。如果被右边删掉，那么剩下的一定是比 $a_1$ 更大，于是最后 $a_1\le x$，同理 $y\le a_n$。

所以我们得到了一个必要条件 $a_1<a_n$，事实上，这也是充分条件。

为什么？我们尝试构造一个消除的方法。

首先，一个元素可以疯狂地删掉左边比它更小的元素。基于这个朴素的想法，我们希望找到一个 $a_r$，使得 $a_r$ 比它左边的元素都大。

怎么找呢？这就是一个非常技巧性的思维跳跃了，我们找 $a_1$ 右边第一个比 $a_1$ 大的元素，记作 $a_r$，那么 $a_1$ 与 $a_r$ 之间的元素都可以被 $a_r$ 删掉，此后 $a_r$ 也可以被 $a_1$ 删掉。

不断重复这一步骤，直到找到的 $a_r$ 是 $a_n$，那此时再删掉它们之间的元素，就只剩下 $a_1$ 和 $a_n$ 了。

AC Code。

[CF2120C] Divine Tree

我们先考虑能构造出来的最小值和最大值。

先考虑最小值，由于 $d(u)\ge 1$ 天然成立，如果我们把 $1$ 放到根，那么 $d(u)=1$，所以最小值就是 $n$。

再考虑最大值，由于 $d(u)$ 是 $u$ 到根上的编号最小值，那么 $d(u)\le u$ 一定成立，如果把 $n$ 放到根上，做一个菊花图，那么每一个 $d(u)=u$ 就成立，所以最大值就是 $\sum_{u=1}^n u=\cfrac{n(n+1)}{2}$。

那我们接下来，对于给定的 $m$，需要构造出恰好 $\sum_{u=1}^n d(u)=m$，这怎么办？

自然地，从特殊的树形态入手，看一条链会怎么样。如果想让一条链是最小值 $n$，只需要把 $1$ 放到根上；如果想让它是最大值，那么需要从根到叶子按照 $n,n-1,n-2,\dots,1$ 的顺序排列。

考虑把 $1,2,\dots,n$ 进行重排，由于我们希望较少的元素会被影响，所以一个自然的想法是把 $1$ 作为屏障来使用：

$$\begin{aligned} 2,1,3,\dots,n&\mapsto n+1\\ 3,1,2,\dots,n&\mapsto n+2\\ 4,1,2,\dots,n&\mapsto n+3\\ &\vdots\\ n,1,2,\dots,n-1&\mapsto n+n-1\\ n,2,1,3,\dots, n-1&\mapsto n+n-1+1\\ n,3,1,2,\dots, n-1&\mapsto n+n-1+2 \end{aligned}$$

这样构造出来的方式的值一点点增加，所以按照这个想法做下去就可以了。

AC Code。

[CF1758C] Almost All Multiples

对于这种题目，首先的想法应该是如果没有他令的 $p_1=x,p_n=1$ 会怎么样？

很快就会发现，如果没有这个限制构造出来的一定就是 $1,2,\dots,n$。

类比这个想法，如果第一项是 $x$，那么 $2\sim x-1$ 的位置，一定就是 $2,3,\dots,x-1$，这是因为如果前面不放这些数，后面不可能能放这些数，所以它们的位置是定死的。

接下来考虑 $x$ 位置填什么。我们只要想一下如果填了 $2x,3x$ 等等，不妨设填的是 $kx$，接下来 $x+1\sim kx-1$ 的位置和 $2\sim x-1$ 类似，都是唯一固定好的，只能填 $x+1,x+2,\dots,kx-1$，然后 $kx$ 面临的处境和之前一样。

问题是，什么时候是个头？我们知道每次填写的 $kx$ 都要满足 $\le n$，只要它小于 $n$ 就会面临上面所说的相似的局面，并且下一次填的数一定比这一次更大，所以最终一定填的是 $n$。

这样这个问题就被解决掉了，首先一定要 $x\mid n$，否则无解；令 $d=\cfrac{x}{n}$，那么每一次乘的都是 $d$ 的因子，我们取它最小的非平凡因子 $i$，然后 $d\gets d/i$，显然这样生成的序列字典序是最小的。

AC Code。

[CF1761C] Set Construction

给定的矩阵可以看作邻接矩阵，那么它一定是一个 DAG，可以先进行一个拓扑排序，从末尾开始考虑。

我们希望，一个集合包含它所有的子孙，被它的祖先包含，同时又不能包含别的集合。

对于不能包含，只需要让每一个集合有一个独特的元素，然后处理包含关系的时候再并入这个元素就能做到了。

这样的话，如果 $u$ 不是 $v$ 的子孙，那么 $u$ 一定有一个独特的元素，并且 $v$ 没有，那么这里就没有包含关系。

具体地说，只要令每一个集合初始的时候加上自己的编号这个元素就可以做到这一点。

代码里用 int128 来二进制地表示一个集合。

AC Code。

[CF1733D1] Zero-One (Easy Version)

我们可以把 $a$ 与 $b$ 每一个位置异或一下，构造一个新的二进制串 $A_1,A_2,\dots,A_n$。

那么给定的操作就是选定两个 $l,r$ 并且翻转 $A_l,A_r$，问将 $A$ 串变成全 $0$ 需要的最小花费。

容易知道这个操作并不会改变 $A$ 串中 $1$ 的数量的奇偶性，并且如果有偶数个 $1$，我总可以两两配对全部消掉。

因此可以将 $A$ 串变成全 $0$ 当且仅当 $1$ 的个数是偶数，设个数是 $S$。

这个版本的题目中，保证了 $x\ge y$，即如果能隔项消除，我们一定不会邻项消除。

所以，如果 $S\ge 4$，直接交叉着消即可。

为什么？原因是，假设有 $S$ 个 $1$，那么消除它们至少需要 $\cfrac{S}{2}$ 步，每一步的费用至少是 $y$，而我们交叉消的费用就是 $\cfrac{S}{2}y$，所以这就是最小花费。

如果 $S=2$，比较一下邻项消除和借助一个隔着的节点消的费用即可；如果 $S=0$ 自然输出 $0$。

AC Code。

[CF1733D2] Zero-One (Hard Version)

如果 $x\ge y$，直接复用上个题目的代码即可，下面我们考虑 $x<y$ 的情况。

此时我们不能直接构造出一个最小花费了，所以我们重新审视这个抽象出来的数学模型。

我们最终的目的是让 $A$ 变成全 $0$，每一次操作有可能让 $1$ 的个数 $S$ 进行 $+2,0,-2$。

执行 $+2$ 的操作一定是不优的，所以我们真正执行的只有 $0$ 和 $-2$，并且最后一步一定是 $-2$。

那么 $S$ 的变化序列可能如下：$0,0,-2,0,0,-2,-2,0,\dots,-2$。

我们把连续的 $0$ 和 $-2$ 放到一起看，这一定是连续若干次邻项消除。为什么？因为如果这些次数有隔项消除，花费是 $mx+ny$，不如直接一步到位地一个 $y$ 消掉两个 $1$。

如果 $-2$ 前面没有 $0$，那么是一次邻项消除或者一次隔项消除。

所以这样分析下来，我们选择了 $\cfrac{S}{2}$ 对 $1$，进行若干次邻项消除（花费 $Lx$，其中 $L$ 是这对 $1$ 的距离），或者一次隔项消除（花费 $y$）。

对于此类数轴模型，通常将匹配的点对视作线段，并考察线段间的几何关系：

1. 相交但不包含，如 $(p,q)$ 和 $(a,b)$ 构成 $p<a<q<b$，那么我们可以构造出 $(p,a)$ 和 $(q,b)$ 这两个配对，原始花费一定不会比得到的花费更优。

2. 嵌套关系：

   • 如果外层使用了若干次邻项消除，说明外层的长度 $L$ 使得 $Lx\le y$，那么内层长度比 $L$ 小，它们也都会选择若干次邻项消除，此时花费与距离的和成正比。

     我们可以构造说明一定不会嵌套：这些点按照最近的点两两配对，这样的所有距离之和小于原先最外层一个线段的距离，这样一定比嵌套结构更优。

   • 如果外层使用隔项消除，那么内层如果使用隔项消除，可以将这四个点重新分配成不相交的线段，这样的花费与原先相等；

     如果内层使用若干次邻项消除，根据上文，内层不能再嵌套内层了。

综上所述，最优解如果有嵌套，至多只会嵌套一层，并且外层是隔项，内层是邻项。

我们给 $dp$ 加一个状态 $0/1$ 表示在最外层或一个线段的内层，那么转移就是：

1. 最外层邻项消除：$dp(i,0)\gets dp(i-2,0) + x(p_i-p_{i-2})$
2. 关闭一个开放的线段：$dp(i,0)\gets dp(i-1,1)+y$
3. 进入一个线段内部：$dp(i,1)\gets dp(i-1,0)$
4. 一个线段内部的邻项消除：$dp(i,1)\gets dp(i-2,1)+x(p_i-p_{i-2})$

AC Code。

[CF2145D] Inversion Value of a Permutation

注意 inversion value 的定义，它是存在逆序对的 subsegment 的数量，并非逆序对的数量。

存在性的数数一般都不是很好做，我们可以看它的反面，那就是不存在逆序对的 subsegment 的数量，现在我们统计这种 $(l,r)$ 的数量。

不存在逆序对，那就是一段 $(l,r)$ 满足 $a_l<a_{l+1}<\cdots<a_r$。

很自然地，我们可以对每个满足要求的 $(l,r)$ 尽可能向左右延，直到不能延为止。

对于这样一个极大的 $(l,r)$，假设它的长度是 $L=r-l+1$，那么它对我们要统计的数量的贡献是 $\binom{L}{2}$。

显然，任何一个序列，都是一堆这种极大的 $(l,r)$ 拼在一起的。因为你无论如何都能把这个序列划分成若干个极大的首尾相接的 $(l,r)$，并且每一个极大的 $(l,r)$ 都是孤立的，即整个序列的贡献就是每一段的贡献之和。

因此，现在的问题就转化成了，我们需要构造一组 $L_1,L_2,\dots,L_k$ 满足 $\sum L_i=n$ 且 $\sum \binom{L_i}{2}=\binom{n}{2}-k$。

设 $dp_{i,j,k}$ 表示考虑 $L$ 的值为前 $i$ 个数，$\sum L=j$，$\sum\binom{L}{2}=k$ 是否存在，并且需要记录 $pre_{i,j,k}$ 表示当前状态从哪个状态转移过来。

转移的话，枚举 $l\ge 0$ 个 $i+1$，会有 $dp_{i+1,j+l(i+1),k+l\binom{i+1}{2}}\gets dp_{i,j,k}$

最终构造只要从 $n-L+1,n-L+2,\dots,n$ 这样入手就行了。

AC Code。

[CF1451E2] Bitwise Queries (Hard Version)

首先使用 $n-1$ 次操作询问出 $a_1\oplus a_i(2\le i\le n)$，然后我们只需要求出某一个 $a_i$ 就可以求出整个序列了。

由于 $x\lor y=x\oplus y\oplus(x\land y)$，事实上此时已经可以求出任意两个 $a_i,a_j$ 的异或和，所以我们可以只考虑 $\land$。

下面假设你询问了 $a_i\land a_j$，下一次再询问，不可能是另外两个完全不同的位置。这是因为目前为止我们已知的所有信息都是对称的，对称的话就势必不能解出唯一解，除非你解出来的两个解是相等的，显然数据并不能保证这一点。

不妨设已知 $a_i\land a_j$ 与 $a_j\land a_k$，其中 $i,j,k$ 两两不同，接下来我们考虑某个二进制位的情况。

1. 若 $a_i\land a_j=1$ 或者 $a_j\land a_k=1$，那么 $a_j=1$。
2. 否则，若 $a_i\oplus a_j=0$ 或者 $a_j\oplus a_k=0$，那么 $a_j=0$。
3. 否则，此时我们可以推出 $\{a_i,a_j\}=\{a_j,a_k\}=\{0,1\}$，枚举不难发现只能是 $(a_i,a_j,a_k)=(0,1,0)$ 或 $(1,0,1)$。

我们会发现，最后的情况是无法确定出来到底是哪一种的。如果是 Easy Version 允许询问 $n+2$ 次，只要询问 $a_i\land a_k$ 就好了。

那么，我们如何省掉这一次询问？这就必然和题目保证的特殊数据范围有关系了。

不难发现取值范围 $0\sim n-1$ 有 $n$ 个不同的数，所以如果 $a_1\sim a_n$ 两两不同，那么它们一定是 $0\sim n-1$ 的一个排列。

在考虑这种特殊的情况之前，我们先来看如果存在两个相同的元素该怎么办。

1. 如果存在某个 $a_i,i=2\sim k$ 满足 $a_1=a_i$，这等价于 $a_1\oplus a_i=0$；
2. 如果存在某对 $2\le i,j\le k,i\neq j$ 满足 $a_i=a_j$，这等价于 $a_1\oplus a_i=a_1\oplus a_j$。

如果存在这样的情况，我们只需要问这两个位置的 $\land$ 或者 $\lor$，就可以求出这个位置的取值，然后解出每一个值了。

好，下面再看 $a_1\sim a_n$ 组成 $0\sim n-1$ 的排列这一情况。由于 $n$ 是 $2$ 的幂，所以任意两个 $0\sim n-1$ 的数异或起来仍然在 $0\sim n-1$ 中，因此 $a_1\oplus a_2\sim a_1\oplus a_n$ 一定是 $1\sim n-1$ 的一个排列（如果有 $0$ 是上一种情况）。

那么就必然存在一个 $a_k$ 使得 $a_1\oplus a_k=n-1$。这有什么特殊的？因为这两个数异或起来二进制全 $1$，那么它们不可能有两个位置都是 $1$，于是 $a_1\land a_k=0$，这就可以帮我们省掉一次询问。

AC Code。