配点:500 点
字符串 A 和 B 应该具有相同的长度,但在问题描述中没有提到。对于由此带来的不便,我们深表歉意。
问题陈述
E869120 和 square1001 的括号序列是正确的且长度相同。“正确的括号序列”定义如下:
()是正确的括号序列。- If X 是正确的括号序列,串联
(, X,)这个顺序也是正确的括号顺序。 - If X 和 Y 是正确的括号序列,串联 X 和 Y 这个顺序也是正确的括号顺序。
- 每个正确的括号序列都可以从上述规则中推导出来。
将 E869120 的括号序列表示为 A,将 square1001 的括号序列表示为 B。chokudai 执行了以下操作,从 A 和 B.
请注意 A 和 B 应该具有相等的长度。
- 对于 B的每个字符,
(,他将其改为)。如果是的话),他将其改为(。在此操作之后,他定义了一个空字符串 C,并在 A or B 非空字符串时执行下面两种操作之一。 - 将 A 的第一个字符插入字符串 C的末尾。之后,删除 A.
- 将 B 的第一个字符插入字符串 C的末尾。之后,删除 B.
给你一个字符串 S的第一个字符。请检查是否可能 S=C 或者不是。
输入
输入由标准输入按以下格式给出。 注意:你应该回答 Q 查询。字符串 S in i-第一个查询是 S_i.
Q S_1 S_2 : S_Q
输出
打印 Q 行。
In i第行,打印 Yes 如果可能的话 S_i = C,并打印 No 如果不可能的话 S_i = C.
约束
- 1 \leq Q \leq 50
- 1 \leq |S_i| \leq 20 \ 000
- S_i 包括
(和) - 的长度 S_i 可以被4整除。
子任务
子任务 1 [90 点]
- |S| \leq 16.
子任务 2 [100 点]
- |S| \leq 50.
子任务 3 [310 点]
- 没有其他限制。
示例输入 1
4 (()) )()( (()) )(()
示例输出 1
No Yes No Yes
在第二个查询中,如果 A 是 "()",B = "()" 并且 chokudai 按顺序执行操作 BAAB, C 应该是 )()(。
在这种情况下, A, B, C 更改如下:
- A = "()", B = ")(", C = ""(在 chokudai 翻转每个字符之后 B)
- A = "()", B = "(", C = ")"
- A = ")", B = "(", C = ")("
- A = "", B = "(", C = ")()"
- A = "", B = "", C = ")()("
示例输入 2
1 (())(()(
示例输出 2
No
在这种情况下,有 5 (和 3 )s。因为字符数量 ( 和字符数量 ) 对于所有正确的括号序列是相同的,它不可能是 S=C.
示例输入 3
11 ))(((()()()) ))((())(())( ()())))(()(( )(()())()()( )(())())(()( )(()))()((() )()()()())(( (())(()())() )(())(()())( ((()())(())) )))()())()()
示例输出 3
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No