C. Recover an RBS

Topic link
The question ： Is to give a sequence of parentheses , It only contains ’(‘,’)‘,’?‘, here ’?‘ It can be for ‘(’ or ‘)’ , Ask whether the sequence is only one correct parenthesis sequence ( In the question, ensure that each string has at least one correct bracket sequence ).
Answer key ： We can analyze several properties of this problem ：
1： Ensure that there is at least one correct bracket sequence in the question , So don't consider the situation that doesn't exist .
2： There is no requirement to find all possible parenthesis sequences , Just find out if there is only one correct bracket sequence , So we can find all possible sequences of parentheses to see if they are 1; You can also find two possible sequences and output "NO", You can also find out if you can't find another result on the basis of the original strategy , It outputs "YES"
2： There is only one kind of bracket in the question , So don't consider something like ( [ ) ] This bracket situation , So the preceding ’(‘ It must be able to eliminate the latter one ’)‘, That is, when the number of whole brackets is the same , In a section , Ahead ‘(’ As long as it's better than the back ‘)’ Just more , Because every paragraph ‘(’ Can destroy the next section ‘)’ , Then continue to destroy the following ‘)’ .
After analyzing the above properties , We can determine a strategy that can be sure to succeed , That is to put all ‘(’ They are all placed in front in turn ’?‘ in , So under the condition of this question , There must be a strategy that can match the success .
Let's analyze how to find another answer that may match successfully , Is to let in front of and behind ‘(’ and ‘)’ If the quantitative impact is as small as possible, it is to see whether there is still a strategy that may match successfully .
How to minimize the quantitative impact of both ？
Is to exchange two different parentheses closest to each other, which is the original ’?‘, This will ensure that the impact is minimal , Because each exchange will affect the relative number of left and right parentheses in that paragraph , Suppose a far away ’)’ With the current ‘(’ swapping , This will affect a wide range , Probably the one far away ’)' It will be the last bracket . If we can't understand it like this, we can understand it like this , Our best strategy every time is to put the left bracket to the left as far as possible , The right bracket should be placed to the right as far as possible . And our current step must be to replace a left bracket with a right bracket , under these circumstances , Our best case is to take two recently different brackets , This ensures that the last left parenthesis on the left is placed in the first right parenthesis ; The first right parenthesis is placed at the position of the last left parenthesis on the left . This situation must be the best strategy in the current situation .
Here is AC Code ：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
const int N=2e5+10;
char s[N];
vector<int> l;
vector<int> r;
int main()
{
    
    int t;
    cin>>t;
    while(t--)
    {
    
        l.clear();
        r.clear();
        cin>>s+1;
        int len=strlen(s+1);
        int cntl=0,cntr=0;
        for(int i=1;i<=len;i++)
        {
    
            if(s[i]=='(') cntl++;
            if(s[i]==')') cntr++;
        }
        cntl=len/2-cntl;
        cntr=len/2-cntr;
        if(cntl==0||cntr==0)
        {
    
            printf("YES\n");
            continue;
        }
        for(int i=1;i<=len;i++)
        {
    
            if(cntl==0) break;
            if(s[i]=='?')
            {
    
                cntl--;
                l.push_back(i);
            }
        }
        for(int i=0;i<l.size();i++)
        {
    
            int x=l[i];
            s[x]='(';
        }
        for(int i=l.back()+1;i<=len;i++)
        {
    
            if(cntr==0) break;
            if(s[i]=='?')
            {
    
                cntr--;
                r.push_back(i);
            }
        }
        for(int i=0;i<r.size();i++)
        {
    
            int x=r[i];
            s[x]=')';
        }
        swap(s[l.back()],s[r.front()]);
        // Judge whether it is possible 
        int cnt=0;
        bool flag=false;
        for(int i=1;i<=len;i++)
        {
    
            if(s[i]=='(') cnt++;
            if(s[i]==')') cnt--;
            if(cnt<0)
            {
    
                flag=true;
                break;
            }
        }
        if(flag==true) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

summary ： The key to solving this problem is that any bracket in front of it can eliminate the bracket behind it , It is different from the bracket matching encountered before , therefore , Such questions must be specific , make a concrete analysis . Find out the unique properties of this problem , Never set your mind .