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

T1

100%

题目要求判断字符串 $s$ 中是否同时包含子串 lzm 和 tom。

假设我们要找 $s$ 中是否有某个串，一个方法就是枚举被查找的字符串的开头，然后一个一个检查字符，看原串是否和被查找串相同。

时间复杂度 $O(|s|)$ 。

T2

100%

根据题意我们需要验证以下四个条件：

长度必须恰好为 $8$ 。
前两个字符必须在 A 到 G 之间。
第 3 到第 7 个字符必须是 0 到 9 之间的数字。
第 8 个字符必须是 0 到 9 之间的数字，或者是大写字母 X。

只需遍历对应下标的字符进行 ASCII 码范围判定即可，若所有条件全部通过则合法。

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

T3

100%

题目要求将环切分成两半，每部分 $n$ 个元素。令所有 $2n$ 个元素的总和为 $S = \sum_{i=1}^{2n} a_i$ 。

无论我们怎么切分，如果其中一部分的元素和为 $x$ ，那么另一部分的元素和必然为 $S - x$ 。题目要求最大化 $x \oplus (S - x)$ 。

由于是环上的连续 $n$ 个元素，我们可以采用破环成链的技巧：构建一个长度为 $4n$ 的数组，将原数组重复两次。在这个 $4n$ 的数组上做一次前缀和，这样我们可以枚举每个长度为 $n$ 的数组，我们都可以在 $O(1)$ 时间内算出他们的和，进而更新答案。

对于每一个长度为 $n$ 的窗口，设其和为 $x$ ，更新答案 $ans = \max(ans, x \oplus (S - x))$ 。

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

T4

100%

先不考虑交换操作（即类型 $1$ 操作），观察答案会是什么形式。对于一对匹配 $(a_i, b_i)$ ，将 $a_i$ 变为 $b_i$ 的代价就是在模 $m$ 意义下从 $a_i$ 顺时针增加到 $b_i$ 的距离，即 $(b_i - a_i) \bmod m$ 。

具体来说：

当 $a_i \le b_i$ 时，代价为 $b_i - a_i$ 。
当 $a_i > b_i$ 时，由于跨越了模数的边界，代价为 $b_i - a_i + m$ 。

假设我们通过类型 1 操作（代价为 $0$ ，可以任意重排序列 $a$ ），将 $a$ 重排为 $a'$ ，使得 $a'_i$ 与 $b_i$ 一一对应匹配。那么将整个序列转换完毕的总代价为：

$$\sum_{i = 1}^{n} ((b_i - a'_i) \bmod m) = \sum_{i = 1}^{n} b_i - \sum_{i = 1}^{n} a'_i + m \times k$$

其中 $k$ 为满足 $a'_i > b_i$ 的匹配对数。

由于无论如何重排， $\sum_{i = 1}^{n} b_i$ 和 $\sum_{i = 1}^{n} a'_i$ （即序列原有的元素和 $\sum_{i = 1}^{n} a_i$ ）都是定值，所以我们唯一能优化的部分就是通过交换，让 $a'_i > b_i$ 的对数 $k$ 尽可能小。

反过来说，让 $k$ 尽可能小，等价于让满足 $a'_i \le b_i$ 的匹配对数尽可能多。这就转换成了一个经典的贪心匹配问题：给定两个数组，求最多能组成多少对 $(a'_i, b_i)$ 满足 $a'_i \le b_i$ 。

这个问题的解法有很多（二分答案，二分查找，multiset，双指针等），但大体思路都是一样的：为了让成功匹配的对数尽可能多，我们应该把 $a$ 和 $b$ 中的较小值优先进行匹配。

对于任意一个 $a_i$ ，如果我们要给它找一个匹配的 $b_j$ （满足 $b_j \ge a_i$ ），我们应该在所有满足条件的 $b$ 中，挑选最小的那一个。因为较大的 $b$ 具有更高的“包容性”，留着它们去匹配后面更大的 $a$ ，显然能得到更优的结果。

以下是二分查找的做法：

将 $a$ 和 $b$ 数组分别从小到大进行排序。
设一个变量 $p = 0$ ，用来记录上一次在 $b$ 中匹配成功的位置下标。
从左到右遍历排序后的序列 $a$ $a$ 中的每个元素 $a_i$ $a_{i}$ ：
- 我们需要在 $b$ 数组的 $[p + 1, n]$ 这个区间内，二分查找第一个大于等于 $a_i$ 的元素。
- 如果找到了满足条件的 $b_j$ （且 $j \ge p$ ），说明 $a_i$ 匹配成功。我们将成功匹配的对数加一，并更新 $p = j + 1$ ，表示下一次查找要从 $j$ 的下一个位置开始。
- 如果找不到，说明剩下的 $b$ 中已经没有大于等于当前 $a_i$ 的元素了。由于 $a$ 序列递增，后面的 $a$ 显然也不可能再找到匹配项，此时可以直接退出循环结束匹配。
同样，总个数 $n$ 减去成功匹配的对数，即为最小的 $k$ 。

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

T5

100%

我们先单独分析一维的情况，以序列 $a$ 和变量 $x$ 为例。若使得 $a_i \le x < a_j$ 成立，显然 $x$ 必须落在 $[a_1, a_n)$ 的范围内。假设 $x$ 落在了某一段区间 $[a_p, a_{p+1})$ 中（其中 $1 \le p < n$ ）。因为序列 $a$ 是严格单调递增的，满足条件的 $i$ 必然是 $1, 2, \dots, p$ （共 $p$ 个），满足条件的 $j$ 必然是 $p+1, \dots, n$ （共 $n-p$ 个）。所以对于任意 $x \in [a_p, a_{p+1})$ ，它的区间出现个数实际上是一个固定值： $V_p = p \times (n - p)$ 。而这样的 $x$ 共有 $W_p = a_{p+1} - a_p$ 个。

同理，对于序列 $b$ ，若 $y \in [b_q, b_{q+1})$ ，它在第二维上的权值贡献为 $U_q = q \times (m - q)$ ，对应的 $y$ 有 $L_q = b_{q+1} - b_q$ 个。二元组 $(x, y)$ 的总权值即为 $V_p \times U_q$ 。题目要求 $V_p \times U_q \ge v$ 。

我们把所有的 $(V_p, W_p)$ 提取为一个大小为 $n-1$ 的数组，把所有的 $(U_q, L_q)$ 提取为大小为 $m-1$ 的数组。将第二组数据按照 $U_q$ 从小到大排序，并对 $L_q$ 预处理出后缀和。接着，我们遍历第一组数据的每一个 $V_p$ ，在第二组数据中通过二分查找找到满足 $U_q \ge \lceil v / V_p \rceil$ 的最小下标，利用后缀和即可 $O(1)$ 计算所有合法 $y$ 的个数 $L_q$ 的和，乘以当前的 $W_p$ 即为当前段对答案的贡献。

时间复杂度 $O(n \log n + m \log m)$ 。

T6

100%

通常我们思考括号序列是从左到右，或者从 $1$ 级往 $m$ 级（从内向外）嵌套。但这道题由于存在严格的包含关系限制，我们可以倒着考虑：从最外层、最高级别的 $m$ 级括号开始，一层层往里面“塞”低级别的括号。

仔细观察题目中“可爱”序列的限制条件：

$v$ 级括号内部必须包含至少一个 $v-1$ 级括号（ $v > 1$ ）。
$v$ 级括号内部不能包含 $v$ 级或更高级别的括号（即同级或高级不能嵌套）。
$1$ 级括号内部必须为空。

同时，根据题目给定的数量规律可以发现：相邻两级之间，低级括号永远只比高级括号多出恰好 $1$ 对。具体的，级别为 $v$ 的括号恰好有 $n-v+1$ 对。

假设我们现在已经合法地排好了所有级别 $\ge v$ 的括号，接下来我们考虑如何把 $v-1$ 级的括号加入到序列中。

设当前序列中级别 $\ge v$ 的括号总对数为 $P_v$ 。

一个包含 $P_v$ 对（即 $2 P_v$ 个字符）的合法括号序列，自然会形成 $2 P_v + 1$ 个“空隙”（包含最左边、最右边，以及每两个相邻字符中间）。

现在，我们要把所有的 $v-1$ 级括号插进这 $2 P_v + 1$ 个空隙中。当前序列中共有 $N_v = n-v+1$ 对 $v$ 级括号，而我们需要放入 $N_{v-1} = n-v+2$ 对 $v-1$ 级括号。

因为“每一个 $v$ 级括号内部必须包含至少一个 $v - 1$ 级括号”，所以对于当前序列中的那 $N_v$ 个 $v$ 级括号，它们的最直接的内部空隙（即紧挨着左括号和右括号之间的位置）是必须放东西的。这就强制消耗掉了 $N_v$ 对 $v-1$ 级括号（每个 $v$ 级括号内部放 $1$ 对）。

填完这些必须填的位置后，我们手中恰好只剩下 $1$ 对 $v-1$ 级括号。而这剩下的 $1$ 对 $v-1$ 级括号，可以直接放在当前序列的 $2 P_v + 1$ 个空隙中的任意一个位置。

如果把它放在普通的空隙，它将单独成为一对。
如果把它放在刚刚已经填过强制 $v-1$ 级括号的空隙里，意味着这个 $v$ 级括号内部会有 $2$ 对并列的 $v-1$ 级括号。我们可以默认这两个并列的 $v-1$ 级括号是等价的。例如我们钦定第一个括号是第一次强制填的，第二个括号是剩下的来填的。

直接递推这个过程即可。

时间复杂度为 $O(\sum m )$ 。

T7

100%

题目可以转化为经典的最小割模型。

每个格子最终的状态要么是红色（获得 $a_{i,j}$ ），要么是白色（获得 $b_{i,j}$ ），要么是粉色（获得 $0$ ）。

初始假设我们拿到了所有的美观值 $\sum (a_{i,j} + b_{i,j})$ ，然后通过“割”去减掉无法同时获得的代价。

我们为每个格子定义两个决策：是否放入集合 $R$ （红色），是否放入集合 $W$ （白色）。

构造一个二分图：

左侧点集 $R$ ：代表每个格子选红色，源点 $S$ 向每个 $R_{i,j}$ 连一条容量为 $a_{i,j}$ 的边。
右侧点集 $W$ ：代表每个格子选白色，每个 $W_{i,j}$ 向汇点 $T$ 连一条容量为 $b_{i,j}$ 的边。
冲突连边：
- 同一个格子不能既是红色又是白色：连边 $R_{i,j} \to W_{i,j}$ ，容量 $\infty$ 。
- 相邻的格子约束（红色周围不能有白色）：如果 $(i,j)$ 是红色，那么它相邻的 $(x,y)$ 绝对不能是白色。因此连边 $R_{i,j} \to W_{x,y}$ ，容量 $\infty$ 。

在上述建图后，跑一遍 $S$ 到 $T$ 的最大流。最大流即为必须舍弃的最小代价（最小割）。最终答案 = $\sum_{i,j} (a_{i,j} + b_{i,j}) - \text{最大流}$ 。