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

T1

100%

本题要求将字符串中的数字重复 $3$ 次，字母重复 $2$ 次。

直接遍历字符串 $s$，判断当前字符的类型：

• 如果是数字字符（'0' $\sim$ '9'），循环输出 $3$ 次；

• 如果是字母字符（'a' $\sim$ 'z' 或 'A' $\sim$ 'Z'），循环输出 $2$ 次。

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

T2

100%

首先考虑数值重复的问题：

• 当 $|s|=1$ 时，无论 $s$ 是什么字符，在所有合法的进制下，它代表的数值都是它本身（例如字符 1 在各进制下数值均为 $1$）。根据题目要求“数值相等只能算作一种”，因此当 $|s|=1$ 时，答案固定为 $1$。
• 当 $|s|>1$ 时，由于题目保证没有前导零，显然，随着 $base$ 的增大（$2 \to 8 \to 10 \to 16$），算出的数值是严格单调递增的。因此，只要进制合法，算出的数值一定互不相同。

所以我们就把问题变成了：统计字符串 $s$ 能符合多少种进制的定义。

我们可以通过找到字符串 $s$ 中最大的字符 $mx$ 来快速判断：

1. 十六进制：题目保证字符只包含 0-9 和 A-F，且至少在一种进制下合法。因此 $s$ 在十六进制下一定合法。
2. 十进制：要求 $s$ 中不包含字母。即 $mx \le \text{'9'}$。
3. 八进制：要求 $s$ 中只包含 0-7。即 $mx < \text{'8'}$。
4. 二进制：要求 $s$ 中只包含 0-1。即 $mx < \text{'2'}$。

统计答案即可。

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

T3

100%

本题要求最小化将 $s$ 变为 $t$ 的总代价。由于每一位的变换互不影响，我们可以单独计算每一对字符 $(s_i, t_i)$ 的最小转换代价，最后累加。

由于数字字符与对应的小写字母（0 $\leftrightarrow$ a, ..., 9 $\leftrightarrow$ j）之间转换代价为 $0$。因此我们可以忽略它们之间的区别。为了方便计算，我们可以优先将所有的数字字符都转化为对应的小写字母。

• 若字符是数字，则转化为 a $\sim$ j。
• 若字符原本就是字母，则保持不变。

经过这一步，问题就转化为了：在 a $\sim$ z 的字符集上，给定两个字符 $x$ 和 $y$，求最短距离。

接下来我们考虑字符之间的连接边（代价为 $1$ 的操作）。 如果没有数字，只有字母，那么除了相邻字母的连边外，只有一条特殊的“字母循环边”：z $\leftrightarrow$ a。

但是，因为引入了数字，我们还需要考虑数字原本的循环性质：

• 原本 9 和 0 是相邻的（代价 $1$）。
• 映射到字母后，这意味着 j 和 a 之间也多出了一条“数字循环边”（代价 $1$）。

3. 计算最短路径 综上所述，归一化后的字符 $x$ 到 $y$ 有以下几种路径选择，取最小值即可：

1. 直接移动：不经过任何循环边界。代价为：$|x - y|$。

2. 利用“数字循环边” (a $\leftrightarrow$ j)：

   • 路径：$x \to \dots \to \text{'a'} \to \text{'j'} \to \dots \to y$。
   • 代价：$|x - \text{'a'} | + 1 + | \text{'j'} - y|$（反向同理）。

3. 利用“字母循环边” (a $\leftrightarrow$ z)：

   • 路径：$x \to \dots \to \text{'a'} \to \text{'z'} \to \dots \to y$。

   • 代价：$|x - \text{'a'}| + 1 + |\text{'z'} - y|$（反向同理）。

4. 同时利用两条边：

   • 即经过 j $\leftrightarrow$ a $\leftrightarrow$ z 的路径。
   • 代价：$|x - \text{'j'}| + 1 + 1 + |\text{'z'} - y|$（反向同理）。

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

T4

100%

题目要求我们需要构造一棵 $n$ 个节点、直径为 $x$ 的树，并使得其度数序列 $d_1, d_2, \dots, d_n$ 的字典序最小。

所谓“度数序列字典序最小”，意味着我们需要让序列前面的元素尽可能小。 由于我们可以任意安排节点的编号（$1$ 到 $n$），因此只要我们确定了这棵树由哪些度数构成，为了让序列字典序最小，我们最优的策略一定是将这些度数从小到大排序，然后依次分配给节点 $1, 2, \dots, n$。 问题就转换成构造一个合法的度数集合，使得其中包含尽可能多的 $1$，其次是尽可能多的 $2$，以此类推。

为了满足直径为 $x$ 的限制，树中必须包含一条长度为 $x$（包含 $x+1$ 个节点）的链，我们称之为“骨架”。

接着我们考虑将剩下的节点全部接到不是直径两端的某个点上，这样其他的点的度数就是 $1$。不难证明此时是最优的。

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

T5

100%

让所有兔子在坐标 $P$ 集合所需的时间 $T$，取决于初始（或使用魔法后）所有兔子中，位置最左的兔子 $L$ 和位置最右的兔子 $R$ 之间的距离。如果最左和最右的坐标确定，则所有人集合到中间的最短时间为 $\lceil (R - L) / 2 \rceil$。

题目保证坐标和 $x$ 均为偶数，因此计算时直接用 $(R - L) / 2$ 即可。

根据上述观察可以发现，我们只需要让左边的往右走，右边的往左走，因此不用魔法的兔子一定构成一个区间。

我们可以枚举不用魔法的兔子的区间 $[l,r]$（区间长度固定为 $n-k$），然后计算出最左边的兔子坐标（ $\min(a[l], a[1] + x)$） 和最右边的兔子坐标 （$\max(a[r], a[n] - x)$）即可。

注意特判 $k = n$ 。

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

T6

100%

题目要求计算消除节点 $u$ 的电荷（即令 $a_u = 0$）后，树的“健康程度” $\sum |S_i|$。 首先我们需要预处理出初始状态下每个节点的子树和 $S_i$。 当我们将 $a_u$ 变为 $0$ 时，会对树产生什么影响？

• 对于 $u$ 的所有祖先节点（包括 $u$ 自己），其子树和会减小 $a_u$，即变为 $S_v - a_u$。
• 对于其他节点（非 $u$ 的祖先），其子树和保持不变。

记 $Path(u)$ 为从根节点到 $u$ 的路径上的节点集合（即 $u$ 及其所有祖先）。 消除 $u$ 后的总健康程度可以表示为：

$$Ans_u = \sum |S_i| - \sum_{v \in Path(u)} |S_v| + \sum_{v \in Path(u)} |S_v - a_u|$$

当我们从根节点递归走到节点 $u$ 时，当前的递归栈正好对应了 $Path(u)$。因此，我们可以动态维护当前路径上的 $S_v$ 集合。

我们需要计算的是 $\sum_{v \in Path(u)} |S_v - a_u|$。可以将绝对值拆解：

• 对于 $S_v < a_u$ 的部分：$|S_v - a_u| = a_u - S_v$。
• 对于 $S_v \ge a_u$ 的部分：$|S_v - a_u| = S_v - a_u$。

为了快速计算，我们可以使用两个树状数组 分别维护 $S_v$ 的个数和数值 $S_v$ 的和

由于 $S_v$ 和 $a_u$ 的值域很大且可能有负数，需要进行离散化处理。

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

T7

100%

FHQ Treap 模板题。

为了处理操作 1 中一次性插入 $x$ 个 $v$ 的情况，我们将这 $x$ 个相同的元素看作一个节点。每个 Treap 节点维护以下信息：

1. val：当前节点存储的单个元素的数值。
2. len：当前节点代表了多少个重复的元素（即块的长度）。
3. size：以当前节点为根的子树中包含的实际元素总数。
4. sum：以当前节点为根的子树中所有元素的数值总和。
5. lazy：区间加法的懒标记。

由于每次操作 $1$ 至多插入 $1$ 个节点，故时间复杂度为 $O((n + q) \log (n + q))$。