括号序列
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
有一个由 $n$ 个左括号 “(” 和 $n$ 个右括号 “)” 组成的序列。每次操作时可以选定两个数 $l, r$,然后把第 $l$ 到第 $r$ 个括号的顺序翻转(括号的朝向保持不变)。例如将 “()((()(” 翻转第 $3$ 到第 $7$ 个括号后的结果为 “()()(((”。
我希望使用不超过 $n$ 次操作,将这个序列变为一个合法的括号序列。
众所周知,合法括号序列的定义如下:
- () 是合法括号序列;
- 如果 A 是合法括号序列,则 (A) 是合法括号序列;
- 如果 A,B 是合法括号序列,则 AB 是合法括号序列。
自从来到 UOJ 这个宝地,我的视野变得开阔了,也见识了更多富有人类智慧的人士。我相信各位一定能给我更加满意的答案!
输入格式
一行一个长度为 $2n$ 的非空字符串表示初始序列。保证字符串只包含左括号和右括号,且左右括号的个数均为 $n$。
输出格式
对于给出的字符串,输出调整成合法的括号序列的方案。如果不存在这样的方案输出一行一个整数 $-1$。
否则,第一行一个整数 $m$ 表示要进行 $m$ 次翻转操作。
接下来 $m$ 行每行两个整数 $l, r$ 表示要翻转区间 $[l, r]$ 内的括号顺序。翻转操作会按你输出的顺序执行。
请保证 $m \leq n$ 以及 $1 \leq l \leq r \leq 2n$,否则会被判 $0$ 分。
如果有多组方案,输出任意一组即可。)))()(((
2
1 6
5 8
)))()(((
4
1 4
2 6
3 7
4 8
第一次操作后序列变为 “()()))((”。
第二次操作后序列变为 “()()(())”。
限制与约定
测试点编号 | $n$的规模 |
---|---|
1 | $n \leq 4$ |
2 | $n \leq 100$ |
3 | |
4 | |
5 | |
6 | $n \leq 100000$ |
7 | |
8 | |
9 | |
10 |
时间限制:$1\texttt{s}$
空间限制:$256\texttt{MB}$