2026.10.27 衡中集训

CSP-S 模拟赛

这两场模拟赛真的是 CSP-S 难度吗？为什么我能打这么多分。信心场来的。

A. del

很容易注意到要删除第一个下降位置的前一位。证明也很容易：如果不删，转而删其他位置，这个位置一定会限制其不优。

B. inv

考虑如何在顺序过程中找到描述连通分量的方式。新的小元素会弹出旧的大元素，在单调栈中存已知连通分量的最大节点。每弹出一次，连通分量的数量就少一个。

C. bracket

设 dp_i 为权值为 i 的最小代价。容易想到转移。

复杂度为 O(n^2len) 的。其中 len 为字符串长度。打表发现 len 最大不超过 40。