CodeForces 构造题专项解题报告（二）

$\newcommand \m \mathbf$$\newcommand \oper \operatorname$$\newcommand \txt \texttt$

$\text{By DaiRuiChen007}$

1. [1481D] - AB Graph

Rating：2000
Status：Solve
Evaluate：Medium

首先，如果有一对点 $(i,j)$ 正向和反向字母相同，那么重复 $i\to j\to i\to j\to\cdots$ 即可

否则，每对点之间的两条边一定是 $\txt a,\txt b$ 各一个，假如 $m\bmod 2=1$，那么随便找一对点 $(i,j)$ 重复 $i\to j\to i\to j\to\cdots$ 即可

剩下的只有 $2\mid m$ 的情况，考虑得到的字符串中第 $\dfrac m2$ 个和第 $\dfrac m2+1$ 个字符，显然这两个字符需要相同，而且这两条边必然是连接三个不同的节点，因此找到一组 $(i,j,k)$使得 $j\to i=i\to k=\txt a $（事实上 $j\gets i=j\gets k=\txt b$，因此找 $\txt a$ 或 $\txt b$）没有区别

接下来考虑 $\dfrac m2$ 的奇偶性

若 $4\mid m$，那么形成的字符串形如 $\txt{bababa}\cdots\txt{ba}+\txt{ab}\cdots\txt{ababab}$，因此行走的路径应该是 $i\to (j\to i\to j\to\cdots \to j\to i)\to (k\to i\to k\to\cdots\to i\to k)$
若 $4\nmid m$，那么形成的字符串形如 $\txt{ababa}\cdots \txt{ba}+\txt{ab}\cdots\txt{babab}$，因此行走的路径应该是 $j\to (i\to j\to\cdots i\to j\to i)\to (k\to i\to k\to\cdots i\to k)$

分情况进行模拟即可

时间复杂度 $\Theta(n^2)$

Code Link

2. [1470D] - Strange Housing

Problem Link

Rating：2200
Status：No Solve
Evaluate：Hard

首先，原图 $\m G=(\m V,\m E)$ 在不连通的情况下必然无解，注意到如下的观察：

观察：

在图联通的情况下必然有解

对 $|\m V|$ 进行归纳，在 $|\m V|=1$ 的时候必然联通

否则，任意考虑一个节点 $v$ 加入 $\m G-v$ 中的过程，设所有与 $v$ 相连的点构成集合$N(v)$

若 $N(v)$ 中有黑色节点，则 $v$ 为白色依然联通

若 $N(v)$ 中无黑色节点，则 $v$ 为黑色依然联通

则原问题被转化为了构造 $\m G-v$ 这张图上的一个解，注意到 $|\m V|\gets |\m V|-1$，根据归纳假设得证

因此做一遍 BFS 即可

时间复杂度 $\Theta(n+m)$

Code Link

3. [1468H] - K and Medians

Problem Link

Rating：2200
Status：No Solve
Evaluate：Hard

首先，一次操作会删除 $k-1$ 个数，因此如果 $(n-m)\bmod (k-1)\ne 0$，那么必然无解

假设 $d=\dfrac{k-1}2$，那么一次操作可以看在 $\{a_i\}$ 中选定一个下标 $x$，并在 $x$ 的左边和右边各删除 $d$ 个元素

注意到如下的观察：

观察：

若 $(n-m)\bmod(k-1)=0$，那么当且仅当存在一个 $i\in[1,m]$ 使得 $1\sim n$ 的待删除元素中 $<b_i$ 和 $>b_i$ 都至少有 $d$ 个时，原问题有解

对待删除元素的数量进行归纳，显然当待删除元素数量为 $0$ 时一定有解

否则，考虑最后一次操作，保留的中位数一定是某个 $b_i$，而这就要求 $<b_i$ 和 $>b_i$ 的待删除元素都至少有 $d$ 个，如果存在这样的 $b_i$，假设操作时删除了 $a_{i_1}\sim a_{i_{k-1}}$，那么在这次操作之前，我们可以把 $a_{i_1}\sim a_{i_{k-1}} $ 全部看成需要保留的元素

那么我们只需要删除剩下的的 $(n-m)-(k-1)$ 个元素，由于 $(n-m)\bmod (k-1)=0$，那么一定能归纳到待删除元素数量为 $0$ 的情况

因此我们只需要证明，在保留 $a_{i_1}\sim a_{i_{k-1}}$ 之后，若 $(n-m)>(k-1)$，我们依然能够找到一个合法的操作位置来删除 $k-1$ 个元素即可

不妨假设原本 $<b_i$ 的待删除元素有 $x$ 个，$>b_i$ 的待删除元素有 $y$ 个，而在保留 $a_{i_1}\sim a_{i_{k-1}}$ 后 $<b_i$ 的还剩 $x-d=x'$ 个，而 $>b_i$ 的还剩 $y-d=y'$ 个

由于 $x+y=n-m,2\times d=k-1$，因此 $x+y\ge 4d$ 即 $x'+y'\ge 2d$，因此 $x'\ge d$ 和 $y'\ge d$ 中至少有一个成立，而同时成立的情况只需要继续操作 $b_i$ 即可，故我们假设 $x'> d>y'$：

设 $d-y'=r$，则 $x'\ge d+r$，那么 $x\ge 2d+r$，那么我们在最后一次操作时选择恢复这 $x$ 个元素中的第 $d+1\sim 2d$ 个待删除元素即可，此时在这些被恢复的元素中任选一个，其左侧剩下 $d$ 个带删除元素，右侧剩下 $x'-2d+y'\ge d$ 个元素，因此我们构造出了一种方法使得在剩下的 $(n-m)-(k-1)$ 个待删除元素中也能找到一个分界点，使得其左右的待删除元素都不少于 $d$ 个，故原命题得证

因此先判断 $(n-m)\bmod (k-1)$ 的值，然后找到一个这样的 $b_i$ 即可

时间复杂度 $\Theta(n)$

Code Link

4. [1451E] - Bitwise Queries (Easy Version) & (Hard Version)

Problem Link(E1) | Problem Link(E2)

Rating：2000 & 2300
Status：Hint
Evaluate：Medium

约定：用 $\land$ 表示按位与，$\lor$ 表示按位或，$\oplus$ 表示按位异或

先解决简单版本：

注意到在 $\land,\lor,\oplus$ 中，$\oplus$ 运算的性质是最好的，对于算式 $a\oplus b=c$，我们可以通过 $a,c$ 的值逆推 $b$

因此考虑先求出 $a_1\oplus a_2, a_1\oplus a_3,\cdots a_1\oplus a_n$ 的值，这需要 $n-1$ 次操作，那么我们的目标就转化为在 $3$ 次操作内求出 $a_1$ 的值

注意到如下的观察：

观察：

对于任意三个正整数 $a,b,c$：我们只需要知道 $(a\oplus b,b\oplus c,c\oplus a)$ 的值和 $(a\land b,b\land c,c\land a) $ 的值就可以确定 $(a,b,c)$ 的值

事实上由于 $\oplus$ 运算和 $\land$ 运算都是对不同位独立的，因此我们只需要解决 $a,b,c\in\{0,1\}$ 的情况就可以逐位确定 $a,b,c$ 的值

$(a,b,c)$ $(a\oplus b,b\oplus c,c\oplus a)$ $(a\land b,b\land c,c\land a) $

$(0,0,0)$ $(0,0,0)$ $(0,0,0)$

$(0,0,1)$ $(0,1,1)$ $(0,0,0)$

$(0,1,0)$ $(1,1,0)$ $(0,0,0)$

$(1,0,0)$ $(1,0,1)$ $(0,0,0)$

$(0,1,1)$ $(1,0,1)$ $(0,1,0)$

$(1,0,1)$ $(1,1,0)$ $(0,0,1)$

$(1,1,0)$ $(0,1,1)$ $(1,0,0)$

$(1,1,1)$ $(0,0,0)$ $(1,1,1)$

不难发现左边的每一列和右边的两列是一一对应的关系，故原命题得证

\((a,b,c)\)	\((a\oplus b,b\oplus c,c\oplus a)\)	$(a\land b,b\land c,c\land a) $
\((0,0,0)\)	\((0,0,0)\)	\((0,0,0)\)
\((0,0,1)\)	\((0,1,1)\)	\((0,0,0)\)
\((0,1,0)\)	\((1,1,0)\)	\((0,0,0)\)
\((1,0,0)\)	\((1,0,1)\)	\((0,0,0)\)
\((0,1,1)\)	\((1,0,1)\)	\((0,1,0)\)
\((1,0,1)\)	\((1,1,0)\)	\((0,0,1)\)
\((1,1,0)\)	\((0,1,1)\)	\((1,0,0)\)
\((1,1,1)\)	\((0,0,0)\)	\((1,1,1)\)

因此解决 E1 问题，我们只需要用剩下的 $3$ 次询问分别求出 $a_1\land a_2,a_2\land a_3,a_3\land a_1$ 的值就可以得到 $a_1$ 的值了

对于每一位枚举 $(a,b,c)$ 的 $2^3=8$ 中情况判断即可

时间复杂度 $\Theta(n)$

Code Link(E1)

接下来解决困难版本，假如我们依然沿用原本的思路，那么我们就必须节省下一次 $\land$ 询问

我们注意到 $a_i$ 的值域大小与 $a_i$ 的数量是相同的，因此我们想到对重复元素进行讨论：

若 $\{a_i\}$ 中存在 $(j,k)$ 使得 $a_j=a_k$

那么此时 $a_1\oplus a_j=a_1\oplus a_k$，因此我们能在前 $n-1$ 次询问内判断这样的 $(j,k)$ 是否存在

而在 $a_j=a_k$ 时，我们有 $a_j\land a_k=a_j=a_k$，因此 $1$ 次询问就可以确定 $a_j$ 的值，而又因为 $a_1\oplus a_j$ 的值已知，那么我们可以在一次额外询问后知道 $a_1$ 的值从而推知整个 $\{a_i\}$ 的值
若 $\{a_i\}$ 两两不同

那么此时考虑 $n-1$ 这个特殊值，由于 $\{a_i\}$ 的值恰好是 $1\sim n-1$，那么我们知道恰好存在一个 $a_i$ 使得 $a_1\oplus a_i=n-1$，而这个 $a_i$ 恰好是 $a_1$ 按位取反后得到的值，这意味着 $a_1\land a_i=0$，那么我们就节省了一次 $\land$ 询问，而这样就能在两次额外讯问内得到 $a_1$ 的值

所以通过对 $\{a_i\}$ 中重复元素的分类讨论，我们承成功地节省了一次询问，从而可以通过困难版本的问题

时间复杂度 $\Theta(n)$

Code Link(E2)

5. [1450C] - Errich-Tac-Toe (Easy Version) & (Hard Version)

Problem Link(C1) | Problem Link(C2)

Rating：2100 & 2300
Status：No Solve
Evaluate：Hard

为了方便表达，记 $\left\lfloor\dfrac k3\right\rfloor=d$

考虑对整个网格按 $(i+j)\bmod 3$ 进行染色，这样每个 $1\times 3$ 或 $3\times 1$ 的连续方格中都恰好有 $0,1,2$ 三种颜色各一

对于简单版本，我们只需要将某种颜色的格子上的 X 全部变成 O 即可，正确性是由于每连续的三个格子中都至少有一个格子上只出现 . 或 O 导出的

而我们需要证明：总存在一种颜色的 X 的出现次数 $\le d$ 次

证：

这一命题是显然的，根据抽屉原理即证

或者说，当三种颜色的 X 出现次数都 $>d$ 次时，会有 $k>3d$ 成立，这显然是违反定义的，故这样的颜色一定是存在的

先统计出每种颜色的 X 的个数，任选一个出现次数 $\le d$ 的并把所有这种颜色的 X 变成 O 即可

时间复杂度 $\Theta(n^2)$

Code Link(C1)

接下来解决困难版本：根据在简单版本中的经验，我们可以把某个颜色的 X 全部变成 O，然后把另一个颜色的 O 全部变成 X，而这是由于每连续的三个格子中，如果不存在 .，那么就会同时出现至少一个 X 和一个 O

同样，我们要证明存在一种选取颜色的方法使得其总代价不超过 $d$

证：

假设在颜色为 $i$ 的格子中，X 有 $a_i$ 个，O 有 $b_i$ 个，那么某种操作的代价就可以表示成 $a_i+b_j$，其中 $i\ne j$ 且 $i,j\in\{0,1,2\}$

考虑三种操作的代价：$(a_0+b_1),(a_1+b_2),(a_2+b_0)$，显然 $(a_0+b_1)+(a_1+b_2)+(a_2+b_0)=k$

根据抽屉原理，这三个代价中至少有一个 $\le d$，故原命题得证

那么我们枚举出合法的两个颜色 $i,j$ 即可

时间复杂度 $\Theta(n^2)$

Code Link(C2)

6. [1438D] - Powerful Ksenia

Problem Link

Rating：2200
Status：Solve
Evaluate：Medium

首先发现 $a_i\oplus a_j\oplus a_k$ 这一形态比较复杂，而我们留意到 $x\oplus y\oplus y=x$，也就是一次操作可以将某两个相同的元素赋成另一个元素的值，考虑用这个操作作为基础来解决问题

注意到 $(a_i\oplus a_j\oplus a_k)\oplus(a_i\oplus a_j\oplus a_k)\oplus(a_i\oplus a_j\oplus a_k)=a_i\oplus a_j\oplus a_k$，也就是说每次操作都不会改变整个序列的异或和，记为 $x$

显然，$x$ 的值应该和最终序列的异或和相等，而最终的序列的异或和，在 $n$ 为偶数的情况下，应该为 $0$，而在 $n$ 为奇数的情况下，则等于这 $n$ 个相等的数的值

先考虑 $2\mid n$ 的情况，若此时 $x\ne 0$，那么必然无解，接下来考虑 $x=0$ 的情况，根据我们最开始的观察，我们应该想办法创造两个相等的数，显然，我们可以再用一次操作来创造这样的一对元素，形式化的说，每次操作 $(2i,2i+1,2i+2)$ 此时 $a_{2i}=a_{2i+1}$，再操作 $(1,2i,2i+1)$ 就可以使 $a_{2i}=a_{2i+1}$，而到最后由于 $2\mid n$，因此会剩下一个 $a_n$ 没被操作，但由于整个序列的异或和始终为 $0$，而 $a_1\sim a_{n-1}$ 已经全部相等，那么 $a_n$ 的值也只能和 $a_1\sim a_{n-1}$ 相同

再考虑 $2\nmid n$ 的情况，此时整个序列的异或和 $x$ 应该就是最终每个数的值，根据上面的观察，我们应该想办法先创造一个 $=x$ 的元素，这也很简单，不断操作 $(1,2i,2i+1)$ 最终就会让 $a_1=x$，而这个时候恰好有 $a_{2i}=a_{2i+1}$，因此再从头开始操作 $(1,2i,2i+1)$ 就能让整个序列的值变成 $x$

计算一下操作次数

$2\mid n$ 时，对于每个 $i$ 操作两次，而 $1\le i<\dfrac n2$，因此操作次数为 $2\times \left(\dfrac n2-1\right)=n-2$ 次
$2\nmid n$ 时，对于每个 $i$ 操作两次，而 $1\le i\le \dfrac{n-1}2$，因此操作次数为 $2\times\dfrac{n-1}2=n-1$ 次

因此以上两种情况均满足题目限制，按照分析过程模拟即可

时间复杂度 $\Theta(n)$

Code Link

7. [1437E] - Make It Increasing

Problem Link

Rating：2200
Status：Solve
Evaluate：Easy

先令 $a_i\gets a_i-i$，使严格递增转化为非严格递增的问题

通过 $b_i$ 把 $\{a_i\}$ 分成 $m+1$ 个形如 $[b_{i-1},b_i]$ 的段（令 $b_0=0,b_{m+1}=n+1$），而我们只需要分别处理每个段的答案

对于一个独立的段 $[b_{i-1},b_i]$，只有第一个最后一个元素不可改变，注意到不改变的元素一定是原本就不下降的，那么原命题可以转化为求出序列 $a[b_{i-1}+1\cdots b_i-1]$值域在 $[a_{b_{i-1}},a_{b_{i}}]$ 中的最长不下降子序列的长度

这就变成了一个非常经典的求最长不下降子序列的 dp 问题，我们只需要考虑所有值 $\ge a_{b_{i-1}}$ 的元素，并且最终返回 $dp_{b_i}$ 的值即可

使用二分优化或离散化 + 树状数组优化均可

时间复杂度 $\Theta(n\log n)$

Code Link

8. [1427D] - Unshuffling a Deck

Problem Link

Rating：2000
Status：No Solve
Evaluate：Hard

考虑归纳求解，即每次复位 $i$ 使得 $a_i=i$，第一次让 $a_1=1$ 是很简单的，不过第二次想让 $a_2=2$ 时候，$1$ 显然就不会在位置 $1$ 上了

不过当在复位 $2$ 的时候，我们可以考虑让 $a_{n-1}=2,a_n=1$，也就是把序列变成 $[\cdots\cdots i,i-1,\cdots ,1]$ 的形式

因此我们只需要每次使得序列的形态变化为 $[1,2,3,\cdots i-1\cdots]\to[\cdots,i,i-1\cdots 3,2,1]$ 或 $[\cdots,i-1\cdots 3,2,1]\to[1,2,3,\cdots i-1,i\cdots]$

而这很简单，具体操作方式如下：

对于第一种形式，设原来 $a_x=i$，此时 $\{d\}=\left\{\underbrace{1,1,\cdots ,1}_{i-1\text{ times}},x-(i-1),n-x\right\}$
对于第二种形式，设原来 $a_x=i$，此时 $\{d\}=\left\{x-1,n-(x-1)-(i-1),\underbrace{1,1,\cdots ,1}_{i-1\text{ times}}\right\}$

模拟执行 $n$ 次即可

时间复杂度 $\Theta(n^2)$

Code Link

9. [1419E] - Decryption

Problem Link

Rating：2100
Status：Solve
Evaluate：Easy

显然，操作次数等于 $n$ 减去相邻的两个数不互质的数对数，因此我们只需要最大化相邻数不互质的对数

假设 $n$ 的标准分解形式为 $n=\prod _{i=1}^k p_i^{a_i}$，一个显然的想法是构造 $\{p_1,\cdots ,p_1\times p_2,p_2\cdots p_2\times p_3,p_3,\cdots\cdots p_{k-1}\times p_k,p_k\cdots,p_k\times p_1\}$，其中 $p_1,\cdots$ 里面可以填所有整除 $p_1$ 的因子，而这样的构造一定是满足任意两个相邻的元素都不互质的，此时答案为 $0$

考虑边界情况：

$k=1$ 时：此时无论怎么排列都有公约数 $p_1$，答案为 $0$
$k=2$ 时：
- 若 $a_1=a_2=1$，即 $n=p_1\times p_2$：无论如何 $p_1$ 和 $p_2$ 都会相邻，构造排列 $\{p_1,p_1\times p_2,p_2\}$，答案为 $1$
- 若 $a_1\ge 2$ 或 $a_2\ge 2$：设 $a_1\ge 2$ 则 $p_1^2\times p_2\mid n$，此时构造排列 $\{p_1,\cdots,p_1\times p_2,p_2,\cdots,p_1^2\times p_2\}$，答案为 $0$
$k>2$ 时：按上述方法构造，答案为 $0$

枚举每个 $\dfrac n{p_i}$ 的约数，乘上 $p_i$ 就能得到 $n$ 的约数中 $p_i$ 的倍数，模拟即可

时间复杂度 $\Theta(k\sqrt n)$，其中 $k\le 10$

Code Link

10. [1416B] - Make Them Equal

Problem Link

Rating：2000
Status：Data
Evaluate：Easy

一个显然的观察，每次操作不会影响 $\{a_i\}$ 的综合，因此最终所有 $a_i$ 会与 $\bar a=\dfrac 1n\sum_{i=1}^n a_i$，即 $\bar a$ 相等，若 $\bar a\not\in\mathbb Z$，则显然无解

在剩下的情况中，我们有一个朴素的思路：把所有的数都集中到 $a_1$ 上，然后再用 $a_1$ 给每个 $a_i$ 加上 $\bar a$

那么我们只需要分析：对于某个 $a_i$ 如何令 $a_1\gets a_1+a_i,a_i\gets 0$，首先发现如果我们想减少 $a_i$ 的值直到 $0$，那么在减少之前，一定有 $i\mid a_i$，因此我们先从 $a_1$ 向 $a_i$ 转移 $-a_i\bmod i$ 的值，然后再从 $a_i$ 向 $i$ 转移 $\left\lceil\dfrac {a_i}i\right\rceil\times i$ 的值