← 返回题目列表

AtCoder · utpc2022_i

I. 哪些必须删除?

中文机器翻译题面 查看原题

配点 : 100 点

問題文

(, ) 仅由括号组成的字符串,如果符合以下任意一项,则称为“正确的括号序列”。

  • 空文字列
  • 某个“正确的括号序列”A 存在 (, A, ) 按此顺序连起来的字符串
  • 某个非空的“正确的括号序列”A,\ B 存在 A,\ B 按此顺序连起来的字符串

长度 小于或等于 4N 在 (, ) 仅由组成的字符串 S 和 按字典顺序比较 2N 的 您可以创建一个包含 2 整数集 当与 (L_i, R_i)\ (1\leq L_i < R_i \leq 4N) 。在这里,(L_1,L_2,\dots,L_{2N}) 是 您也可以写 (1,2,\dots,2N) 的 与(R_1,R_2,\dots,R_{2N}) 是 您也可以写 (2N+1,2N+2,\dots,4N) 的排列。 在

i=1, 2,\dots,2N 按顺序 S 可以得到第 L_i,\ R_i 个字符中的任意位置标记后,仅从左到右读取标记的字符,并作为长度为 2N 的字符串进行解释, 判断是否可以将 S' 。

S' 变为“正确的括号序列”。

T 测试用例。

制約

  • 输入的数值全部为整数。 如果
  • 1 \leq T \leq 1000
  • 1 \leq N \leq 2000
  • S 是 您也可以写 (, ) 组成的长度 4N 的字符串所需的时间.在这次比赛中,参赛者按照以下条件进行打字.
  • 1 \leq L_i \leq 2N < R_i \leq 4N
  • (L_1,L_2,\dots,L_{2N}) 是 您也可以写 (1,2,\dots,2N) 的排列 给出了
  • (R_1,R_2,\dots,R_{2N}) 是 您也可以写 (2N+1,2N+2,\dots,4N) 的排列 给出了
  • 1 对于一个输入中包含的测试用例, N 的总和是 2000 以下

入力

输入是按以下格式从标准输入给出的。

T
\mathrm{case}_1
\vdots
\mathrm{case}_T

每个案例均按以下格式给出。 打印

N
S
L_1 R_1
L_2 R_2
\vdots
L_{2N} R_{2N}

出力

T 行。 i\ (1\leq i \leq T) 在线 i 个测试用例,S' 可以变为“正确的括号序列”, 则在 Yes ,如果不能的话 No 。


入力例 1

3
1
()()
1 3
2 4
2
))()((()
1 6
2 5
3 7
4 8
8
))()))))()())((((()))(()(()))(((
8 26
2 25
1 18
4 22
7 17
12 32
10 31
5 30
15 27
9 23
13 19
11 24
14 29
6 28
16 20
3 21

出力例 1

Yes
No
Yes

1 个测试用例, L_1=1 信和 将其重写为 R_2=4 个字符上标记后, 将变为 S' 是 您也可以写 () ,这是“正确的括号序列”。 关于第

2 个测试用例,无论如何标记, S' 都无法成为“正确的括号序列”。 以