309628: CF1709C. Recover an RBS
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Recover an RBS
题意翻译
有个**合法括号序列**，部分字符被 `?` 替换了，问是否存在**唯一的一种**填 `?` 的方案，使得括号序列合法，即判断填 `?` 使得括号序列合法的方案数**是否等于1**。存在唯一方案输出 `YES`，方案不唯一输出 `NO` 序列长度 $\sum n\le 2\times 10^5$，测试点数 $T\leq 5\times 10^4$ 第一行输出测试点总数 $T$。 之后每一行一个字符串 $s$ 表示替换掉部分字符后的**合法括号序列**。题目描述
A bracket sequence is a string containing only characters "(" and ")". A regular bracket sequence (or, shortly, an RBS) is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence. For example: - bracket sequences "()()" and "(())" are regular (the resulting expressions are: "(1)+(1)" and "((1+1)+1)"); - bracket sequences ")(", "(" and ")" are not. There was an RBS. Some brackets have been replaced with question marks. Is it true that there is a unique way to replace question marks with brackets, so that the resulting sequence is an RBS?输入输出格式
输入格式
The first line contains a single integer $ t $ ( $ 1 \le t \le 5 \cdot 10^4 $ ) — the number of testcases. The only line of each testcase contains an RBS with some brackets replaced with question marks. Each character is either '(', ')' or '?'. At least one RBS can be recovered from the given sequence. The total length of the sequences over all testcases doesn't exceed $ 2 \cdot 10^5 $ .
输出格式
For each testcase, print "YES" if the way to replace question marks with brackets, so that the resulting sequence is an RBS, is unique. If there is more than one way, then print "NO".
输入输出样例
输入样例 #1
5
(?))
??????
()
??
?(?)()?)输出样例 #1
YES
NO
YES
YES
NO说明
In the first testcase, the only possible original RBS is "(())". In the second testcase, there are multiple ways to recover an RBS. In the third and the fourth testcases, the only possible original RBS is "()". In the fifth testcase, the original RBS can be either "((()()))" or "(())()()".Input
题意翻译
有个**合法括号序列**，部分字符被 `?` 替换了，问是否存在**唯一的一种**填 `?` 的方案，使得括号序列合法，即判断填 `?` 使得括号序列合法的方案数**是否等于1**。存在唯一方案输出 `YES`，方案不唯一输出 `NO` 序列长度 $\sum n\le 2\times 10^5$，测试点数 $T\leq 5\times 10^4$ 第一行输出测试点总数 $T$。 之后每一行一个字符串 $s$ 表示替换掉部分字符后的**合法括号序列**。Output
**恢复一个RBS**
**题意翻译**
给出一个**合法的括号序列**，其中部分字符被 `?` 替换。需要判断是否存在**唯一一种**方式填充 `?`，使得括号序列合法。如果存在唯一合法方案，则输出 `YES`；如果存在多种或没有合法方案，则输出 `NO`。序列的总长度 $\sum n \le 2 \times 10^5$，测试点的数量 $T \leq 5 \times 10^4$。
输入第一行包含测试点的总数 $T$。
接下来每一行包含一个字符串 $s$，表示被部分字符替换后的**合法括号序列**。
**题目描述**
一个括号序列是一个只包含字符 "(" 和 ")" 的字符串。一个规则的括号序列（简称 RBS）是一个括号序列，通过在原序列的字符之间插入字符 "1" 和 "+" 可以转换成一个正确的算术表达式。例如：
- 括号序列 "()" 和 "(())" 是规则的（对应的表达式是："(1)+(1)" 和 "((1+1)+1)"）；
- 括号序列 ")("、"(" 和 ")" 不是规则的。
现在有一个 RBS，其中一些括号被问号 "?" 替换了。问题是，是否只有一种方式替换问号为括号，使得结果序列是一个 RBS。
**输入输出格式**
**输入格式**
第一行包含一个整数 $ t $ （$ 1 \le t \le 5 \cdot 10^4 $）——测试案例的数量。
每个测试案例在一行中包含一个带有一些括号被问号 "?" 替换的 RBS。每个字符要么是 '('，要么是 ')'，要么是 '?'。至少可以从给定的序列恢复一个 RBS。
所有测试案例的序列总长度不超过 $ 2 \cdot 10^5 $。
**输出格式**
对于每个测试案例，如果替换问号为括号的方式使得结果序列是一个 RBS 的方案唯一，则输出 "YES"。如果存在多种方式，则输出 "NO"。
**输入输出样例**
**输入样例 #1**
```
5
(?))
??????
()
??
?(?)()?)
```
**输出样例 #1**
```
YES
NO
YES
YES
NO
```
**说明**
第一个测试案例中，唯一可能的原始 RBS 是 "(())"。
第二个测试案例中，存在多种方式恢复一个 RBS。
第三和第四个测试案例中，唯一可能的原始 RBS 是 "()"。
第五个测试案例中，原始 RBS 要么是 "((()()))"，要么是 "(())()()"。**恢复一个RBS** **题意翻译** 给出一个**合法的括号序列**，其中部分字符被 `?` 替换。需要判断是否存在**唯一一种**方式填充 `?`，使得括号序列合法。如果存在唯一合法方案，则输出 `YES`；如果存在多种或没有合法方案，则输出 `NO`。序列的总长度 $\sum n \le 2 \times 10^5$，测试点的数量 $T \leq 5 \times 10^4$。 输入第一行包含测试点的总数 $T$。 接下来每一行包含一个字符串 $s$，表示被部分字符替换后的**合法括号序列**。 **题目描述** 一个括号序列是一个只包含字符 "(" 和 ")" 的字符串。一个规则的括号序列（简称 RBS）是一个括号序列，通过在原序列的字符之间插入字符 "1" 和 "+" 可以转换成一个正确的算术表达式。例如： - 括号序列 "()" 和 "(())" 是规则的（对应的表达式是："(1)+(1)" 和 "((1+1)+1)"）； - 括号序列 ")("、"(" 和 ")" 不是规则的。 现在有一个 RBS，其中一些括号被问号 "?" 替换了。问题是，是否只有一种方式替换问号为括号，使得结果序列是一个 RBS。 **输入输出格式** **输入格式** 第一行包含一个整数 $ t $ （$ 1 \le t \le 5 \cdot 10^4 $）——测试案例的数量。 每个测试案例在一行中包含一个带有一些括号被问号 "?" 替换的 RBS。每个字符要么是 '('，要么是 ')'，要么是 '?'。至少可以从给定的序列恢复一个 RBS。 所有测试案例的序列总长度不超过 $ 2 \cdot 10^5 $。 **输出格式** 对于每个测试案例，如果替换问号为括号的方式使得结果序列是一个 RBS 的方案唯一，则输出 "YES"。如果存在多种方式，则输出 "NO"。 **输入输出样例** **输入样例 #1** ``` 5 (?)) ?????? () ?? ?(?)()?) ``` **输出样例 #1** ``` YES NO YES YES NO ``` **说明** 第一个测试案例中，唯一可能的原始 RBS 是 "(())"。 第二个测试案例中，存在多种方式恢复一个 RBS。 第三和第四个测试案例中，唯一可能的原始 RBS 是 "()"。 第五个测试案例中，原始 RBS 要么是 "((()()))"，要么是 "(())()()"。
**题意翻译**
给出一个**合法的括号序列**，其中部分字符被 `?` 替换。需要判断是否存在**唯一一种**方式填充 `?`，使得括号序列合法。如果存在唯一合法方案，则输出 `YES`；如果存在多种或没有合法方案，则输出 `NO`。序列的总长度 $\sum n \le 2 \times 10^5$，测试点的数量 $T \leq 5 \times 10^4$。
输入第一行包含测试点的总数 $T$。
接下来每一行包含一个字符串 $s$，表示被部分字符替换后的**合法括号序列**。
**题目描述**
一个括号序列是一个只包含字符 "(" 和 ")" 的字符串。一个规则的括号序列（简称 RBS）是一个括号序列，通过在原序列的字符之间插入字符 "1" 和 "+" 可以转换成一个正确的算术表达式。例如：
- 括号序列 "()" 和 "(())" 是规则的（对应的表达式是："(1)+(1)" 和 "((1+1)+1)"）；
- 括号序列 ")("、"(" 和 ")" 不是规则的。
现在有一个 RBS，其中一些括号被问号 "?" 替换了。问题是，是否只有一种方式替换问号为括号，使得结果序列是一个 RBS。
**输入输出格式**
**输入格式**
第一行包含一个整数 $ t $ （$ 1 \le t \le 5 \cdot 10^4 $）——测试案例的数量。
每个测试案例在一行中包含一个带有一些括号被问号 "?" 替换的 RBS。每个字符要么是 '('，要么是 ')'，要么是 '?'。至少可以从给定的序列恢复一个 RBS。
所有测试案例的序列总长度不超过 $ 2 \cdot 10^5 $。
**输出格式**
对于每个测试案例，如果替换问号为括号的方式使得结果序列是一个 RBS 的方案唯一，则输出 "YES"。如果存在多种方式，则输出 "NO"。
**输入输出样例**
**输入样例 #1**
```
5
(?))
??????
()
??
?(?)()?)
```
**输出样例 #1**
```
YES
NO
YES
YES
NO
```
**说明**
第一个测试案例中，唯一可能的原始 RBS 是 "(())"。
第二个测试案例中，存在多种方式恢复一个 RBS。
第三和第四个测试案例中，唯一可能的原始 RBS 是 "()"。
第五个测试案例中，原始 RBS 要么是 "((()()))"，要么是 "(())()()"。**恢复一个RBS** **题意翻译** 给出一个**合法的括号序列**，其中部分字符被 `?` 替换。需要判断是否存在**唯一一种**方式填充 `?`，使得括号序列合法。如果存在唯一合法方案，则输出 `YES`；如果存在多种或没有合法方案，则输出 `NO`。序列的总长度 $\sum n \le 2 \times 10^5$，测试点的数量 $T \leq 5 \times 10^4$。 输入第一行包含测试点的总数 $T$。 接下来每一行包含一个字符串 $s$，表示被部分字符替换后的**合法括号序列**。 **题目描述** 一个括号序列是一个只包含字符 "(" 和 ")" 的字符串。一个规则的括号序列（简称 RBS）是一个括号序列，通过在原序列的字符之间插入字符 "1" 和 "+" 可以转换成一个正确的算术表达式。例如： - 括号序列 "()" 和 "(())" 是规则的（对应的表达式是："(1)+(1)" 和 "((1+1)+1)"）； - 括号序列 ")("、"(" 和 ")" 不是规则的。 现在有一个 RBS，其中一些括号被问号 "?" 替换了。问题是，是否只有一种方式替换问号为括号，使得结果序列是一个 RBS。 **输入输出格式** **输入格式** 第一行包含一个整数 $ t $ （$ 1 \le t \le 5 \cdot 10^4 $）——测试案例的数量。 每个测试案例在一行中包含一个带有一些括号被问号 "?" 替换的 RBS。每个字符要么是 '('，要么是 ')'，要么是 '?'。至少可以从给定的序列恢复一个 RBS。 所有测试案例的序列总长度不超过 $ 2 \cdot 10^5 $。 **输出格式** 对于每个测试案例，如果替换问号为括号的方式使得结果序列是一个 RBS 的方案唯一，则输出 "YES"。如果存在多种方式，则输出 "NO"。 **输入输出样例** **输入样例 #1** ``` 5 (?)) ?????? () ?? ?(?)()?) ``` **输出样例 #1** ``` YES NO YES YES NO ``` **说明** 第一个测试案例中，唯一可能的原始 RBS 是 "(())"。 第二个测试案例中，存在多种方式恢复一个 RBS。 第三和第四个测试案例中，唯一可能的原始 RBS 是 "()"。 第五个测试案例中，原始 RBS 要么是 "((()()))"，要么是 "(())()()"。