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

T1

100%

读入字符串 $S$。如果它等于 2026.09.25，输出 Mid-Autumn Festival；否则根据题目保证，它一定等于 2026.10.01，输出 National Day。

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

T2

100%

逐轮模拟。为了避免每个球传到后面之后影响之后的判断，可以考虑倒着模拟题目的要求：若 $a_i$ 为奇数，就令新数组中第 $i$ 个盒子的球数减一。若 $i<n$，再令第 $i+1$ 个盒子的球数加一。

时间复杂度为 $O(nr)$。

PS:这个题实际上还存在 $O(n)$ 的做法。

T3

50%

用一个数组从底到顶保存当前文件堆。文件第一次出现时放到数组末尾；第二次出现时，判断它是否位于末尾，然后在线性时间内找到并删除它。

共有 $n$ 次删除，每次最多扫描 $O(n)$ 个文件，时间复杂度为 $O(n^2)$。

100%

仍然使用栈记录文件第一次出现的先后顺序，但删除堆中间的文件时不立即移动其他元素，只将该文件标记为“已取出”。

处理编号 $x$ 的第二次出现时：

1. 此前已经清理过栈顶的无效元素，因此栈顶有效元素就是真实文件堆的顶部；若栈顶为 $x$，答案加一。
2. 将 $x$ 标记为已取出。
3. 不断弹出栈顶已经被取出的文件，直到栈空或栈顶仍在文件堆中。

被埋在中间的无效文件不会影响顶部是谁；等它上方的文件全部取出后，它才会到达栈顶并被清理。每个编号只会入栈、出栈各一次，所以时间复杂度为 $O(n)$。

T4

25%

直接模拟每一轮：扫描所有未移走的盒子，找出物料量最小且编号最小的盒子；再向右扫描其最近的未移走盒子并完成归并。

共进行 $n$ 轮，每轮扫描 $O(n)$ 个位置，时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。

100%

每轮需要完成两个查询：

• 在所有未移走的盒子中，按照“物料量优先、原编号次优先”的规则找到最小者；
• 找到该盒子右侧最近的未移走盒子。

用 $2$ 个 set 来维护即可。第一种用 set 来求最小二元组 $(a_i,i)$，对应本轮应当移走的盒子；第二种按照原编号排序，因此编号 $i$ 的直接后继就是它右侧最近的未移走盒子。

设本轮选中的盒子为 $i$，物料量为 $v$，它在编号顺序中的后继为 $j$。删除 $i$ 后，将 $v$ 加入 $j$，并在第一个 set 中更新 $j$ 的物料量。若 $i$ 的右侧不存在未移走盒子，则直接丢弃 $v$。也可以在最右侧增加一个永远不会被选中的哨兵，使每个真实盒子始终存在后继，统一处理。

每轮只需常数次 set 的查询、删除和插入，时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。

T5

100%

先考虑部分分怎么处理：考虑分层图最短路。

建立两层状态 $(u,t)$：

• $t=0$ 表示消息位于 $u$，下一次必须经过已有线路；
• $t=1$ 表示消息位于 $u$，下一次必须经过不存在的线路。

起点为 $(1,0)$。每次传递后令 $t$ 取反，在这张 $2n$ 个状态的无权图上做 BFS。对于 $n\le2000$，可以用邻接矩阵判断两点之间是否有线路，并在扩展每个状态时枚举全部 $n$ 个目的地。

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

可以发现复杂度瓶颈在于在补图中的边十分多，直接遍历会超时。

可以发现一个显然的性质：在 BFS 的过程中，如果一个点被遍历过了，那么之后的松弛操作均不会考虑这个点，所以如果我们能维护出哪些点没有被遍历过，接下来只要考虑这些没有被遍历过的点即可。可以发现，我们目前只需要维护第 $0$ 层的点。

维护所有尚未到达的第 $0$ 层状态所对应的站点集合 $S$。扩展状态 $(u,1)$ 时，把候选站点分成两类：

• 与 $u$ 没有已有线路且不等于 $u$ 的站点，可以通过本次传递到达，将其第 $0$ 层状态加入 BFS 队列，并从 $S$ 中删除；
• 与 $u$ 有已有线路的站点，本次不能到达，继续留在候选集合中。
• 站点 $u$ 本身不能作为传递目标；若仍在候选集合中，也暂时保留。

为了完成这次划分，可以先标记 $u$ 及其所有邻点，再扫描候选集合。没有被标记的站点全部进入下一层并从候选集合中删除，被标记的站点保留。

这一步的时间复杂度为 $O(|S| + \operatorname{deg} (u))$，这一步之后，$S$ 的大小是 $O(\operatorname{deg} (u))$ 的。

总复杂度仍然是线性的。一个候选站点如果是合法的非邻点，就会被删除，并且之后不再出现；这种扫描每个站点至多发生一次。一个候选站点如果因为与当前点相邻而被保留，这次扫描可以归到对应输入边上；因为它就是当前点而被保留的情况，每个状态也至多发生一次。再加上所有图的边的枚举，总操作数为 $O(n+m)$。

因此时间复杂度为 $O(n+m)$，空间复杂度为 $O(n+m)$。

T6

100%

使用分治统计。对当前区间 $[L,R]$，令中点为 $M$；递归统计完全位于左右两半的答案，只需再统计满足 $l\le M<r$ 的跨中点区间。

对每个 $l\le M$，预处理区间 $[l,M]$ 的最小值、最大值及其位置，分别记为 $mn_L(l),\ mx_L(l),\ posmn_L(l),\ posmx_L(l).$

对每个 $r>M$，类似地预处理 $[M+1,r]$ 的四个量 $mn_R(r),mx_R(r),posmn_R(r),posmx_R(r)$。排列中的值互不相同，所以最值位置唯一。

根据整个区间的最小值、最大值来自哪一半，将跨中点区间分成四种互不相交的情况:

• 最大最小值都在左侧
• 最大最小值都在右侧
• 最大值在右侧，最小值在左侧
• 最大值在左侧，最小值在右侧

可以发现第 $1,2$ 种是类似的，第 $3,4$ 种也是类似的，下面主要说明第 $1,3$ 种的求法。

情况 $1$：

枚举左端点 $l$。此时左半段 $[l,M]$ 的最小值、最大值位置已经确定，记为

$$u=posmn_L(l),\qquad v=posmx_L(l)$$

若整个区间合法，则必须满足 $u+v=l+r$，所以右端点只能是

$$r=u+v-l.$$

因此对每个 $l$ 只会产生一个候选 $r$。首先检查它是否满足 $M<r\le R$，保证区间确实跨过中点。接着还要保证加入右半段后，整个区间的最小值和最大值仍然来自左侧，即

$$mn_R(r)>mn_L(l),\qquad mx_R(r)<mx_L(l)$$

若这些条件全部成立，就找到一个合法区间。枚举所有左端点即可完整统计本情况，因为对称条件已经唯一确定了右端点。

情况 $2$

考虑最小值来自左侧、最大值来自右侧。需要

$$mn_L(l)<mn_R(r),\qquad mx_L(l)<mx_R(r)$$

且对称条件可以改写为

$$posmn_L(l)-l=r-posmx_R(r)$$

固定 $l$。因为 $mn_R(r)$ 随 $r$ 增大而不增，$mx_R(r)$ 随 $r$ 增大而不减，所以两个大小条件共同限制出一段连续的合法范围

$$lo(l)\le r\le hi(l).$$

也就是说我们只需要求出 $lo(l)$ 和 $hi(l)$ 中，有多少个 $r$ 满足 $r-posmx_R(r)= posmn_L(l)-l$ 即可，这一步可以利用二分求解，也可以利用滑动窗口：

当 $l$ 从 $M$ 向左移动时，$mn_L(l)$ 不增、$mx_L(l)$ 不减，$lo(l)$ 和 $hi(l)$ 都只会向右移动。维护当前右端点窗口，并统计窗口中每个值 $r-posmx_R(r)$ 出现了多少次，即可把当前贡献直接加上 $cnt[posmn_L(l)-l]$。

最大值来自左侧、最小值来自右侧时同理。

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