Codeforces Round #529 (Div. 3) E. Almost Regular Bracket Sequence (思维,模拟栈)

题意:给你一串括号,每次仅可以修改一个位置,问有多少位置仅修改一次后所有括号合法.
题解:我们用栈来将这串括号进行匹配,每成功匹配一对就将它们消去,因为题目要求仅修改一处使得所有括号合法,所以栈中最后一定会有两个括号剩余,并且这两个括号要么是\(((\)要么是\())\),\()(\)是无论如何都不合法的,对于\())\),我们去找它左边的\()\)的个数贡献给答案(因为每次修改可以使[\((++\),\()--\)],所以栈中剩余的\())\)就没有了),对于\(((\)的情况也是一样的,我们只要去找它右边的\((\)就行了.

代码:

int n;

char s[N];

int stk[N];

int cnt;

int main() {

    //ios::sync_with_stdio(false);cin.tie(0);

    scanf("%d",&n);

    scanf("%s",s+1);

    for(int i=1;i<=n;++i){

        if(s[i]==')'){

            if(cnt && s[stk[cnt]]=='(') cnt--;

            else stk[++cnt]=i;

        }

        else stk[++cnt]=i;

    }

    if(cnt&1 || cnt>2 || cnt==0){

        puts("0");

        return 0;

    }

    int top1=stk[cnt];

    int top2=stk[cnt-1];

    int ans=0;

    if(s[top2]==')'){

        if(s[top1]==')'){

            for(int i=top2;i>=1;--i){

                if(s[i]==')') ans++;

            }

            printf("%d\n",ans);

        }

        else{

            puts("0");

        }

    }

    else{

        for(int i=top1;i<=n;++i){

            if(s[i]=='(') ans++;

        }

        printf("%d\n",ans);

    }

    return 0;

}

巴特西

Codeforces Round #529 (Div. 3) E. Almost Regular Bracket Sequence (思维,模拟栈)

最新文章

热门文章