SCP-S2025 题解

KingPowers · 2025-10-19 00:26:33 · 题解

题比去年没意思了很多，虽然去年我连 T2 都不会。

A

设原序列的前缀和数组为 s_i，显然选择区间的右端点一定是 n，如果左端点选择 l 则答案就是 [l,n] 里 s_{l-1} 的出现次数。只需要求一下前缀和数组里众数的出现次数即可，特殊处理 l=1，复杂度 O(Tn\log n)，瓶颈在于排序。

B

显然选的 k 个点深度都要相同，不然第一个点所在的深度不可能在交中。预处理每个点 u 子树内最深叶子的深度 f_u，然后枚举一下第一个点的深度，以及具体选了哪个点 u，简单讨论一下：

• 存在同深度的 v 满足 f_u=f_v 被选，则只需要随便从 f_v\ge f_u 的 v 中选择 k-1 个，保证选完后还剩下 f_v\ge f_u 的点即可。
• 否则剩下 k-1 个选的恰好是所有 f_v>f_u 的点，保证 f_v=f_u 的 v 至少还有一个即可。

具体方案数可以使用组合数和阶乘计算，容易做到 O(n\log n)。

C

设 f_i 表示最大的 j<i 满足 j 直达 i 的列车还能用，则显然 f_i 是单调不降的。

对于修改操作，相当于区间对 l-1 做 \text{chkmin}，由于 f_i 单调可以二分出区间内第一个 \ge l 的位置变成区间赋值。

对于查询操作，线段树二分找到最小的 i\ge r 满足 f_i\ge l，则答案为 \min(\min_{j=r}^{i-1}(p_j-p_{f_j}),p_i-p_l)，由于修改操作是区间赋值所以线段树也可以直接维护区间内 p_i-p_{f_i} 的最小值。

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

D

考虑对于固定局面设计一个形式简单的判定，然后将判定的过程写成 DP 计数。首先显然连续的相同段缩起来一定不劣，现在序列相邻两个位置都是不同的。

考虑继续调整，对于一对相邻的位置，用 \to 表示左边能赢右边，用 \gets 表示右边能赢左边。如果序列中存在 \to\gets 这种结构，也可以直接把这三个位置合并造出来一个平局。不断重复这个过程，最终序列的结构会是 \gets\gets\ldots\gets\to\ldots\to\to。设 \gets 和 \to 的数量分别为 x,y，则最终对答案额外产生的贡献为 \lfloor\frac{x}{3}\rfloor+\lfloor\frac{y}{3}\rfloor+[x\bmod 3=2\land y\bmod 3=2]。

这个判定过程可以简单地用一个栈来时限，具体来说从左往右扫用栈维护当前的箭头，加入 \gets 时如果栈顶是 \to 就和它消去，否则就压入栈顶，加入 \to 时直接压入栈顶即可。然后就容易直接对着 DP 了，设 f_{i,x,y,0/1/2} 表示当前扫到了 i，栈内 \gets 的数量为 x，\to 的数量为 y，最后一个元素是 0/1/2 的方案数，g_{i,x,y,0/1/2} 表示对应的答案，转移根据上面讨论进行即可。

当然现在的状态是 O(n^3) 的，但是由于栈内 \gets 的数量是不降的，所以 x 只需要记录 \bmod 3 的结果即可，复杂度降低到 O(n^2)。