CF2110B Down with Brackets
题目描述
在 2077 年,机器人决定一劳永逸地摆脱平衡括号序列!
一个括号序列被称为**平衡的**,如果它可以通过以下形式文法构造:
1. 空序列 $\varnothing$ 是平衡的。
2. 如果括号序列 $A$ 是平衡的,那么 $\mathtt{(}A\mathtt{)}$ 也是平衡的。
3. 如果括号序列 $A$ 和 $B$ 是平衡的,那么拼接序列 $A B$ 也是平衡的。
你是对抗平衡括号序列部门的负责人,你的主要任务是确定哪些括号可以被销毁,哪些不能。
给定一个由字符串 $s$ 表示的平衡括号序列,仅包含字符 `(` 和 `)`。由于机器人的能力有限,它们只能从字符串中**恰好删除一个左括号和一个右括号**。
你的任务是判断机器人是否能删除这样两个括号,使得字符串 $s$ **不再**是一个平衡括号序列。
输入格式
每个测试包含多个测试用例。第一行包含测试用例的数量 $t$($1 \le t \le 10^4$)。接下来是每个测试用例的描述。
每个测试用例由一个字符串 $s$($2 \leq |s| \leq 2 \cdot 10^5$)组成——仅由 `(` 和 `)` 构成的序列。
保证 $s$ 是一个平衡括号序列。
同时保证所有测试用例的 $|s|$ 之和不超过 $2 \cdot 10^5$。
输出格式
对于每个测试用例,如果机器人可以使字符串不再是平衡括号序列,输出 "YES";否则输出 "NO"。
输出字母大小写不敏感(如 "yEs"、"yes"、"Yes" 或 "YES" 均被视为肯定答案)。
说明/提示
在第一个测试用例中,可以证明机器人无法破坏正确的括号序列。
在第二个测试用例中,一种可行的括号删除方式如下:
$\texttt{(())}{\color{red}\texttt{(}}\texttt{)(}{\color{red}\texttt{)}} \rightarrow \texttt{(()))(}$,结果不是一个正确的括号序列。
在第四个测试用例中,一种可行的删除方式如下:
$\texttt{(}{\color{red}\texttt{(}}\texttt{))((}{\color{red}\texttt{)}}\texttt{)}\rightarrow \texttt{())(()}$,结果不是一个正确的括号序列。
翻译由 DeepSeek V3 完成