309474: CF1685C. Bring Balance

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Bring Balance

题意翻译

### 题目描述 Alina 有一个长度为 $2n$ 的括号序列 $s$,由 $n$ 个左括号 `(` 和 $n$ 个右括号 `)` 组成。她想把这个括号序列变成一个平衡括号序列。 平衡括号序列定义为:能通过插入字符 `+` 和 `1` 使之成为合法数学表达式的序列。例如,序列 `(())()`、`()` 和 `(()(()))` 是平衡的,而 `)(`、`(()` 和 `(()))(` 就不是的。 在一次操作中,她可以反转 $s$ 的任意子串。 请求出最少几次操作可将 $s$ 转换为平衡括号序列。可以证明,这总是能在 $n$ 次操作中完成。 ### 输入格式 **本题单测试点有多组数据。** 第一行一个整数 $t$($1 \le t \le 2 \cdot 10^4$),表示数据组数。 每组数据格式如下: - 第一行一个整数 $n$($1 \le n \le 10^5$),含义如上所述。 - 第二行为一个长度为 $2n$ 的括号序列,由 $n$ 个左括号 `(` 和 $n$ 个右括号 `)` 组成。 在一个测试点中,所有 $n$ 的总和不超过 $2\cdot 10^5$。 ### 输出格式 对于每一组数据,第一行输出一个整数 $k$($0 \le k \le n$),表示最少 $k$ 次操作可将 $s$ 转换为平衡括号序列。 在接下来的 $k$ 行中,第 $i$ 行有两个整数 $l_i,r_i$($1 \le l_i \le r_i \le 2n$),表示在第 $i$ 次操作中,Alina 会反转子串 $s_{l}s_{l+1}\cdots s_{r-1}s_{r}$(序列从 $1$ 开始编号)。 如果有多种方式将原序列转换为平衡序列,输出其中任意一种即可。 ### 说明/提示 在第一组数据中,字符串已经平衡。 在第二组数据中,字符串转换如下:`())((()))(`$\to$`()()(()))(`$\to$`()()(())()`,最后一个字符串是平衡的。 在第三组数据中,字符串最终将被转换为 `((()))((()))`。

题目描述

Alina has a bracket sequence $ s $ of length $ 2n $ , consisting of $ n $ opening brackets '(' and $ n $ closing brackets ')'. As she likes balance, she wants to turn this bracket sequence into a balanced bracket sequence. In one operation, she can reverse any substring of $ s $ . What's the smallest number of operations that she needs to turn $ s $ into a balanced bracket sequence? It can be shown that it's always possible in at most $ n $ operations. As a reminder, a sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters + and 1. For example, sequences (())(), (), and (()(())) are balanced, while )(, ((), and (()))( are not.

输入输出格式

输入格式


The first line of the input contains a single integer $ t $ ( $ 1 \le t \le 2 \cdot 10^4 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ). The second line of each test case contains a string $ s $ of length $ 2n $ , consisting of $ n $ opening and $ n $ closing brackets. The sum of $ n $ over all test cases doesn't exceed $ 2\cdot 10^5 $ .

输出格式


For each test case, in the first line output a single integer $ k $ $ (0 \le k \le n) $ — the smallest number of operations required. The $ i $ -th of the next $ k $ lines should contain two integers $ l_i, r_i $ ( $ 1 \le l_i \le r_i \le 2n $ ), indicating that in the $ i $ -th operation, Alina will reverse the substring $ s_ls_{l+1} \ldots s_{r-1}s_r $ . Here the numeration starts from $ 1 $ . If there are multiple sequences of operations with the smallest length which transform the sequence into a balanced one, you can output any of them.

输入输出样例

输入样例 #1

3
2
(())
5
())((()))(
6
())((()))(()

输出样例 #1

0
2
3 4
9 10
1
2 11

说明

In the first test case, the string is already balanced. In the second test case, the string will be transformed as follows: ())((()))( $ \to $ ()()(()))( $ \to $ ()()(())(), where the last string is balanced. In the third test case, the string will be transformed to ((()))((())), which is balanced.

Input

题意翻译

### 题目描述 Alina 有一个长度为 $2n$ 的括号序列 $s$,由 $n$ 个左括号 `(` 和 $n$ 个右括号 `)` 组成。她想把这个括号序列变成一个平衡括号序列。 平衡括号序列定义为:能通过插入字符 `+` 和 `1` 使之成为合法数学表达式的序列。例如,序列 `(())()`、`()` 和 `(()(()))` 是平衡的,而 `)(`、`(()` 和 `(()))(` 就不是的。 在一次操作中,她可以反转 $s$ 的任意子串。 请求出最少几次操作可将 $s$ 转换为平衡括号序列。可以证明,这总是能在 $n$ 次操作中完成。 ### 输入格式 **本题单测试点有多组数据。** 第一行一个整数 $t$($1 \le t \le 2 \cdot 10^4$),表示数据组数。 每组数据格式如下: - 第一行一个整数 $n$($1 \le n \le 10^5$),含义如上所述。 - 第二行为一个长度为 $2n$ 的括号序列,由 $n$ 个左括号 `(` 和 $n$ 个右括号 `)` 组成。 在一个测试点中,所有 $n$ 的总和不超过 $2\cdot 10^5$。 ### 输出格式 对于每一组数据,第一行输出一个整数 $k$($0 \le k \le n$),表示最少 $k$ 次操作可将 $s$ 转换为平衡括号序列。 在接下来的 $k$ 行中,第 $i$ 行有两个整数 $l_i,r_i$($1 \le l_i \le r_i \le 2n$),表示在第 $i$ 次操作中,Alina 会反转子串 $s_{l}s_{l+1}\cdots s_{r-1}s_{r}$(序列从 $1$ 开始编号)。 如果有多种方式将原序列转换为平衡序列,输出其中任意一种即可。 ### 说明/提示 在第一组数据中,字符串已经平衡。 在第二组数据中,字符串转换如下:`())((()))(`$\to$`()()(()))(`$\to$`()()(())()`,最后一个字符串是平衡的。 在第三组数据中,字符串最终将被转换为 `((()))((()))`。

Output

**题目大意:**
Alina有一个长度为$2n$的括号序列$s$,由$n$个左括号`(`和$n$个右括号`)`组成。她希望通过反转序列的任意子串,使得序列变成一个平衡括号序列。平衡括号序列是指可以通过插入字符`+`和`1`使之成为合法数学表达式的序列。要求出最少需要进行多少次操作才能将$s$转换为平衡括号序列。可以证明,这总是能在$n$次操作中完成。

**输入格式:**
- 第一行一个整数$t$($1 \le t \le 2 \cdot 10^4$),表示数据组数。
- 每组数据包含两行:
- 第一行一个整数$n$($1 \le n \le 10^5$),表示括号序列的长度的一半。
- 第二行为一个长度为$2n$的括号序列,由$n$个左括号和$n$个右括号组成。

**输出格式:**
- 对于每组数据,第一行输出一个整数$k$($0 \le k \le n$),表示最少$k$次操作可将$s$转换为平衡括号序列。
- 接下来的$k$行中,每行两个整数$l_i,r_i$($1 \le l_i \le r_i \le 2n$),表示在第$i$次操作中,Alina会反转子串$s_{l}s_{l+1}\cdots s_{r-1}s_{r}$。

**样例输入输出:**
- 输入样例:
```
3
2
(())
5
())((()))(
6
())((()))(())
```
- 输出样例:
```
0
2
3 4
9 10
1
2 11
```
- 说明:在第一组数据中,字符串已经平衡。在第二组数据中,字符串转换如下:`())((()))(` $\to$ `()()(()))(` $\to$ `()()(())()`,最后一个字符串是平衡的。在第三组数据中,字符串最终将被转换为`((()))((()))`。**题目大意:** Alina有一个长度为$2n$的括号序列$s$,由$n$个左括号`(`和$n$个右括号`)`组成。她希望通过反转序列的任意子串,使得序列变成一个平衡括号序列。平衡括号序列是指可以通过插入字符`+`和`1`使之成为合法数学表达式的序列。要求出最少需要进行多少次操作才能将$s$转换为平衡括号序列。可以证明,这总是能在$n$次操作中完成。 **输入格式:** - 第一行一个整数$t$($1 \le t \le 2 \cdot 10^4$),表示数据组数。 - 每组数据包含两行: - 第一行一个整数$n$($1 \le n \le 10^5$),表示括号序列的长度的一半。 - 第二行为一个长度为$2n$的括号序列,由$n$个左括号和$n$个右括号组成。 **输出格式:** - 对于每组数据,第一行输出一个整数$k$($0 \le k \le n$),表示最少$k$次操作可将$s$转换为平衡括号序列。 - 接下来的$k$行中,每行两个整数$l_i,r_i$($1 \le l_i \le r_i \le 2n$),表示在第$i$次操作中,Alina会反转子串$s_{l}s_{l+1}\cdots s_{r-1}s_{r}$。 **样例输入输出:** - 输入样例: ``` 3 2 (()) 5 ())((()))( 6 ())((()))(()) ``` - 输出样例: ``` 0 2 3 4 9 10 1 2 11 ``` - 说明:在第一组数据中,字符串已经平衡。在第二组数据中,字符串转换如下:`())((()))(` $\to$ `()()(()))(` $\to$ `()()(())()`,最后一个字符串是平衡的。在第三组数据中,字符串最终将被转换为`((()))((()))`。

加入题单

上一题 下一题 算法标签: