题目详情题解（0）讨论（0）提交记录（0）

AT_s8pc_5_c.Two Parentheses

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

E869120 和 square1001 各自拥有一串等长的“正确括号序列”。所谓“正确括号序列”是指符合下列条件的字符串：

  • () 是一个正确的括号序列。
  • 如果 XX 是一个正确的括号序列，那么 (、XX 和 ) 连接在一起也是一个正确的括号序列。
  • 如果 XX 和 YY 都是正确的括号序列，那么 XX 和 YY 相连也是一个正确的括号序列。
  • 其他任何括号序列都是不正确的。

设 E869120 的括号序列为 AA，square1001 的括号序列为 BB。chokudai 对 AA 和 BB 进行了以下操作：

  • 将 BB 中的每个 ( 替换为 )，每个 ) 替换为 (。然后，定义一个初始为空的字符串 CC，并交替进行以下两种操作，直到 AA 和 BB 均为空：
    • 把 AA 的首字符移至 CC 的末尾，并删除 AA 的首字符。
    • 把 BB 的首字符移至 CC 的末尾，并删除 BB 的首字符。

给定字符串 SS，判断是否可能通过上述操作使得 S=CS = C。如果可以，输出 Yes；否则输出 No。

输入格式

输入通过标准输入给出。你需要回答 QQ 个问题。第 ii 个问题的字符串为 SiS_i。

第一行输入整数 QQ，表示问题的数量。
接下来的 QQ 行，每行一个字符串 S1,S2,…,SQS_1, S_2, \ldots, S_Q。

输出格式

输出 QQ 行。对于每个字符串 SiS_i，如果存在以 S=CS = C 的情况，输出 Yes，否则输出 No。

输入输出样例

  • 输入#1

    4
(())
)()(
(())
)(()

    输出#1

    No
Yes
No
Yes

  • 输入#2

    1
(())(()(

    输出#2

    No

  • 输入#3

    11
))(((()()())
))((())(())(
()())))(()((
)(()())()()(
)(())())(()(
)(()))()((()
)()()()())((
(())(()())()
)(())(()())(
((()())(()))
)))()())()()

    输出#3

    Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No

说明/提示

约束

  • QQ 是 11 到 5050 之间的整数。
  • SiS_i 是一个长度在 11 到 20 00020\ 000 之间，仅由 ( 和 ) 构成的字符串。
  • SiS_i 的长度必为 44 的倍数。

子任务

子任务 1 [9090 分]

  • ∣S∣≤16|S| \leq 16。

子任务 2 [100100 分]

  • ∣S∣≤50|S| \leq 50。

子任务 3 [310310 分]

  • 无额外约束。

样例解释

例如，在第二个问题中，S2S_2 = )()(。我们可以选择 AA = "()", BB = ")("。按顺序将字符插入 CC 后，可以得到 $C = $ )()(。变化过程如下：

  • 初始：AA = "()", BB = ")(", CC = ""
  • 第一步：AA = "()", BB = "(", CC = ")"
  • 第二步：AA = ")", BB = "(", CC = ")("
  • 第三步：AA = "", BB = "(", CC = ")()"
  • 第四步：AA = "", BB = "", CC = ")()("

在这个过程中，每步都选择从 AA 或 BB 中取字符加入 CC 末尾。通过合适的选择，我们得以构造出与 S2S_2 相同的序列。

而对于某个问题，如果 ( 和 ) 的数量不相等，比如 ( 出现 55 次，) 只出现 33 次，那么根据括号序列相等原则，根本无法达成 S=CS = C 的条件。

本翻译由 AI 自动生成

输入解题思路，AI测评打分。不知道怎么写?

首页