CF1153C. Serval and Parenthesis Sequence

题目链接：CF1153C

题目大意

给你一个串，只包含字符 "(" ")" "?",问可不可以通过吧 "?" 变成括号，使得字符串s满足：
1.整个串是合法的括号序列
2.任何前缀都不是一个合法的括号序列
如果可以输出转换后的串，否则输出“:(”

Input

第一个行输入一个 表示字符串长度
第二行输入一个只含有题意中字符的串

Output

如果有解，输出这个解
没有则输出“:(”

样例

Input:

6
(?????

Output:

(()())

Input:

10
(???(???(?

Output:

:(

解题思路

s[0...t-1] ="(((?))?)"

一个串整体是合法括号序列，那么必有s[0]='('和s[t-1]=')'
任意前缀都不是合法序列，那么去掉s的开头和结尾，剩下的中间这部分一定是一个合法括号序列。

对于s,开头结尾已经是"("和")"了，剩下部分用区间[l,r]表示：
s[l...r]=((?))?
需要让这段区间是合法序列，我们遍历这个区间，更改"？"，从开头到每一个位置为止，左括号数量不能小于右括号的数量（多出的右括号会和s[0]凑成一个合法前缀），最后在这个区间中，左括号数量等于右括号数量的话，即为答案。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
string s;
int t;
int main(){
    cin>>t;
    cin>>s;
    if(t%2!=0
       ||t==0
       ||s[0]==')'
       ||s[t-1]=='('
       ){//答案一定是偶数长度的串，s[0]不是),s[t-1]不是(
            cout<<":("<<endl;
            return 0;
       }
    s[0]='(';
    s[t-1]=')'; //上面判断后 s[0] s[t-1] 一定可以改成这样
    int l=1,r=t-2; // 区间 [l,r]
    int jsl=0,jsr=0,f;
    for(int i=l;i<=r;i++){  //遍历扫一遍，统计左括号，右括号已经有多少个
        if(s[i]=='(') jsl++;
        else if(s[i]==')') jsr++;
    }

    int m = (r-l+1)/2; //如果区间长度是6，左括号右括号肯定不大能于3个，m=3;
    f=1; //记录结果是否可以
    if(jsl>m||jsr>m)f=0;
    int acl=0,acr=0; //遍历时，记录已经出现多少左括号和右括号
    if(f)
    for(int i=l;i<=r;i++){
       if(s[i]=='('){
            acl++; //左括号用正数表示
        }else if(s[i]==')'){
            acr--; //右括号用负数表示
            if(acl+acr<0){f=0;break;} //任何时候，右括号不能比左括号出现的多
        }else if(s[i]=='?'){
            if(acl+acr==0){ // 左右括号相等，"()"，肯定放"("
                s[i]='(';
                acl++;
                jsl++;
                if(jsl>m){f=0;break;} //不能多于m个
            }else if(acl+acr<0){ //右括号不能比左括号多
                f=0;
                break;
            }else if(acl+acr>0){ //这里"("多，可以放"("或")",优先放"(",否则会错，比如s[l,r]="((?))?"
                if(jsl+1<=m){
                    s[i]='(';
                    acl++;
                    jsl++;
                }else{
                    s[i]=')';
                    jsr++;
                    acr--;
                    if(jsr>m){f=0;break;}
                }
            }
        }
    }
    if(f)
        if(!(acl+acr==0&&jsl<=m&&jsr<=m&&jsl+jsr==m*2))f=0;
    if(f)cout<<s<<endl;
    else cout<<":("<<endl;
    return 0;
}