← 返回题目列表

AtCoder · s8pc_5_c

C. 两个括号

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

配点: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