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


























有帮助,赞一个