CodeForces 构造题专项解题报告（二）
\(\newcommand \m \mathbf\)\(\newcommand \oper \operatorname\)\(\newcommand \txt \texttt\)
\(\text{By DaiRuiChen007}\)
来源：CodeForces *constructive algorithms
推荐阅读：
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)\)
2. [1470D] - Strange Housing
- 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)\)
3. [1468H] - K and Medians
- 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)\)
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)\) 不难发现左边的每一列和右边的两列是一一对应的关系，故原命题得证
因此解决 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)\)
接下来解决困难版本，假如我们依然沿用原本的思路，那么我们就必须节省下一次 \(\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)\)
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)\)
接下来解决困难版本：根据在简单版本中的经验，我们可以把某个颜色的 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)\)
6. [1438D] - Powerful Ksenia
- 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)\)
7. [1437E] - Make It Increasing
- 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)\)
8. [1427D] - Unshuffling a Deck
- 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)\)
9. [1419E] - Decryption
- 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\)
10. [1416B] - Make Them Equal
- 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\) 的值
而对于所有的 \(a_i\)，我们操作完之后，\(a_1\) 一定会变大，不过我们在 \(a_1\) 增加之前必须付出一定的代价，这就是一个显然的贪心问题，按代价从小到大贪心即可
注意到每次把 \(a_i\) 转移到 \(a_1\) 上至多操作 \(2\) 次，而从 \(a_1\) 中将 \(\bar a\) 转移给 \(a_i\) 上操作 \(1\) 次
因此总操作数不超过 \(3n\) 次
时间复杂度 \(\Theta(n\log n)\)
标签：专项,land,元素,CodeForces,times,cdots,解题,Link,oplus From： https://www.cnblogs.com/DaiRuiChen007/p/17061399.html