代码源挑战赛 Round 52 题解 - 代码源竞赛平台

T1

100%

题目要求判断是否能通过若干次比赛，恰好将所有的传统题和交互题都放到比赛中。

根据题意，每场比赛恰好包含 $1$ 道之前未被放进比赛的传统题，这意味着如果想要把所有传统题用完，比赛的场数必须恰好为 $a$ 场。

同时，每场比赛至少包含 $2$ 道之前未被放进比赛的交互题。这意味着在 $a$ 场比赛中，总共至少需要消耗 $2a$ 道交互题。因此，必须满足交互题的总数 $b \ge 2a$。

如果 $b \ge 2a$，我们完全可以给前 $a-1$ 场比赛每场恰好分配 $2$ 道交互题，然后将剩下所有的 $b - 2(a-1)$ 道交互题全部分配给最后一场比赛。由于 $b - 2a + 2 \ge 2$，最后一场比赛也满足至少 $2$ 道交互题的条件。

因此，只需要判断 $b \ge 2a$ 是否成立。成立输出 NOI，不成立输出 NOIP。

时间复杂度 $O(1)$。

T2

100%

根据题意，发生错乱的字符串变化规律为 b 和 d 互换，p 和 q 互换。

不难发现，如果我们对错乱后的字符串再次进行相同的互换操作，就可以恢复出原本的字符串（因为改变两次等于没有改变）。

因此，我们只需要遍历输入的字符串 $s$，遇到 b 就将其修改为 d，遇到 d 就将其修改为 b；遇到 p 就将其修改为 q，遇到 q 就将其修改为 p。对于其他的字符，保持原样即可。

时间复杂度 $O(n)$。

T3

100%

分析两种法术的具体的操作情况：

• 法术 $1$（删除最左侧两个元素，在最右侧插入它们的和，然后循环右移一位）：等价于直接将序列最左侧的两个元素合并为它们的和，并在原位置保留，其它元素位置不变。
• 法术 $2$（删除最右侧两个元素，在最左侧插入它们的和，然后循环左移一位）：等价于直接将序列最右侧的两个元素合并为它们的和，并在原位置保留，其它元素位置不变。

因此，所有的法术仅仅是将 $A$ 的某一个前缀合并为了一个元素，或者将某一个后缀合并为了一个元素。 这意味着经过一系列操作后得到的序列 $B$，其构成必定满足以下形式：

1. $B$ 的第一个元素 $b_1$ 等于 $A$ 的某个前缀和，设其由 $A[1 \dots L]$ 合并而来。
2. $B$ 的最后一个元素 $b_m$ 等于 $A$ 的某个后缀和，设其由 $A[R \dots n]$ 合并而来。
3. 如果 $m \ge 3$，$B$ 中间的元素 $b_2, \dots, b_{m-1}$ 必须与 $A$ 中未被合并的元素 $a_{L+1}, \dots, a_{R-1}$ 完全一一对应。

由于 $A$ 中的元素均为正整数，其前缀和与后缀和都是严格单调递增的。因此，可以通过寻找与 $b_1$ 相等的前缀和来唯一确定分界点 $L$，寻找与 $b_m$ 相等的后缀和来唯一确定分界点 $R$。

• 如果 $m=1$，只需判断 $A$ 的所有元素之和是否等于 $b_1$。
• 如果 $m \ge 2$，我们尝试寻找上述唯一的 $L$ 和 $R$。若不存在这样的 $L$ 或 $R$，则输出 No。 找到 $L$ 和 $R$ 后，判断是否满足 $R - L = m - 1$（即中间剩余的元素个数正好为 $m-2$）。若满足，再依次比对 $A[L+1 \dots R-1]$ 是否与 $B[2 \dots m-1]$ 对应位置上的元素完全相等。若全都满足，则输出 Yes，否则输出 No。

单次测试用例的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

T4

100 %

对于非摩卡串（即 01 交替出现的序列），其最重要的性质是：任意相邻的两个字符都不相同。 为了方便处理相邻字符的关系，我们可以构造一个长度为 $n-1$ 的数组 $c$：如果原字符串中 $s_i \neq s_{i+1}$，则 $c_i = 1$；如果 $s_i = s_{i+1}$，则 $c_i = 0$（其中 $1 \le i < n$）。

那么，原序列中一段长度为 $L$ 的非摩卡子串，恰好等价于差分数组 $c$ 中一段长度为 $L-1$ 的全 $1$ 连续子数组。

接下来考虑区间翻转操作对差分数组的影响：

当我们将原序列区间 $[l, r]$ 内的字符全部翻转时，区间内部的相邻字符同时翻转，它们是否相同的关系保持不变；区间外部的字符未被修改，相邻关系自然也保持不变。

只有边界处的相邻关系发生了改变，即 $s_{l-1}$ 与 $s_l$ 的关系，以及 $s_r$ 与 $s_{r+1}$ 的关系。 因此，对原序列执行一次区间翻转操作，等价于在差分数组 $c$ 中将最多两个元素的值翻转（即 $c_{l-1}$ 变为 $1-c_{l-1}$，$c_r$ 变为 $1-c_r$，若下标越界则忽略）。

既然每次操作最多可以改变差分数组中的 $2$ 个元素，那么执行至多 $k$ 次操作，就最多可以改变差分数组中的 $2k$ 个元素。 并且，任意挑选差分数组中的两个元素 $c_x$ 和 $c_y$（$x < y$），我们总可以通过翻转原序列的 $[x+1, y]$ 区间来恰好同时改变这两个元素的值。

于是原问题被转化为了：在只包含 0 和 1 的差分数组 $c$ 中，找到一个最长的连续子数组，使得该子数组中 0 的个数不超过 $2k$。只要将这些 0 通过操作全部变为 1，该子数组就能对应一个极长的非摩卡子串。

问题转换到这里，做法就比较多了。双指针或者二分查找都是可以的，下面是二分查找的做法：

先对 $1 - c_i$ 做一次前缀和 $pre$，枚举左端点 $L$，然后在前缀和数组上用二分查找找到 $R$ 满足 $pre[R] - pre[L - 1] \leq 2 k$ 的最大 $R$（表示把 $[L,R]$ 内的所有 0 全部变成 1），然后记录答案即可。

时间复杂度 $O(n \log n)$ 或 $O(n)$，空间复杂度 $O(n)$。

T5

30%

对于 $n \le 15$ 的数据，由于最多可以提问 $17$ 次，我们可以直接使用 $n$ 次询问来确定整个排列。 第 $j$ 次询问（$1 \le j \le n$）构造一个长度为 $n$ 的字符串 $s$，其中只有第 $j$ 位为 1，其余全为 0。 交互器返回的字符串 $t$ 中，如果 $t[i] = 1$，说明 $s[P[i]] = 1$，由于 $s$ 只有第 $j$ 位为 1，因此 $P[i]$ 必然等于 $j$。

通过 $n$ 次这样的查询，我们可以还原出所有的 $P[i]$。这可以获得 $30\%$ 的分数。

100%

对于 $n \le 10^5$ 的数据，这启发我们利用二进制拆分的思想来进行查询，因为 $n < 2^{17}$。 任何一个从 $1$ 到 $n$ 的整数都可以用一个不超过 $17$ 位的二进制数唯一表示。

我们可以发起恰好 $17$ 次查询。对于第 $k$ 次查询（$0 \le k \le 16$），我们构造字符串 $s$ 使得 $s[j]$ 等于 $j$ 在二进制下的第 $k$ 位（即如果 $j$ 的第 $k$ 位是 $1$ 则 $s[j] = 1$，否则为 $0$）。

根据交互规则，$t[i] = s[P[i]]$，这意味着返回的 $t[i]$ 恰好等于 $P[i]$ 在二进制下的第 $k$ 位。

在 $17$ 次查询结束后，对于每一个位置 $i$（$1 \le i \le n$），我们都从交互器那里获取到了 $P[i]$ 的第 $0 \sim 16$ 位的二进制表示。我们只需要将这些位重新组合成整数，即可求出真实的 $P[i]$，进而还原出完整的排列 $P$。

单次询问构造和复原排列的时间复杂度为 $O(n \log n)$。

T6

30%

对于 $n \le 20$ 且 $k \le 2$ 的数据，树的规模很小，可以直接使用深度优先搜索遍历所有 $k^n$ 种染色方案，然后对每种染色方案再利用 DFS 寻找单色连通块，统计点数为奇数的单色连通块数量。时间复杂度 $O(n \cdot k^n)$，可以获得 $30\%$ 的分数。

100%

根据求和的性质，总的奇数大小连通块数量可以转化为：枚举树上所有可能的连通子图 $C$，如果 $|C|$ 为奇数，则计算有多少种染色方案使得 $C$ 恰好成为一个极大的单色连通块，并将这些方案数累加。

对于一个大小为 $c$，且有 $m$ 个邻居节点（与 $C$ 中节点有边相连但不在 $C$ 中的节点）的连通子图 $C$，它成为极大单色连通块的条件是：

1. $C$ 内部的所有节点颜色必须相同（共 $k$ 种选择）。
2. $C$ 的所有 $m$ 个邻居节点的颜色必须与 $C$ 的颜色不同（每个邻居有 $k-1$ 种选择）。
3. 其余 $n - c - m$ 个节点可以任意染色（每个有 $k$ 种选择）。

有了上面的分析，现在的问题就变成了如何统计每个连通块的出现次数。

在一棵无根树中，如果我们任意指定一个节点（例如 $1$ 号节点）作为树的根，那么任何一个单色连通块必定存在唯一一个深度最浅的节点，我们称之为该连通块的“顶部节点”。

因此，原问题等价于：枚举每个节点 $i$，计算有多少种染色方案使得节点 $i$ 恰好是某个奇数大小的极大单色连通块的顶部节点，然后将结果累加。

节点 $i$ 能够成为它所在单色连通块的顶部节点，当且仅当：

• 如果 $i = 1$（即根节点），它没有父节点，必然是顶部节点。
• 如果 $i > 1$，为了保证它是连通块的最顶端，它的颜色必须与父节点的颜色不同。

可以考虑使用树形 DP 来解决这个问题。 定义 $dp[u][0]$ 和 $dp[u][1]$ 表示：假设节点 $u$ 的颜色已确定，在其子树中进行染色，使得 $u$ 所在的单色连通块大小为偶数 / 奇数的方案数。 （注意：这里仅指代 $u$ 所在连通块在其子树内的部分，且 DP 状态的方案数已经包含了子树中那些颜色断开的节点的任意合法染色方案）。 对于每个节点 $u$，在还未合并任何子节点时，连通块仅包含 $u$ 自己，大小为 $1$。因此初始状态为 $dp[u][0] = 0$，$dp[u][1] = 1$。 假设我们正在计算 $u$，并准备将它的一个子节点 $v$ 及其子树合并进来。 子节点 $v$ 的颜色有以下两种情况：

1. $v$ 的颜色与 $u$ 相同： 此时 $v$ 必定只有 $1$ 种颜色选择。连通块 $u$ 与连通块 $v$ 合并，大小相加。
   • 产生偶数连通块的方案数（偶+偶 或 奇+奇）：$dp[u][0] \times dp[v][0] + dp[u][1] \times dp[v][1]$。
   • 产生奇数连通块的方案数（偶+奇 或 奇+偶）：$dp[u][1] \times dp[v][0] + dp[u][0] \times dp[v][1]$。
2. $v$ 的颜色与 $u$ 不同： 此时 $v$ 可以选择剩下的 $k - 1$ 种颜色。一旦 $v$ 的颜色确定，它所在的子树中剩下的 $sz[v] - 1$ 个节点可以任意染色，共有 $k^{sz[v] - 1}$ 种方案。 所以让 $v$ 与 $u$ 颜色断开的合法染色方案数共有 $val = (k - 1) \times k^{sz[v] - 1}$。 因为颜色断开，所以 $u$ 所在连通块的大小和奇偶性均不变。
   • 产生偶数连通块的方案数增加：$dp[u][0] \times val$。
   • 产生奇数连通块的方案数增加：$dp[u][1] \times val$。

综上，合并子树 $v$ 后的新状态转移方程为：

$$ndp[u][0] = dp[u][0] \times (dp[v][0] + val) + dp[u][1] \times dp[v][1]$$$$ndp[u][1] = dp[u][1] \times (dp[v][0] + val) + dp[u][0] \times dp[v][1]$$

当整棵树的 dp 数组计算完毕后，我们遍历每个节点 $i$，统计其作为顶部节点的奇数连通块对答案的贡献：

1. 对于根节点 $i = 1$： $1$ 号节点有 $k$ 种颜色可选。其子树就是整棵树，贡献即为 $k \times dp[1][1]$。
2. 对于非根节点 $i > 1$： $i$ 号节点有 $k$ 种颜色可选。$i$ 的子树外共有 $n - sz[i]$ 个节点，其中 $i$ 的父亲有 $k - 1$ 种颜色可选（不能和 $i$ 一样），其余的点有 $k$ 种颜色可选。所以节点 $i$ 的贡献为：$k^{n - sz[i]} \times (k - 1) \times dp[i][1]$。

通过预处理 $k$ 的次幂可以将时间复杂度优化为 $O(n)$ ，空间复杂度为 $O(n)$。