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

T1

100%

至少购买一种沙威玛的人数为 $买了第一种的人数 + 买了第二种的人数 - 两种都买的人数 = p_2 + p_3 - p_4$。

因此，什么都没买的人数为 $p_1 - (p_2 + p_3 - p_4)$。

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

T2

100%

本题可以通过将所有时间点统一转换为“相对于 2026 年 1 月 1 日 00:00 的总小时数”来简化判断。

一开始题目给出的时间起点是 $1$ 月 $9$ 日 $20:00$。这相当于 $2026$ 年已经过了 $8$ 个完整的日子（$1$ 号到 $8$ 号）以及 $9$ 号的 $20$ 个小时。因此，我们将输入的时间偏移量 $x$ 加上 $24 \times 8 + 20$，此时 $x$ 表示当前时刻距离年初的总小时数。

接着，我们可以处理出休假所代表的小时数，设 $S[i]$ 表示前 $i$ 个月的天数。

• 开始时间 $L = (S[m_1 - 1] + d_1 - 1) \times 24$，表示休假开始前完整经过的小时数。

• 结束时间 $R = (S[m_2 - 1] + d_2) \times 24$，表示休假结束时完整经过的小时数（包含 $d_2$ 日全天）。

接着我们可以进行判断：

• 休假判定：如果 $x \ge L$ 且 $x < R$，说明在休假期间，输出 Shawarma is the best food。

• 营业时间判定：如果不在休假期间，通过 $x \bmod 24$ 得到当前时刻在一天中的小时数。如果该值在 $[6, 18]$ 之间，输出 I love Shawarma，否则输出 Shawarma is the best food。

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

T3

100%

题目要求判断两个序列 $a$ 和 $b$ 是否“本质相同”，定义为：对于任意下标 $i, j$，满足 $a[i] < a[j] \iff b[i] < b[j]$。

设 $A[i]$ 表示 $a[i]$ 里是整个 $a$ 数组里第 $A[i]$ 小的数字，$B[i]$ 表示 $b[i]$ 里是整个 $b$ 数组里第 $b[i]$ 小的数字。例如 $a = \{ 100 , 99 ,8, 10\}$，那么 $A = \{ 4, 3, 1,2 \}$。可以将 $A$ 和 $B$ 理解成 $a$ 和 $b$ 的“排名数组”。题目的要求也就是说 $a[i]$ 和 $b[i]$ 所占的排名需要相同。

即如果 $A$ 数组和 $B$ 数组完全相同，那么答案为 Yes，否则为 No。

为什么？

• 如果 $A$ 数组和 $B$ 数组完全相同，显然成立。
• 如果 $A$ 数组和 $B$ 数组不同，考虑找出某个 $(i,j)$ 不满足条件，具体证明如下：

不妨设有个下标 $k$，满足 $A[k] < B[k]$。

记 $V = B_k$。由于 $b_k$ 的排名是 $V$，说明在数组 $b$ 中，存在 $V-1$ 个比 $b_k$ 更小的本质不同的数值。

我们可以找到一组下标 $p_1, p_2, \dots, p_{V-1}$，使得它们的排名分别为 $1, 2, \dots, V-1$。

即：$B_{p_1}=1, B_{p_2}=2, \dots, B_{p_{V-1}}=V-1$。

此时，在数组 $b$ 中，这组下标构成了一个严格递增的链：

$$b_{p_1} < b_{p_2} < \dots < b_{p_{V-1}} < b_k$$

如果数组 $a$ 和 $b$ 本质相同，那么这一组下标在 $a$ 中也必须满足同样的严格递增关系：

$$a_{p_1} < a_{p_2} < \dots < a_{p_{V-1}} < a_k$$

如果上式成立，意味着 $a_k$ 至少比 $a$ 中的 $V-1$ 个其他数值要大。那么 $a_k$ 的排名 $A_k$ 至少应该是 $(V-1) + 1 = V$。

即推导出 $A_k \ge V$。但这与我们的假设 $A_k < B_k = V$ 矛盾。故答案是 No。

现在我们该如何算出 $A$ 和 $B$ ？

将 $a$ 复制一份并排序去重，利用二分查找将 $a$ 中的每个数值替换为其排名（二分查找的下标就是它的排名），得到数组 $A$ ，数组 $B$ 的做法同理。

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

T4

100%

利用题目性质进行分析。 题目中的操作是删除等差数列。由于任意两个数都能构成等差数列，这意味着如果我们能把元素删到只剩两个相邻，它们就可以一起消掉。

结论：

1. 若 $n$ 为偶数，答案永远为 $0$。
   • 因为我们可以简单地将数组分为 $n/2$ 对，每对相邻元素组成长度为 $2$ 的等差数列依次删除。
2. 若 $n$ 为奇数，答案为 $0$ 或 $1$。
   • 想要将 $n$（奇数）个元素全部删除，必须在某一步删除一个长度为奇数的等差数列（如果全是偶数的话，删除的个数不可能是奇数）。
   • 对于删除长度为奇数的等差数列，我们可以把它拆分成删除一个长度为 $3$ 的等差数列+删除若干次长度为 $2$ 的等差数列。删掉这一部分后，剩下的数是偶数，自然就能全部删完。也就是说，我们的策略就变成了：删若干次长度为 $2$ 的数列，删一次长度为 $3$ 的数列，删若干次长度为 $2$ 的数列。
   • 假设我们要删除 $a_i, a_j, a_k$ 这三个构成等差数列的数。为了能将它们一起删除，必须先把它们之间的元素删光。
   • $a_i$ 和 $a_j$ 之间的元素个数为 $j - i - 1$。要能完全删除这些中间元素（使用偶数长度的删除操作），必须满足 $j - i - 1$ 是偶数，即 $j - i$ 是奇数。这意味着 $i$ 和 $j$ 的奇偶性不同。
   • 同理，$j$ 和 $k$ 的奇偶性也必须不同。
   • 因此，若要删除 $a_i, a_j, a_k$，必须满足：$i, k$ 奇偶性相同，$j$ 与它们奇偶性不同。

故当 $n$ 为奇数时，检查是否存在下标 $i < j < k$，满足 $i \equiv k \pmod 2$，$j \not\equiv i \pmod 2$，且 $a_i + a_k = 2a_j$。如果存在，答案为 $0$，否则为 $1$。

这可以通过枚举中间点 $j$，然后在左右两侧寻找同奇偶性的 $a_i, a_k$ 来判定。

单组数据的时间复杂度 $O(n^2 \log n)$。

T5

100%

我们先来考虑 $l = r$ 的时候，两个人是怎么行动的。假设必定选择的是 $i$ 这个位置 （$i = l = r$）。

1. 情况一：$x = 0$，显然此时答案为 $a_i$。
2. 情况二：$x = 1$，此时 jiangly 选择先手，ta 会选择 $i$ 两边中小的那个。故答案为 $\max(a[i - 1],a[i + 1])$。
3. 情况三：$x = 2$，我们考虑 jiangly 选择先手还是后手。

• 选择先手：
  • 如果 jiangly 选择了往左走，那么答案就为 $\min(a[i - 2], a[i])$。
  • 如果 jiangly 选择了往右走，那么答案就为 $\min(a[i + 2], a[i])$。
  • 于是答案为 $\max(\min(a[i - 2], a[i]), \min(a[i + 2], a[i]))$。
• 选择后手：
  • 如果 apiadu 选择了往左走，那么答案就为 $\max(a[i - 2], a[i])$。
  • 如果 apiadu 选择了往右走，那么答案就为 $\max(a[i + 2], a[i])$。
  • 于是答案为 $\min(\max(a[i - 2], a[i]), \max(a[i + 2], a[i]))$.

此时 $\max(\min(a[i - 2], a[i]), \min(a[i + 2], a[i])) \le \min(\max(a[i - 2], a[i]), \max(a[i + 2], a[i]))$，故会选择后手。

4. 情况四：$x$ 为大于 $1$ 的奇数。

由于博弈的可逆性（即一方走了一步，另一方可以走回来），在双方都绝顶聪明且目标相反（一个想变大，一个想变小）时，棋子实际上会在 $i$ 及其邻居之间“拉扯”。

当 $x$ 是奇数时，jiangly 总是可以通过安排先手顺序，让自己走最后一步。不管中间过程如何，jiangly 总能利用最后一步将局面控制在 $x=1$ 的最优解状态。

因此，所有奇数 $x$ 的情况等价于 $x=1$。答案为 $\max(a_{i - 1}, a_{i + 1})$。

5. 情况五：$x$ 为大于 $2$ 的偶数

同理，由于“拉扯”现象，所有 $x \ge 2$ 的偶数情况等价于 $x=2$。

jiangly 依然会选择他在 $x=2$ 时推导出的最优策略（即选择后手）。

答案为 $\min(\max(a_{i - 2}, a_{i}), \max(a_{i + 2}, a_{i}))$。

此时考虑一般情况，我们可以算出上面上述情况中每个位置的答案。apiadu 会选择对应情况中结果最小的 $i$。利用 ST 表找到最小值即可。

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

T6

100%

题目要求计算从起点 $s$ 到终点 $t$ 的路径费用。 在路径上，经过每个点 $u$ 时，我们需要购买 $w_u$ 的体力。购买单价取决于从起点 $s$ 到当前点 $u$ 的路径上所有节点中 $a_v$ 的最小值。

即设 $path(s, u)$ 表示 $s$ 到 $u$ 的简单路径上的点集。 点 $u$ 的花费为：$cost_u = w_u \times \min_{v \in path(s, u)} \{ a_v \}$。 总花费为：$\sum_{u \in path(s, t)} cost_u$。

首先，利用树链剖分将树上复杂的路径 $s \to t$ 拆分为 $O(\log N)$ 个线性的连续区间。 由于路径具有方向性（单价取决于前缀最小值），我们需要区分处理：

• 向下走的路径（从 $LCA$ 到 $t$）：按照正常的 DFS 序处理。
• 向上走的路径（从 $s$ 到 $LCA$）：其行进方向与 DFS 序相反。我们可以将这部分的序列逻辑上进行翻转，将其转化为向右走的问题，从而复用向下走的做法。

现在的问题转化为：在一个序列上，给定一个区间和进入该区间时的初始最低价格 $V$，求通过该区间的总花费，并求出离开时的最低价格。

在这个区间走时，价格的变化呈现出阶梯状下降的规律：

1. 维持阶段：如果当前位置本身的价格高于手中的最低价格 $V$，则购买单价维持 $V$ 不变。
2. 更新阶段：一旦遇到一个价格低于 $V$ 的位置，购买单价立即更新为该位置的价格。此后单价保持不变，直到遇到下一个更低的价格。

第一步我们可以用 ST 表来维护，从而找到第一个 $< V$ 的位置。

考虑第二步的答案怎么维护。

我们可以预处理出从当前位置开始，连续跳跃 $2^k$ 次（即连续找 $2^k$ 次下一个更小值）后到达的位置。同时预处理出这 $2^k$ 次跳跃过程中的总花费。利用这两个值可以维护出第二步的操作的值。

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