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

T1

100%

直接计算 $(a\times b) \% 2$ 的值即可。

记得开 long long。

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

T2

100%

从 $L$ 枚举到 $R$ ，然后判断这些数中哪些是质数即可。

注意和可能爆 int，以及 $1$ 不是质数。

时间复杂度 $O(\sqrt{R} (R - L))$。

T3

100%

我们需要尽可能地在当前行塞入更多的单词，只有当放不下时才换行。

在提供的代码中，使用变量 $now$ 来记录当前行已经使用的长度，$ans$ 记录总行数。 一个技巧是：将 $now$ 初始化为 $m$（即假定当前行已满）。$ans$ 一开始是 $0$。

遍历每个单词，设当前单词长度为 $x$：

1. 检查 $x + now + 1 > m$ 是否成立（这里的 $+1$ 代表单词前的空格）。

• 对于第一个单词：由于 $now$ 初始为 $m$，条件必定成立。$ans$ 增加 $1$（变为第一行），$now$ 更新为当前单词长度 $x$。
• 对于后续单词：
  • 如果 $x + now + 1 > m$，说明当前行放不下（加上空格和单词后超出了 $m$），需要换行。$ans$ 加 $1$，$now$ 重置为当前单词长度 $x$。
  • 否则，说明能放下。$now$ 更新为 $now + x + 1$（加上空格和单词长度）。

循环结束后，$ans$ 即为最少行数。

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

T4

30%

数据规模 $n \le 30$。 可以使用四重循环暴力枚举 $i, j, k, l$，判断是否满足 $i < j < k < l$ 且 $a_i + a_j = a_k + a_l$。 时间复杂度 $O(n^4)$。

100%

这里的关键在于 $j < k$ 这个限制。我们可以枚举 $k$，在枚举 $k$ 的同时维护出所有 $a_i + a_j$ 的和。

具体的，我们可以维护一个计数数组 $cnt[i]$，用于存右端点小于当前位置的所有数对的和出现的次数。

首先我们可以让 $k$ 从 $1$ 枚举到 $n$，在这个过程中：

• 枚举 $l$：从 $k + 1$ 到 $n$，在这个过程中统计左边 $a_k + a_l$ 的个数。
• 更新 $cnt$ 数组，因为 $k$ 变大的过程中 $cnt[i]$ 也在变大， 所以我们可以枚举 $i$ 从$1$ 到 $k - 1$，把 $cnt[a_i + a_k]$ 的值 + 1。

最后输出答案即可。

时间复杂度 $O(n ^2 + V)$。

T5

30%

只有 1 类操作。这是一个经典的差分数组（或者线段树）题目。 使用差分数组记录区间加法，最后求前缀和即可。 时间复杂度 $O(n+q)$。

100%

操作之间存在依赖关系：操作 $i$ 可能会调用操作 $j$ ($j < i$)。这构成了一个有向无环图（DAG），且由于只能调用编号更小的机器，依赖方向是单向的。

我们可以计算每台机器最终被实际执行了多少次。

• 定义数组 $cnt[i]$ 表示从指令中得到第 $i$ 台机器被执行的次数。
• 初始时，读取 $q$ 条指令。对于指令 $[l, r]$，我们在差分数组上进行标记，计算前缀和得到初始的 $cnt$ 数组。
• 接下来我们维护一个 $cnt2[i]$ 数组，它表示第 $i$ 个机器在调用机器中得到的次数。从大到小遍历机器编号 $i$ 从 $m$ 到 $1$（因为 $i$ 只会调用比它小的，倒序处理可以将 $i$ 的次数传递给它调用的机器），设 $v$ 为调用该机器的次数，即我们需要先对 $cnt2$ 做后缀和（$cnt2[i] += cnt2[i + 1]$），此时 $v$ 为 $cnt[i] + cnt2[i]$。

1. 如果机器 $i$ 是类型 $2$：说明机器 $l \sim r$ 各被额外调用了 $v$ 次。我们在差分数组上操作（$cnt2[r] += v,cnt2[l - 1]-=v$)。
2. 如果机器 $i$ 是类型 $1$：直接维护答案的差分数组即可。

最后对答案的差分数组做前缀和即可。

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

T6

100%

我们需要通过操作使得序列 $a$ 变为 $b$。令 $d_i = b_i - a_i$，我们的目标是使得操作产生的变化量等于 $d_i$。

假设我们在下标 $i$ 处进行了操作，数值为 $x_i$。这个操作会对序列产生如下影响：

• 下标 $i$ 处增加 $x_i$
• 下标 $(i+1)\bmod n$ 处增加 $-2x_i$
• 下标 $(i+2)\bmod n$ 处增加 $x_i$

对于任意位置 $k$，它的最终变化量是由 $x_k, x_{k-1}, x_{k-2}$（下标均模 $n$）共同贡献的。具体来说，位置 $k$ 接收到来自 $x_k$ 的系数 $1$，来自 $x_{k-1}$ 的系数 $-2$，来自 $x_{k-2}$ 的系数 $1$。 因此，我们需要满足：

$$x_k - 2x_{k-1} + x_{k-2} = d_k \quad (\forall k \in [0, n-1])$$

令 $y_k = x_k - x_{k-1}$。 那么：

$$x_k - 2x_{k-1} + x_{k-2} = (x_k - x_{k-1}) - (x_{k-1} - x_{k-2}) = y_k - y_{k-1}$$

所以方程变为：

$$y_k - y_{k-1} = d_k$$

这是一个关于 $y$ 的差分方程。对该式在整个环上求和：

$$\sum_{k=0}^{n-1} (y_k - y_{k-1}) = \sum_{k=0}^{n-1} d_k$$

左边为裂项相消等于 0，因此有第一个无解判定条件：$\sum_{k=0}^{n-1} d_k = 0$

如果 $\sum d_k \neq 0$，输出$-1$。

由 $y_k = y_{k-1} + d_k$，我们可以递推得到 $y$ 的通解形式。

$$\begin{aligned} &y_0 = y_{n-1} + d_0\\ &y_1 = y_0 + d_1 = y_{n-1} + d_0 + d_1 \\ &... \\ &y_k = y_{n-1} + \sum_{j=0}^k d_j\\ \end{aligned}$$

令 $S_k = \sum_{j=0}^k d_j$（$d$ 的前缀和），则 $y_k = y_{n-1} + S_k$。

由于 $y_k$ 本身是由 $x$ 定义的差分（$y_k = x_k - x_{k-1}$），在环上求和必须为 0：

$$\sum_{k=0}^{n-1} y_k = 0$$

代入 $y_k$ 的表达式：

$$&\sum_{k=0}^{n-1} (y_{n-1} + S_k) = 0 \\ &n \cdot y_{n-1} + \sum_{k=0}^{n-1} S_k = 0 \\ &n \cdot y_{n-1} = - \sum_{k=0}^{n-1} S_k \\$$

为了保证 $y_{n-1}$ 是整数，必须满足第二个无解判定条件：

$$\sum_{k=0}^{n-1} S_k \equiv 0 \pmod n$$

如果不满足，输出 $-1$。

否则，我们可以唯一确定一个基准值 $C = y_{n-1} = (-\sum S_k) / n$。

此时，确定的 $y$ 序列为 $Y_k = S_k + C$。

现在我们有 $x_k - x_{k-1} = Y_k$。这与之前解 $y$ 的形式完全一样。

$$x_k = x_{n-1} + \sum_{j=0}^k Y_j$$

令 $P_k = \sum_{j=0}^k Y_j$（$Y$ 的前缀和），则 $x_k = x_{n-1} + P_k$。

注意这里 $P_{n-1}$ 必然为 0（因为 $\sum Y_k = 0$）。

我们的目标是最小化总代价 $\sum |x_k|$。

代入 $x_k$ 的表达式，也就是求：

$$\sum_{k=0}^{n-1} |x_{n-1} + P_k|$$

这是一个经典的问题：给定一组数 $P_0, P_1, \dots, P_{n-1}$，求一个数 $X$（这里 $X = -x_{n-1}$），使得 $\sum |P_k - X|$ 最小。

最优的 $X$ 是这组数 $P$ 的中位数。带入即可。

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

T7

100%

定义一个序列是好序列当且仅当它可以被消除完。

设 $f0[i][j]$ 为 考虑完前 $i - 1$ 个数，此时第 $i$ 个数有 $j$ 种填法能让序列变成好序列，但此时前 $i$ 个数构成的序列不是好序列的序列数量。 $f1[i][j]$ 为 考虑完前 $i - 1$ 个数，此时第 $i$ 个数有 $j$ 种填法能让序列变成好序列，但此时前 $i$ 个数构成的序列是好序列的序列数量。

转移如下：

1. $f0[i][j] \to f1[i + 1][j]$：在末尾选其中的 $j$ 种填法即可。($f1[i + 1][j] += f0[i][j]\times j$)

2. $f0[i][j] \to f0[i + 1][j]$：在末尾选不在状态中的 $j$ 种填法即可。($f0[i + 1][j] += f0[i][j] \times (m - j)$)

3. $f1[i][j] \to f1[i + 1][j]$：在末尾选其中的 $j$ 种填法即可。($f1[i + 1][j] += f1[i][j]\times j$)

4. $f1[i][j] \to f0[i + 1][j + 1]$：在末尾选不在状态中的 $j$ 种填法即可。($f0[i + 1][j + 1] += f1[i][j] \times (m - j)$)

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