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

T1

100%

可以使用一个布尔类型的数组 $vis$（大小为 $n+1$，初始全部为 false）来记录数字的出现情况。

遍历输入的 $n-x$ 个数字，对于读入的每个数字 $v$，将 $vis[v]$ 标记为 true。

然后从 $1$ 到 $n$ 枚举所有的数字 $i$。如果此时 $vis[i]$ 仍然为 false，说明 $i$ 就是一个被删除的数字，我们直接将其输出。由于是从小到大枚举的，被删除的数字天然也会按照从小到大的顺序被输出。

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

T2

100%

因为题目保证这 $n$ 个字符串的第一个字符互不相同，这意味着我们只需要通过观察剩余目标长字符串 $S$ 的首个字符，就能唯一确定接下来应该拼接的是哪一个字符串。

接着，维护一个指针 $p$ 表示当前在目标字符串 $S$ 中的匹配位置，初始时 $p=0$。 在 $p < |S|$ 的循环中：

• 根据当前字符 $S[p]$，直接得出匹配的字符串编号 $i$。
• 输出编号 $i$。
• 将指针 $p$ 向后移动第 $i$ 个字符串的长度。

重复上述过程直到整个 $S$ 匹配完毕。

时间复杂度 $O(|S|)$，空间复杂度 $O(\sum |c_i|)$。

T3

50%

对于 $50\%$ 的数据（$n \le 2000$），我们可以枚举所有可能满足条件的 $x$ 值。

对于某一个具体的位置 $i$，如果要满足条件 $\min(D, a_i + x) \ge b_i$，必须同时满足两个前提：

1. $D \ge b_i$。如果连 $D$ 都比 $b_i$ 小，那么无论 $x$ 取多大，条件的左边最大也只能是 $D$，永远无法满足 $\ge b_i$。
2. $a_i + x \ge b_i$，这意味着需要的最小非负整数 $x$ 为 $\max(0, b_i - a_i)$。

因此，对于那些 $D \ge b_i$ 的位置，我们可以收集其对应的 $x = \max(0, b_i - a_i)$ 作为 $x$ 的候选值。然后对于每一个候选值 $x$，遍历一遍数组检查有多少个位置满足 $\min(D, a_i + x) \ge b_i$。如果满足的位置数 $\ge k$，则这个 $x$ 是合法的。在所有合法的 $x$ 中取最小值即可。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。

100%

基于上述分析，对于每一个位置 $i$，它能满足要求的充要条件是：$D \ge b_i$ 且选取的 $x \ge \max(0, b_i - a_i)$。

于是，我们只需保留满足 $D \ge b_i$ 的所有位置，并对每个位置计算出它所需的最小 $x$ 值 $req_i = \max(0, b_i - a_i)$。 将所有计算出的 $req_i$ 放入一个数组中。如果这个数组的大小不足 $k$ 个，说明无论 $x$ 取多大，都不可能凑齐 $k$ 个满足条件的位置，此时直接输出 -1。

若数组大小 $\ge k$，我们将这个 $req_i$ 数组按升序排序。为了让至少 $k$ 个位置同时满足条件，我们只需要取排序后第 $k$ 小的 $req_i$（即数组下标为 $k-1$ 的元素）。这就是我们要找的最小的非负整数 $x$。

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

T4

40%

对于 $40\%$ 的数据，$n_a, n_b, n_c \le 200$。

我们可以直接使用三重循环，枚举所有可能的三元组 $(i, j, k)$。对于枚举到的每一组，判断其是否满足条件 $a_i \le b_j \le c_k$ 并且 $c_k - a_i \le d$。如果满足，则对答案计数加 $1$。

时间复杂度 $O(n_a n_b n_c)$，空间复杂度 $O(n_a + n_b + n_c)$。

100%

首先将数组 $a, b, c$ 从小到大进行排序。

考虑枚举 $c_k$。对于一个固定的 $c_k$，我们需要找出满足 $a_i \le b_j \le c_k$ 且 $c_k - a_i \le d$（即 $a_i \ge c_k - d$）的二元组 $(i, j)$ 的数量。

综合这两个条件，可得 $c_k - d \le a_i \le b_j \le c_k$。

既然 $a_i \le b_j$ 且 $a_i \ge c_k - d$，那么合法的 $b_j$ 必然满足 $c_k - d \le b_j \le c_k$。

因为数组 $b$ 已经排序，我们可以使用二分查找快速找出所有满足 $c_k - d \le b_j \le c_k$ 的 $b_j$ 所在的下标区间，记为 $[L, R]$。

对于该区间内的某一个 $b_j$，合法的 $a_i$ 需要满足 $c_k - d \le a_i \le b_j$。满足该条件的 $a_i$ 的数量等于：

（满足 $a_i \le b_j$ 的数量）$-$（满足 $a_i < c_k - d$ 的数量）。

我们发现：

1. “满足 $a_i < c_k - d$ 的数量”只与 $c_k$ 有关，与 $j$ 无关。我们可以再次使用二分查找（std::lower_bound）在数组 $a$ 中求出这个数量，记为 $cnt$。
2. “满足 $a_i \le b_j$ 的数量”只与 $b_j$ 有关。我们可以预处理出一个数组，表示数组 $a$ 中小于等于 $b_j$ 的元素个数。为了快速计算区间和，我们再对这个数量求前缀和，记为 $preb[j]$。即 $preb[j]$ 表示前 $j$ 个 $b$ 数组元素所对应的合法 $a$ 元素个数的总和。

那么对于固定的 $c_k$，下标在 $[L, R]$ 内的 $b_j$ 对应的合法二元组 $(i, j)$ 的总数为： $(preb[R] - preb[L - 1]) - (R - L + 1) \times cnt$

我们将每个 $c_k$ 对应的上述结果累加起来，即为最终答案。

时间复杂度 $O(N \log N)$，其中 $N = \max(n_a, n_b, n_c)$。空间复杂度 $O(N)$。

T5

100%

考虑建图，将点 $i$ 向 $X_i$ 连一条权值为 $C_i$ 的有向边，可以发现它是一个它是一个的内向基环树森林(即每个联通部分只有一个环)。

“分配到 A 和 B” 就相当于对图进行黑白染色，要求每条边连接的两个点的颜色不同。

“建立备份” 可以理解成将 $i \to X_i$ 这条边删除，代价为 $C_i$。

可以发现，对于每个联通部分，如果这个联通部分的环的大小是偶数，那么可以直接染色而不删除任何边。如果这个联通部分的环的大小是奇数，那么在环上的点无论怎么染色，都是会有一条边两端颜色相同。所以我们可以将一条环上最小权值的边，将其删除即可。

实现上，我们只需要找到每个联通部分的环（可以利用拓扑排序或 bfs ）， 然后判断它的环的大小的奇偶性，如果是偶数就跳过；如果是奇数就跑一遍环的边即可。

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

T6

100%

根据题目条件，数组的第 $i$ 个元素 $a_i$ 表示值大于等于 $i$ 的元素数量，这等价于定义了一个 $b$ 数组。条件 $a_i = b_i$ 意味着，如果我们把数组 $a$ 的各个元素作为每一行的长度画出图像（由方格组成的图形，第 $i$ 行有 $a_i$ 个方格），这个图形关于主对角线是完全对称的。因此，满足条件的平衡数组与完全对称的整数拆分一一对应。我们需要求所有总和为 $N$ 的对称整数拆分中，不同数字个数（即平衡值）的总和。

为了高效计算，我们可以挖掘对称图形的结构性质。对于一个总和为 $N$ 的对称拆分，我们在其图像的左上角框出一个最大的正方形 (即最大的满足 $a_i \ge i$ 的最大的 $i$)。

假设该最大正方形的边长为 $k$。由于图形是对称的，正方形右侧的图像（记为 $\lambda$）和正方形下方的图像（记为 $\lambda'$）形状完全沿对角线对称，即 $\lambda'$ 是 $\lambda$ 的转置。

这说明除去中间的正方形后，剩余部分的元素个数为 $N - k^2$，且一半在右侧，一半在下方。因此必定有 $N - k^2$ 为偶数。

令 $rem = \frac{N - k^2}{2}$。由于右侧的 $\lambda$ 高度不能超过 $k$（否则正方形的边长就可以更大了），因此 $\lambda$ 是一个总和为 $rem$ 且最多只有 $k$ 行的拆分。将 $\lambda$ 转置后，等价于一个总和为 $rem$ 且最大元素 $\le k$ 的拆分 $\mu$。

接下来考虑该平衡数组的平衡值（互不相同的元素个数）：

对称拆分的各个部分大小，等于前 $k$ 行的长度以及下方 $\lambda'$ 的各行长度：

1. 前 $k$ 行的长度为 $k + \lambda_i$ （其中 $\lambda_i \ge 0$）。这些数字都 $\ge k$。这里产生的不同数字个数，等于 $\lambda$ 中严格大于 0 的不同数字个数，假设为 $d$。

2. 第 $k+1$ 行及以后的长度为 $\lambda'_j$。因为 $\lambda$ 最多有 $k$ 行，所以 $\lambda'_j \le k$。根据转置的性质，$\lambda'$ 中不同数字的个数，恰好也等于 $d$。

3. 数字 $k$ 本身是否出现：综合 1 和 2，如果 $\lambda_k = 0$，则前 $k$ 行中第 $k$ 行长度恰好为 $k$；如果 $\lambda_k > 0$，则下方的最大元素等于 $k$。仔细推导可知，数字 $k$ 必定会在拆分中出现。其中，大于 $k$ 的不同数字有 $d$ 个，小于 $k$ 的不同数字有：若最大元素等于 $k$ 则为 $d-1$ 个，若最大元素小于 $k$ 则为 $d$ 个。

因此，这个对称拆分的平衡值总和固定为：

$$d + (d -[\mu \text{ 的最大元素} = k]) + 1 = 2d +[\mu \text{ 的最大元素} \le k-1]$$

其中 $d$ 等于拆分 $\mu$ 中不同数字的个数。

考虑动态规划：

• 定义 $dp1[i][j]$ 表示将 $j$ 拆分成最大元素不超过 $i$ 的方案数。
• 定义 $dp2[i][j]$ 表示将 $j$ 拆分成最大元素不超过 $i$ 的所有方案中，不同数字个数的总和。

状态转移方程如下：

• $dp1[i][j] = (dp1[i-1][j] + dp1[i][j-i])$ （方案数 = 不包含 $i$ 的方案数 + 至少包含一个 $i$ 的方案数）
• $dp2[i][j] = (dp2[i-1][j] + dp2[i][j-i] + dp1[i-1][j-i])$ （不同数字个数总和 = 不包含 $i$ 的转移 + 包含 $i$ 的转移。若之前不包含 $i$，现在加入了第一个 $i$，则新产生了一个不同的数字，因此要额外加上从前 $i-1$ 转移过来的基础方案数 $dp1[i-1][j-i]$）

预处理出 $dp1$ 和 $dp2$ 数组后，枚举所有满足 $k^2 \le N$ 且 $N - k^2$ 为偶数的最大正方形边长 $k$：

令 $rem = \frac{N - k^2}{2}$，该边长 $k$ 对应的所有对称拆分贡献的平衡值之和即为：

$$dp1[k-1][rem] + 2 \times dp2[k][rem]$$

将所有合法 $k$ 对应的 $res$ 累加即可。

预处理时背包容量最大为 $N/2$，最大元素 $m = \lfloor\sqrt{N}\rfloor$。

时间复杂度 $O(N \sqrt{N})$，空间复杂度 $O(N \sqrt{N})$。