2026.10.26 衡中集训

CSP-S 模拟赛

A. pair

set 板子题，复杂度 O(log n)。

我们发现未配对的最小一人只会向大了推，用一个指针维护只会更新 O(n) 次，这样复杂度 O(n)。

B. peak

枚举最高点。在最高点之前，? 要都填 +；在最高点之后，? 要都填 -。场上这点没想清。

这样可能的问题是，+ 会把值顶破上限高度。会这样吗？不会。因为 + 不但加了中间部分，还加了枚举的最高点。都加相当于都不加。

处理出 ? 都填 + 的高度，然后做后缀 max。我们只在乎高度的差值，所以 ? 的分配情况只要是统一的就可以。浅浅推式子可以得到正解做法。

C. score

f_idx,i 为第 idx 位，甲 - 乙的分数是 i 的方案数。f_{i,j} = f_{i-1,j} + 1 (s_i = 1) ，f_{i,j} = f_{i-1,j-1} (s_i = 0 and j <= 2)，f_{i,1} += f_{i,3} , f_{i,3} = 0 (s_i = 0)。

O(n) 的转移是不可接受的，一个常见的 trick 是维护偏移量 D。这样那几个 O(n) 转移的就是 O(1) 的了。

D. door

显然正解是困难的。记录一下场上写的部分分。

装压做 M<=18，即 M/2 <= 9。

以 1 为根，2 和 3 向上跳链直到父亲。标记路径上的边。取符合集合关系的权值最小边即可。