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

样例输入 #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 “(())()()”.

1:判断一个括号是不是正确算术表达式的括号序列，另(为1，)为-1，如果在遍历过程算前缀和出现小于0的情况就是不符合的

2:这里有一个思想，对于这些问号，我先填(肯定是最优的，就相当于，前面全是(,后面全是),)这个要尽量靠后

3:当)这个向前移动一位，这个就是第二优的情况，对于这个第二优，如果可以，那就是NO，如果不行，说明明后面不管怎么移也都是不行的

4:所以这样之后只要判断()的最中间位置，这两个交换下位置即可

小细节：序列肯定是(的数量等于)的数量，所以他们的数量必定是len/2，len/2-左括号的数量或者右括号的数量就是他们剩下需要的数量，如果问号的数量等于某一个括号所需要的数量，必定是YES，因为没得选

const int N = 1e6 + 10;
int n;
int cheak(string s)
{
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (s[i] == '(') ans++;
        else ans--;
        if (ans < 0) return 0;
    }
    return 1;
}
int a[N];
void solve()
{
    string s;
    cin >> s;
    n = s.size();
    s = " " + s;
    if (s[1] == '?') s[1] = '(';
    if (s[n] == '?') s[n] = ')';
    int z = 0, y = 0;
    int wen = 0;
    for (int i = 1; i <= n; i++)
    {
        if (s[i] == '(') z++;
        else if (s[i] == ')') y++;
        else wen++, a[i] = 1;
    }
    int ca = max(y, z) - min(y, z);
    if (wen == 0 || wen == 1 || wen == ca)
    {
        cout << "YES" << '\n';
        for (int i = 0; i <=  n; i++) a[i] = 0;
        return;
    }
    int zs = n / 2 - z;
    int ys = n / 2 - y;

    for (int i = 1; i <= n; i++)
    {
        if (s[i] == '?' && zs >= 1)
        {
            s[i] = '(';
            zs--;
        }
        else if (s[i] == '?' && zs == 0 && ys >= 1)
        {
            s[i] = ')';
            ys--;
        }
    }
    int ok = 0;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == 1 && s[i] == ')')
        {
            for (int j = i - 1; j >= 1; j--)
            {
                if (a[j] == 1 && s[j] == '(')
                {
                    s[i] = '(';
                    s[j] = ')';
                    ok = 1;
                    break;
                }
            }
        }
        if (ok) break;
    }
    if (cheak(s)) cout << "NO" << '\n';
    else cout << "YES" << '\n';
    for (int i = 0; i <= n; i++) a[i] = 0;
}