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

T1

100%

数据范围非常小，直接枚举答案即可。

从小到大枚举 $x$ 从 $0$ 到 $10000$。对于每个 $x$，检查是否满足所有的 $n$ 个条件（即对于所有 $i$，判断 $x \bmod a_i$ 是否等于 $b_i$）。

如果找到满足条件的 $x$，直接输出并结束程序。 如果枚举完所有可能的 $x$ 都没有找到答案，输出 $-1$。

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

T2

100%

对于每个询问 $(l, r)$，遍历数组 $a$ 中下标从 $l$ 到 $r$ 的元素，求出其中的最大值 $max\_val$ 和最小值 $min\_val$。

判断 $max\_val - min\_val \le k$ 是否成立即可。

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

T3

30%

枚举所有可能的子数组。 第一层循环枚举左端点 $l$ 从 $1$ 到 $n$。 第二层循环枚举右端点 $r$ 从 $l$ 到 $n$。 第三层循环遍历 $a[l \dots r]$ 寻找最大值和最小值，判断是否满足条件。 时间复杂度 $O(n^3)$。

100%

在 $30\%$ 的基础上优化寻找最值的过程。

枚举左端点 $l$ 从 $1$ 到 $n$。

然后枚举右端点 $r$ 从 $l$ 到 $n$。

在 $r$ 向右移动的过程中，动态维护当前区间 $[l, r]$ 的最大值 $mx$ 和最小值 $mn$。

每次移动后判断 $mx - mn \le k$，如果满足则答案加一。

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

T4

100%

题目要求子序列的极差（最大值减最小值）不超过 $k$。 注意到，子序列的极差只与选出的数值有关，而与这些数值在原数组中的相对位置无关。因此，我们可以先将原数组 $a$ 从小到大进行排序。

排序后，问题转化为：在有序数组 $a$ 中选出一个子集，使得子集内最大值与最小值之差 $\le k$。

为了不重不漏地统计所有合法子序列，我们可以枚举子序列中最小值在排序后数组中的位置。

假设排序后的数组为 $a_1, a_2, \dots, a_n$。 我们枚举 $i$（$1 \le i \le n$）作为子序列中下标最小的元素（即我们在排序后的数组中选取的第一个元素是 $a_i$）。 此时，子序列的最小值即为 $a_i$。

为了满足极差限制，子序列中的其他元素 $a_j$ 必须满足 $a_j - a_i \le k$，即 $a_j \le a_i + k$。 因为数组是有序的，我们可以找到一个最大的下标 $r$，使得 $a_r \le a_i + k$。那么，所有满足条件的元素都在下标区间 $[i, r]$ 内。

对于固定的 $i$，合法的子序列必须：

1. 包含 $a_i$（作为选取的下标最小的元素）。
2. 其余元素可以从区间 $(i, r]$（即下标 $i+1$ 到 $r$）中任意选取。

区间 $(i, r]$ 的长度为 $r - i$。该区间内每个元素都有“选”或“不选”两种可能，因此方案数为 $2^{r-i}$。

对于每个 $i$ ，我们可以用二分或双指针算出对应的 $r$。

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

T5

100%

这是一道最短路问题。

定义状态 $(x, y, s)$，表示 apiadu 位于 $(x, y)$，且此时持有青蛙的状态为 $s$（$s=0$ 表示无青蛙，$s=1$ 表示有青蛙）。

状态转移如下：

1. 普通移动：从 $(x, y, s)$ 向四个方向移动到 $(nx, ny)$，花费 $1$ 秒。条件：$(nx, ny)$ 不是大树 #。状态变为 $(nx, ny, s)$。
2. 拾取青蛙：如果在 $(x, y)$ 处有青蛙（地图字符为 F）且 $s=0$，可以花费 $1$ 秒捡起。状态变为 $(x, y, 1)$。
3. 投掷青蛙并移动：如果 $s=1$，且四周某个方向 $(nx, ny)$ 是大树 #，可以花费 $2$ 秒（投掷$1$秒+移动$1$秒）移动到该位置。移动后青蛙消失，且该位置重新变回大树（意味着不能在该位置停留，但在到达的那一刻是安全的，且已经处于该坐标）。状态变为 $(nx, ny, 0)$。

使用 Dijkstra 算法（或 0-1 BFS 的变种，因为边权只有 1 和 2）求解从 $(1, 1, 0)$ 到 $(n, m, 0)$ 或 $(n, m, 1)$ 的最短路。 时间复杂度 $O(nm \log (nm))$。

T6

100%

直接统计二元组 $(S, T)$ 的数量比较困难。我们可以转换视角：枚举最终的评测状态（即经过 Bob 修改后的状态序列）。

假设我们确定了一个最终状态序列 $Fin$，它包含 $cnt_{wa}$ 个 WA 和 $cnt_{ac}$ 个 AC，且满足“存在连续 $m$ 个 WA”的条件。那么，有多少对 $(S, T)$ 可以生成这个 $Fin$ 呢？

对于 $Fin$ 中的每一位 $x$：

• 如果 $Fin_x$ 是 AC：

  • 初始状态 $S_x$ 必须是 AC。
  • $x$ 不能在集合 $T$ 中。
  • 只有 1 种情况。

• 如果 $Fin_x$ 是 WA：

  • 情况 1：$x \in T$。此时 $S_x$ 可以是 AC（被修改成 WA）或 WA（保持 WA）。这是 $2$ 种情况。

  • 情况 2：$x \notin T$。此时 $S_x$ 必须是 WA。这是 1 种情况。

故对于最终状态中的 WA 位置，如果它被选入 $T$，则有 $2$ 种初始可能；没被选入 $T$，则有 $1$ 种初始可能。

假设最终状态中有 $cnt_{wa}$ 个 WA，且 Bob 选择了其中的 $j$ 个位置加入集合 $T$（$0 \le j \le k$且 $j \le cnt_{wa}$），那么对应的 $(S, T)$ 方案数为 $\binom{cnt_{wa}}{j} \times 2^j$。故总的方案为 $\sum_{j = 0}^{\min(cnt_{wa}, k)} \binom{cnt_{wa}}{j} \times 2^j$

因此，我们的解题步骤为： 1.统计有多少种合法的最终状态 $Fin$，按照其中 WA 的总数量进行分类。 2.对于每种 WA 数量，计算上述的每个状态的贡献。

在已知 AC 个数的情况下，如何知道有多少种合法的状态？考虑动态规划。

我们需要求出长度为 $n$，包含 $j$ 个 AC，且是否满足“连续 $m$ 个 WA”条件的序列数量。

设：

• $f[i][j][0]$：长度为 $i$，包含 $j$ 个 AC，未出现过连续 $m$ 个 WA 的方案数。

• $f[i][j][1]$：长度为 $i$，包含 $j$ 个 AC，已出现过连续 $m$ 个 WA 的方案数。

• $s[i][j][k]$ 表示在长度 $\le i$ 的所有前缀中，以 AC 结尾（或空串）且包含 $j$ 个 AC、满足状态 $k$ 的方案数之和。

计算 f

对于当前位置 $i$，枚举 AC 数量 $j$：

1. 当前位放置 AC：

   • 直接从 $i-1$ 转移：
   • $f[i][j][0] += f[i-1][j-1][0]$
   • $f[i][j][1] += f[i-1][j-1][1]$

2. 当前位放置 WA（实际上是放置一段 WA 结尾于 $i$）：

   • 我们不需要一位一位放 WA，而是利用 $s$ 数组，考虑“这一段 WA 是从哪里开始的”。假设上一段以 AC 结尾的位置是 $p$（即 WA 区间为 $(p, i]$），那么 $p$ 的取值范围决定了这段 WA 的长度 $len = i - p$。

   • 情况 A：状态 0 $\to$ 1 (首次达成连续 $m$ 个 WA)

     • 需要这段 WA 长度 $len \ge m$，即 $i - p \ge m \Rightarrow p \le i - m$。
     • 之前的状态必须是 0。
     • 贡献为 $\sum_{p=0}^{i-m} (\text{以p结尾且状态为0的方案}) = s[i-m][j][0]$。

   • 情况 B：状态 1 $\to$ 1 (之前已经达成，现在继续)

     • 无论这段 WA 多长，状态都保持 1。
     • 只要上一位置状态是 1 即可。
     • 贡献为所有之前的状态 1 的总和：$s[i-1][j][1]$。

   • 情况 C：状态 0 $\to$ 0 (仍未达成)

     • 需要这段 WA 长度 $len < m$，即 $i - p < m \Rightarrow p > i - m$。
     • 之前的状态必须是 0。
     • 贡献为 $s[i-1][j][0] - s[i-m][j][0]$（区间和）。

计算 s

$$s[i][j][k] = s[i-1][j][k] + f[i - 1][j - 1][k]$$

其中 $f[i - 1][j - 1][k]$ 在这里表示的是考虑完前 $i$ 个位置后，AC 数为 $j$ ，状态是 $k$ 的方案数（相当于在 $f[i-1][j - 1][k]$ 的末尾加上一个 AC）。

算出数组 $f$ 后，答案为

$$\sum_{cnt_{wa} = 0}^{n} f[n][n - cnt_{wa}][1] \times \big( \sum_{j = 0}^{\min(cnt_{wa}, k)} \binom{cnt_{wa}}{j} \times 2^j \big)$$

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