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

T1

100%

只需要输出任意在 $18$ 到 $120$ 以内的整数即可。

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

T2

100%

用一个变量 $pos$ 表示熊大当前的跑道编号，初始值为 $x$ 。依次遍历操作字符串 $s$ 的每个字符：

如果是 L，则有 $pos = \max(0, pos - 1)$ 。
如果是 R，则有 $pos = \min(m, pos + 1)$ 。

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

T3

100%

考虑展开“合理值”的公式：

$$\begin{aligned} & (x_1 - l)^2 + (x_2 - l)^2 + (x_3 - l)^2 +\cdots (x_m -l)^2 \\ =& (x_1^2 - 2x_1l + l^2) + (x_2^2 -2x_2l + l^2) + (x_3^2 -2x_3l + l^2) + \cdots + (x_m^2 -2x_ml + l^2) \\ = & (x_1^2 + x_2 ^2 + \cdots + x_m^2) - 2l(x_1 + x_2 + x_3 + \cdots + x_m) + m l^2 \end{aligned}$$

这说明，只要我们知道区间 $[l, r]$ 内成绩的个数（ $m$ ）、总和（ $x_1 + x_2 \cdots + x_m$ ）以及平方和 $(x_1^2 + x_2^2 + x_3^2 \cdots x_m ^2 )$ ，就可以在 $O(1)$ 的时间内算出答案。

所以可以将原数组先从小到大排序，后根据排序后的数组利用前缀和计算出总和和平方和。每次询问可以利用二分查找来找到最小的 $\ge l$ 的下标和最大的 $\le r$ 的下标，再利用上面的公式进行计算。

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

T4

50%

考虑动态规划。

设 $dp[i][u][v]$ 表示：已经输入了前 $i$ 个字符，当前左手食指在键盘位置 $u$ （在 $a_u$ ），右手食指在键盘位置 $v$ （在 $a_v$ ）时的最小移动距离和。

为了输入当前字符 $s_i$ （假设它在 $a$ 中的位置 $now$ ），我们只有两种的操作：

左手去按：左手从 $u$ 移动到 $now$ ，右手停留在 $v$ 不动。 $dp[i][now][v] = \min(dp[i][now][v], dp[i-1][u][v] + \min(|now- u|,26 - |now- u|))$
右手去按：右手从 $v$ 移动到 $now$ ，左手停留在 $u$ 不动。 $dp[i][u][now] = \min(dp[i][u][now], dp[i-1][u][v] + \min(|now- v|,26 - |now- v|))$

初始状态为 $dp[0][0][0] = 0$ 。答案为 $dp[n][i][j]$ 的最小值。

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

100%

与 $50\%$ 的做法类似，但是我们可以发现观察到无论怎么移动，在输入完第 $i$ 个字符时，必然有一根食指停留在字符 $s_i$ 的位置。因此，我们只需要记录“另一根食指的位置”即可构成完整的状态。

设 $dp[i][j]$ 表示已经输入了前 $i$ 个字符，且当前一根食指在 $s_i$ 字符所在的位置上，另一根食指在 $a$ 的位置为 $j$ 时的最小移动距离和。

当前我们要输入 $s_i$ （假设它在 $a$ 中的位置 $now$ ），上一时刻一根手指在 $s_{i-1}$ （假设它在 $a$ 中的位置 $u$ ），另一根在 $j$ （它在 $a$ 中的位置 $j$ ）。我们有两种选择：

移动停在 $u$ 的手指去按 $now$ ：那么另一根手指仍然在 $j$ 。

$dp[i][j] = \min(dp[i][j], dp[i-1][j] + \min(|now- u|,26 - |now- u|)))$

移动停在 $j$ 的手指去按 $now$ ：那么另一根手指的位置变成了 $u$ 。

$dp[i][u] = \min(dp[i][u], dp[i-1][j] + \min(|now-j|,26 - |now- j|))$

初始状态为 $dp[0][0] = 0$ 。

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

~~本题也可以在 $O(n \times 26 \times 26)$ 常数小的时候通过。~~

T5

100%

由于 $T$ 高达 $10^5$ ，这就要求我们要先预处理出所有答案。

考虑 $x^2 - y^2 = z^3$ 。根据平方差公式，可以拆解为：

(x + y)(x - y) = z^3

我们令 $u = x + y$ ， $v = x - y$ 。显然有 $u \cdot v = z^3$ 。根据 $u$ 和 $v$ ，我们可以反推 $x$ 和 $y$ ：

x = \frac{u + v}{2}, \quad y = \frac{u - v}{2}

为了保证 $x$ 和 $y$ 均为正整数，必须满足两个条件：

$u$ 和 $v$ 必须同奇偶（即 $(u + v) \equiv 0 \pmod 2$ ）。
$u > v$ （以保证 $y > 0$ ），并且计算出的 $x \le n$ 。

那么也就是说，只要我们知道 $z^3$ 的所有因数，就可以快速求出所有满足条件的 $(x,y,z)$ 。

具体计算方式如下：

题目要求 $x \le n$ ，当 $n = 10^6$ 时，最大的 $x^2$ 是 $10^{12}$ 。因为 $y \ge 1$ ，所以 $z^3 = x^2 - y^2 < x^2 \le 10^{12}$ 。这意味着 $z \le \sqrt[3]{10^{12}} = 10^4$ 。最大的 $z$ 只有 $10000$ 级别，因此我们可以暴力枚举所有的 $z$ ，去计算 $z^3$ 的所有可能分解方式。但是直接用 $O(\sqrt{z^3})$ 的方法显然是不行的，我们需要一些其他方法。

首先我们可以在 $O(\sqrt{z})$ 算出 $z$ 的质因数分解：

z = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}

那么 $z^3$ 的质因数分解其实就是：

z^3 = p_1^{3e_1} p_2^{3e_2} \dots p_k^{3e_k}

有了这个分解式，我们可以利用 dfs 直接枚举出 $z^3$ 的所有因子，具体来说，我们只需要枚举一个长度为 $k$ 的数组 $(c_1 ,c_2 ,c_3 ,\cdots c_k)$ ，满足 $0 \leq c_i \leq 3e_i$ 。那么

p_1^{c_1} p_2^{c_2} \dots p_k^{c_k}

它就是一个 $z^3$ 的一个因子。对于每个因子 $u$ ，只需要根据上述方法计算出对应的 $(x,y,z)$ 即可。设 $cnt[i]$ 表示 $x,y,z$ 中最大值为 $i$ 时满足条件的三元组个数（实际上 $x > \max(y,z)$ ），如果 $x \leq 10^6$ ，我们就可以让 $cnt[x]$ 加上 $1$ ，最后做一次前缀和即可。对于每次查询，我们只需要输出 $cnt[n]$ 的结果就好。

总体时间复杂度为 $O(\sum_{i = 1}^{N^{\frac{2}{3}}}d(z^3) + T)$ 。

T6

100%

考虑分析排序规则：我们可以将物品移到最前或最后。为了使移动代价最小，我们应该保留一个代价最大的子序列不动，然后将其余的元素分别移到它的左边和右边。

什么样的子序列可以“不移动”且能保证其余元素移完后整体有序？它必须满足在数值上是连续的（如标号 $L, L+1, \dots, R$ ），并且在当前数组中的相对位置是从左到右递增的（即 $pos[L] < pos[L+1] < \dots < pos[R]$ ）。

因此，问题的本质是：在数值 $1 \dots n$ 构成的序列中，找到一个连续的区间 $[L, R]$ ，满足对于任意 $k \in [L, R-1]$ 都有 $pos[k] < pos[k+1]$ ，且使得该区间的代价和 $\sum_{k=L}^R W_k$ 最大。最终答案即为：所有物品的总代价 $\sum W - \max(\text{合法区间代价和})$ 。

我们可以考虑用线段树维护连续子段最大和（做法与区间最大子段和类似）：

我们用物品的标号 $1 \dots n$ 作为线段树的底层叶子节点。

线段树的每个节点维护区间 $[l, r]$ 内的以下信息：

$sum$ : 该数值区间所有物品的 $W_i$ 之和。
$pre$ : 从左端点 $l$ 开始，满足 $pos$ 递增的最长合法前缀的权值和。
$suf$ : 以右端点 $r$ 结束，满足 $pos$ 递增的最长合法后缀的权值和。
$mx$ : 该数值区间内，完全合法的子段的最大权值和。
$inc$ : 该数值区间 $[l, r]$ 是否整体合法（即 $pos[l] < pos[l+1] \dots < pos[r]$ ）。

当合并左子节点（区间 $[l, mid]$ ）和右子节点（区间 $[mid+1, r]$ ）时，连接点是 $mid$ 和 $mid+1$ 。当且仅当 $pos[mid] < pos[mid+1]$ 时，左区间的后缀与右区间的前缀可以拼合。通过标准的子段和维护套路更新对应变量即可。这里不再赘述。

时间复杂度：建树 $O(n \log n)$ ，每次修改和查询只需 $O(\log n)$ 。总时间复杂度为 $O((n+q)\log n)$ 。