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

T1

100%

直接读取这个字符串，找出第一个数字 $a$、中间的符号 $op$ 和第二个数字 $b$。

直接使用 if-else 判断即可：

• 如果符号是 <，判断是否 $a < b$。
• 如果符号是 =，判断是否 $a = b$。
• 如果符号是 >，判断是否 $a > b$。

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

T2

100%

题目要求将一个 $m$ 位的数字 $a$ 补齐前导零变为 $n$ 位。 由于 $a$ 很大，所以需要用字符串读入。具体步骤如下：

1. 先计算需要补零的个数：$k = n - m$。
2. 输出 $k$ 个 0。
3. 输出原始数字 $a$。

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

T3

30%

我们可以模拟每一批宝石的生成过程。 使用一个变量 $cnt$ 记录当前已经收集了多少宝石，$level$ 记录当前等级。

循环直到收集满 $n$ 个宝石。对于每一颗宝石，计算其贡献并累加到答案中。

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

100%

观察规律可以发现：

• 第 $i$ 批宝石的数量为 $2^{i-1}$，等级为 $i$。
• 这些宝石在队伍中的位置是从 $2^{i-1}$ 到 $2^i - 1$。
• 这一批宝石的总能量贡献为：$$\sum_{j =2^{i - 1}}^{2^i - 1} (i \times j \times 2) = 2 \times i \times \sum_{j =2^{i - 1}}^{2^i - 1} j = 2 \times i \times (\frac{2^{i - 1} \times (2^{i - 1} + 2^{i} - 1)}{2})$$

由于 $n \le 10^{12}$，批次数量大约在 $40$ 左右，时间复杂度 $O(\log n)$。

T4

30%

对于每个询问 $w_i$，我们枚举数组 $a$ 的每一个下标 $j$ 作为可能的购买点。

如果 $a_j \le c$，为了满足礼物价值至少为 $w_i$，我们需要 $c + b_j \ge w_i \implies c \ge w_i - b_j$。

同时为了能取到下标 $j$，花费 $c$ 必须至少是 $a_j$（且不能达到 $a_{j+1}$，但题目求最小花费，我们只需关注下界）。

所以如果强制选中下标 $j$，最小花费为 $\max(a_j, w_i - b_j)$。

遍历所有 $j$，取最小值即可。

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

100%

观察支付金额 $c$ 与获得的礼物价值之间的关系：

• 随着支付金额 $c$ 的增加，我们可以购买的商品下标 $d$（满足 $a_d \le c$ 的最大下标）是非递减的。 - 题目保证数组 $b$ 是单调递增的，所以 $b_d$ 也是非递减的。
• 因此，总价值 $V(c) = c + b_d$ 关于 $c$ 是单调递增的。

考虑二分答案。

对于当前二分的支付金额 $mid$：

• 在数组 $a$ 中查找第一个大于 mid 的位置，这一步可以通过 C++ 的 upper_bound 函数在 $O(\log n)$ 时间内完成。
• 此时获得的礼物价值 $val = mid + b[d]$。 判断 $val \ge w$ 是否成立即可。

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

T5

100%

题目中的“总工作效率”可以写成：

$$\sum s_i \times i = \sum_{i=1}^n i \times (\sum_{u \in \text{subtree}(i)} val(u))$$

交换求和顺序，可以发现每个节点 $u$ 的能力值 $val(u)$ 被计算的次数是它所有祖先的编号之和。

记 $W_u = \sum_{x \in \text{ancestors}(u)} x$。

这可以通过一次 DFS 在 $O(N)$ 时间内求出。

此时问题转化为：从 $n$ 个位置中选出 $k$ 个位置 $x_1, \dots, x_k$，从 $n$ 个候选人中选出 $k$ 人 $y_1, \dots, y_k$，将位置 $x_j$ 的系数由 $a_{x_j}$ 换成 $b_{y_j}$，最大化 $\sum val(u) \times W_u$。

由于题目限制了下标顺序：$x_1 < x_2 < \dots$ 且 $y_1 < y_2 < \dots$。这意味着我们实际上是在做“序列匹配”。

考虑动态规划：

设 $dp[i][j]$ 表示考虑了前 $i$ 个职位和前 $j$ 个候选人所能获得的最大总效率。 对于第 $i$ 个职位，我们有三种选择：

1. 不替换：保持原样，使用 $a_i$。此时可以从状态 $dp[i-1][j]$ 转移而来。 贡献：$dp[i-1][j] + a_i \times W_i$。
2. 替换：使用第 $j$ 个候选人替换第 $i$ 个职位。此时必须消耗掉第 $j$ 个候选人，从 $dp[i-1][j-1]$ 转移。 贡献：$dp[i-1][j-1] + b_j \times W_i$。
3. 跳过候选人：第 $j$ 个候选人不被使用。这等价于状态回退到 $dp[i][j-1]$（但这通常包含在 $dp$ 状态定义中，即“前 $j$ 个候选人”）。

故方程为： $dp[i][j] = \max(dp[i-1][j] + a_i \times W_i,dp[i-1][j-1] + b_j \times W_i,dp[i][j-1])$。

最终答案为 $dp[n][m]$。

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

T6

100%

由于值域很小，我们可以利用线段树维护区间内每个数值出现次数和数字变为多少的映射。

线段树信息如下：

• 每个节点维护一个数组 $cnt[21]$，表示该区间内数值 $v$ 出现的次数。

标记信息如下：

• 维护一个映射数组 $map[21]$。$map[v] = t$ 表示原本数值为 $v$ 的数字，现在变成了 $t$。 初始时，$map[v] = v$。

对于操作 $1$ （区间修改 1 l r x y）： 在线段树上定位区间。对于覆盖的节点，更新其懒标记。 更新逻辑：将所有原本映射到 $x$ 的值，改为映射到 $y$。即遍历 $k=1 \dots 20$，若 $map[k] == x$，则 $map[k] = y$。 同时更新当前节点的 $cnt$ 数组：$cnt[y] += cnt[x]$，$cnt[x] = 0$，并更新 $sum$。记得下传标记。

对于操作 $2$ （区间查询 2 l r）： 线段树区间求和即可。

由于值域只有 $20$，每次更新标记和合并信息的代价是常数 $C \approx 20$。

总时间复杂度 $O(20 \cdot Q \log N)$。

T7

100%

分两类讨论：$n \leq m$ 和 $n > m$ 两种情况。

$n \leq m$

定义 $dp[i][j]$ 为长度为 $i$ 的排列中，逆序对数量恰好为 $j$ 的排列个数。

状态转移方程为：

$$dp[i][j] = \sum_{k=0}^{i-1} dp[i-1][j-k]$$

利用前缀和优化，时间复杂度为 $O(nm)$。

$n > m$

观察转移方程：$dp[i][j] = \sum_{k=0}^{i-1} dp[i-1][j-k]$。

当 $i > m$ 时，插入第 $i$ 个数字可以产生的逆序对数量范围是 $0 \sim i-1$。

由于我们要计算的逆序对数量上限是 $m$，而 $i-1 \ge m$，这意味着我们可以增加 $0 \sim m$ 任意数量的逆序对而不受 $i$ 的限制。

换句话说，对于 $j \le m$ 的部分，求和区间总是 $[0, j]$（因为 $j-k$ 不能小于 0，而 $j < i$，所以求和的下界自然被 $0$ 截断，而不是被 $i-1$ 限制）。

因此，当 $i > m$ 时，状态转移方程简化为：

$$dp[i][j] = \sum_{k=0}^{j} dp[i-1][j-k] = \sum_{p=0}^j dp[i-1][p]$$

这恰好就是对数组 $dp[i-1]$ 做了一次前缀和操作。

我们知道，对一个数组 $A$ 进行 $K$ 次前缀和后，第 $x$ 个位置的值可以用组合数直接计算（类似于杨辉三角或插板法）。

若 $B$ 是数组 $A$ 进行 $K$ 次前缀和后的结果，则

$$B[x] = \sum_{i=0}^x A[i] \times \binom{K + (x-i) - 1}{x-i}$$

具体证明这里不再赘述，可以用插板法或者生成函数等方法来得到。

也就是说，我们只要算出 $dp[m][0 \cdots m]$，再对 $dp[m]$ 这个数组做 $n - m$ 次前缀和即可。

注意这里的组合数 $\binom{a}{b}$需要用到 $O (b)$ 的写法。

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