文章目录
  1. 1. 输入格式
  2. 2. 输出格式
  3. 3. 样例一
    1. 3.1. input
    2. 3.2. output
    3. 3.3. explanation
  4. 4. 限制与约定
  5. 5. Codes

大家好我是来自百度贴吧的_叫我猪猪侠,英文名叫_CallMeGGBond。

我不曾上过大学,但这不影响我对离散数学、复杂性分析等领域的兴趣;尤其是括号序列理论,一度令我沉浸其中,无法自拔。至于OI算法竞赛,我年轻时确有参加,虽仅获一枚铜牌,但我素性淡泊,毫不在意,毕竟那所谓FFT、仙人掌之类,只是些雕虫小技罢了,登不上大雅之堂的;只有括号序列才会真正激发我的研究热情。

我曾天真地以为,凭借我的学识与才能,足可以在这世间安身立命;然而直到沦落街头后,我终才领悟现实的残酷。迫于生计,我只得转向道德与哲学的研究;但我与括号序列之间情愫依旧,难以剪断。

理性的传播总是不顺的,研究的道路也是曲折的,但轻易放弃决不是我的风格;为了继续实现自己的理想,现在我向大家提出一道括号序列的超级大难题。

有一个由 $n$ 个左括号 “(” 和 $n$ 个右括号 “)” 组成的序列。每次操作时可以选定两个数 $l, r$,然后把第 $l$ 到第 $r$ 个括号的顺序翻转(括号的朝向保持不变)。例如将 “()((()(” 翻转第 $3$ 到第 $7$ 个括号后的结果为 “()()(((”。

我希望使用不超过 $n$ 次操作,将这个序列变为一个合法的括号序列。

众所周知,合法括号序列的定义如下:

  1. () 是合法括号序列;
  2. 如果 A 是合法括号序列,则 (A) 是合法括号序列;
  3. 如果 AB 是合法括号序列,则 AB 是合法括号序列。

自从来到 UOJ 这个宝地,我的视野变得开阔了,也见识了更多富有人类智慧的人士。我相信各位一定能给我更加满意的答案!

输入格式

一行一个长度为 $2n$ 的非空字符串表示初始序列。保证字符串只包含左括号和右括号,且左右括号的个数均为 $n$。

输出格式

对于给出的字符串,输出调整成合法的括号序列的方案。如果不存在这样的方案输出一行一个整数 $-1$。

否则,第一行一个整数 $m$ 表示要进行 $m$ 次翻转操作。

接下来 $m$ 行每行两个整数 $l, r$ 表示要翻转区间 $[l, r]$ 内的括号顺序。翻转操作会按你输出的顺序执行。

请保证 $m \leq n$ 以及 $1 \leq l \leq r \leq 2n$,否则会被判 $0$ 分。

如果有多组方案,输出任意一组即可。

样例一

input



)))()(((



output



2
1 6
5 8



explanation

第一次操作后序列变为 “()()))((”。

第二次操作后序列变为 “()()(())”。

限制与约定

测试点编号 $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}$

Codes

题解见

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn= 100010;
char str[maxn+maxn];
int len, cnt=0, ans=0;
vector<int> list1;
vector<int> list2;
int main()
{
scanf("%s", str);
len= strlen(str);
int j=0;
for(int i=0; i<len; i++)
{
j=max(j, i+1);
if(str[i]=='(')
cnt++;
else if(cnt>0)
cnt--;
else
{
for(; j<len && str[j]==')'; j++);
str[i]='(';
str[j]=')';
list1.push_back(i);
list2.push_back(j);
cnt++;
ans++;
j++;
}
}
printf("%d\n", ans);
for(int i=0; i<list1.size(); i++)
printf("%d %d\n", list1[i]+1, list2[i]+1);
return 0;
}

文章目录
  1. 1. 输入格式
  2. 2. 输出格式
  3. 3. 样例一
    1. 3.1. input
    2. 3.2. output
    3. 3.3. explanation
  4. 4. 限制与约定
  5. 5. Codes