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

T1

100%

直接根据题目要求进行判断和计算即可。

先判断外卖的菜品总价 $S$ 是否满足满 $100$ 元的条件：

如果 $S \ge 100$ ，则享受立减 $20$ 元的优惠，实际菜品花费为 $S - 20$ 元。
如果 $S < 100$ ，则不享受优惠，实际菜品花费为 $S$ 元。

最后，不管是否享受过优惠，都需要加上固定 $5$ 元的配送费。

输出最终求得的实际菜品花费与配送费的和即可。

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

T2

100%

我们可以直接通过循环模拟倒水的过程。

从 $i = 1$ 到 $n - 1$ 依次遍历每个杯子进行操作：

在第 $i$ 次操作中，第 $i+1$ 个杯子最多还能装的水量，等于其最大容量减去当前水量，即剩余容量 $rem = b_{i+1} - a_{i+1}$ 。

第 $i$ 个杯子会尽可能多地倒水，所以实际倒给第 $i+1$ 个杯子的水量为 $W = \min(a_i, rem)$ 。

倒水完成后，更新两个杯子的水量：第 $i$ 个杯子的水量变为 $a_i - W$ ，第 $i+1$ 个杯子的水量变为 $a_{i+1} + W$ 。当 $n - 1$ 次操作全部执行完毕后，按顺序输出数组 $a$ 的每个元素。

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

T3

100%

题目保证根据给出的信息，排列方式只有一种，这意味着所有人构成了一条完整的接力链。我们可以顺着接力棒传递的顺序，从前往后依次计算出每名选手的起跑时间。

已知 $a_i$ 是第 $i$ 个人前一棒的选手编号，这就说明第 $i$ 个人是 $a_i$ 的下一棒。因此，我们可以建立一个数组 $nxt$ ，令 $nxt[a_i] = i$ ，用来记录每个人要把接力棒传给谁。

同时，找出满足 $a_i = 0$ 的选手，这名选手就是第一棒起跑的选手，将其记为起点。

接下来，从起点开始，顺着 $nxt$ 数组依次向后遍历，设 $now$ 为当前在跑步的选手（初始为 $p$ ）， $tim$ 表示当前已经经过的时间：

将当前选手 $now$ 的起跑时间记录为 $tim$ 。
当前选手跑完后，时间会流逝 $t_{now}$ ，因此更新时刻 $tim := tim + t_{now}$ 。
下一位选手起跑，即更新 $now = nxt[now]$ 。

由于总共有 $n$ 个人，只需按上述逻辑循环推导 $n$ 次，即可求出所有人的起跑时间，最后按编号顺序输出即可。

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

T4

100%

首先分析题目中的两种操作会对答案产生什么影响。

对于选定的前缀 $i$ ，如果我们给 $a_1, a_2, \dots, a_i$ 全部加上 $1$ ，那么两数组的积 $\sum_{j=1}^n a_j b_j$ 实际上会增加 $\sum_{j=1}^i b_j$ 。

同理，如果我们给 $a_1, a_2, \dots, a_i$ 全部减去 $1$ ，总的积会减少 $\sum_{j=1}^i b_j$ 。

记 $S_i = \sum_{j=1}^i b_j$ 为数组 $b$ 的前缀和。

那么对于前缀 $i$ 实施一次最佳操作（如果 $S_i > 0$ 我们选择加法，如果 $S_i < 0$ 我们选择减法），我们总是能让总的积增加 $|S_i|$ 。

注意到对于任意一个前缀 $i$ ，它能带来的单次最大收益就是固定的 $|S_i|$ ，而且不同前缀的操作是完全独立、互不干扰的。为了让两数组最终的积最大化，我们只需要贪心地执行操作：优先选择能够带来最高收益的前缀。

所以我们可以将所有 $\{ S_i ,c_i\}$ 按照 $|S_i|$ 的大小进行排序，贪心取即可。最后记得加上一开始的 $\sum_{i = 1}^{n} a_i \times b_i$ 的值。

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

T5

100%

先考虑计算 $f(x)$ 的值。

由于 $A \oplus B = x$ ，所以 $B = A \oplus x$ 。

首先可以发现如果 $A = x$ ，那么 $B = 0$ ，此时是不符合条件的，故实际上 $A,B$ 的范围为 $1 \leq A,B < x$ 。

设数字 $x$ 的二进制最高位为 $k$ （即 $2^k \le x < 2^{k+1}$ ）。由于 $A \oplus B = x$ ，那么 $A$ 和 $B$ 在第 $k$ 位上必然是一个为 $0$ ，一个为 $1$ 。

不妨设 $A$ 的第 $k$ 位为 $1$ ， $B$ 的第 $k$ 位为 $0$ 。

显然 $A$ 的范围为 $[2^k ,x-1]$ ，接下来我们可以证明 $A$ 如果取其中的任意一个值都是满足条件的。

也就是说对于范围内的 $A$ ，其对应的 $B$ 必然满足 $B < x$ ，其实这一步十分显然： $B$ 的二进制第 $k$ 位是 $0$ ，而 $x$ 的二进制第 $k$ 位是 $1$ ，比 $k$ 更高的位置二者都是 $0$ ，故 $B < x$ 。

考虑到 $A$ 和 $B$ 在第 $k$ 位可以互换，所以对于某个 $x$ ，合法的正整数对数 $f(x) = 2(x - 2^k)$ 。

接下来我们需要快速计算 $\sum_{i=1}^n f(i)$ ：

不妨设 $\operatorname{highbit}(x)$ 为 $x$ 的最高位表示的数字，即 $f(x) = 2 (x - \operatorname{highbit}(x))$ 。

我们要求的是

$$\begin{aligned} \sum_{i = 1}^{n} f(i) &= \sum_{i = 1}^{n} 2 (i - \operatorname{highbit}(i)) \\ &= \sum_{i = 1}^{n} 2i - 2 \sum_{i = 1}^{n} \operatorname{highbit}(i) \end{aligned}$$

其中 $\sum_{i = 1}^{n} 2i$ 可以直接用等差数列求和计算（结果为 $n \times (n + 1)$ ）， $\sum_{i = 1}^{n} \operatorname{highbit}(i)$ 可以通过最高位来计算。

具体来说，我们可以先枚举最高位（假设为 $k$ ），此时最高位是 $k$ 的数的范围是 $[2^{k} , \min(2^{k + 1} - 1, n)]$ ，故这一段的求和结果为 $2^{k} \times (\min(2^{k + 1} - 1, n) - 2^{k} + 1)$ 。

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

T6

100%

首先有一个非常关键的结论：第一个不能整除区间 LCM 的数字 $x$ 必然是一个质数的次幂（即 $x = p^k$ ）。

证明：假设最小的不能整除 LCM 的数 $x$ 是一个包含不同质因数的合数。那么 $x$ 可以分解为若干个两两互质的质数次幂的乘积，这些质数次幂都严格小于 $x$ 。因为 $x$ 是“最小的”不能整除的数，所以这些严格小于 $x$ 的质数次幂必然都能整除 LCM。而它们两两互质，故它们的乘积 $x$ 也必然能整除 LCM，产生矛盾。因此，第一个不能整除的数字绝不可能是包含多种质因数的合数。

所以，我们只需要寻找最小的、且其倍数在查询区间 $[l, r]$ 中没有出现过的质数次幂 $p^k$ 。由于 $a_i \le 10^6$ ，能够成为 $a_i$ 约数的质数次幂最大不超过 $10^6$ 。大于 $10^6$ 的最小质数次幂是 $1000003$ （它本身是质数）。这意味着对于所有的询问区间，无论其内的元素是多少， $1000003$ 这个质数次幂绝对不可能出现在它的因子中。所以，任何询问的最小缺失质数次幂最大就是 $1000003$ ，答案不可能超过 $1000002$ 。

考虑先预处理出 $10^6$ 内的所有数字的质因子。

我们可以离线处理所有询问：

将所有询问区间按照右端点 $r$ 从小到大排序。
建立一棵线段树，维护的值域为 $2 \sim 1000003$ 。线段树维护区间内的最小值，其中第 $i$ 个值表示从小到大的第 $i$ 个质数幂在数组中最后一次出现的位置
随着指针 $r$ 向右移动，我们通过预处理好的最小质因子数组在 $O(\log a_r)$ 时间内对 $a_r$ 进行质因数分解。对于它的每一个极大质因子次幂（例如 $p^m | a_r$ ），我们将 $p^1, p^2, \ldots, p^m$ 在线段树上对应位置的值更新为当前的 $r$ 。
对于右端点正好在 $r$ 的所有询问 $[l, r]$ ，由于我们要找最小的缺失质数次幂，只需在线段树上寻找：从左往右第一个（最小的）其最后出现位置 $< l$ 的位置。这一步可以在线段树上二分得到。因为线段树维护了最小值，如果左子树的最小值 $< l$ ，说明缺失的最靠前质数次幂在左半区，我们就向左递归；否则向右递归。查找到的叶子节点对应的值再减去 $1$ ，即为该次询问的答案。

时间复杂度 $O(n \log n \log V + V \log V)$ （其中 $V = 10^6$ ）。