巅峰赛#29 T6 题解
2026-01-09 21:37:44
发布于：浙江
25阅读
0回复
0点赞
因为一些神秘原因，需要写一下 T6 思路，后来考虑到既然都赛后复盘整理思路了（我平时打模拟赛从来不复盘的，显然这是一个坏习惯），不如水一篇题解。
容易发现这题其实是有原的：https://codeforces.com/problemset/problem/1239/B。
我两万年前打 Duel 的时候竟然还刷到过（），不过不幸的是当时对着题解看了好久没看懂。
先考虑什么是正规括号序列，比较容易想到的做法是栈，线性跑一遍即可，我记得这好像专门有一道题是干这个的，但是目前没找到/kel。但是这种方法在本题中显然是不可取的，不可能每次都要用栈跑一遍。考虑以 ( 为 ，) 为 所构建的前缀和数组 ，满足以下条件：
- 对于每一个 ，都有 。
- 。
其实很好证明，原理和栈实现是一样的。
很显然对于 ，必然无解，直接输出 0 1 1。
然后有一个比较常见的解决环上问题的方法就是破环为链，考虑将原数组复制两份。
然后考虑在一个序列中，怎么找到其合法切口数。其实就是由前缀和数组中最小的那个元素的决定的，读者可以自己思考一下为什么一定要在最小的那个元素位置上切开，才可以保证切割后的序列合法（主要还是满足上述条件第一条）。接下来易得合法切口数就是最小元素的出现次数。
然后是最难的部分也就是如何考虑交换这个东西。
我们要做的就是使得交换后的序列中出现尽可能多的最小值，我不知道这样子讲得详不详细，如果存在疑问可以指出。
通过注意力可以发现
后面的目前更不了，笔者被浮木线下单杀了，可以先暂时自行思考交换后对前缀和数组会有哪些影响。
有帮助，赞一个