配点 : 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' 都无法成为“正确的括号序列”。 以