Codeforces Round #529 (Div. 3) E. Almost Regular Bracket Sequence （思维）

Codeforces Round #529 (Div. 3)

题目传送门

题意：

给你由左右括号组成的字符串，问你有多少处括号翻转过来是合法的序列

思路：

这么考虑：

如果是左括号

1）整个序列左括号个数比右括号多 2

2）在这个位置之前，所有位置的前缀左括号个数都不少于前缀右括号个数

3）在这个位置和这个位置之后，在修改后所有位置的前缀左括号个数减去前缀右括号个数大于2

（这里这么想，把左变成右，左-1，右+1）

右括号也是这样

代码：

#include<bits/stdc++.h>

using namespace std;

const int N=1e6+;

int a[N],pre[N],post[N];

char s[N];

int n;

int main()

{

    while(~scanf("%d",&n))

    {

        scanf("%s",s+);

        int x=;

        memset(a,,sizeof(a));

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

        {

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

            else x--;

            a[i]=x;

        }

       pre[]=N,post[n]=N;

       for(int i=;i<n;i++) pre[i]=min(pre[i-],a[i]);

       for(int i=n-;i>=;i--) post[i]=min(post[i+],a[i]);

       int ans=;

       if(x!=-&&x!=)

       {

           printf("0\n");

       }

       else{

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

       {

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

           {

               if(pre[i-]>=&&post[i]>=&&x==) ans++;

           }

           else if(pre[i-]>=&&post[i]>=-&&x==-) ans++;

       }

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

       }

    }

}

巴特西

Codeforces Round #529 (Div. 3) E. Almost Regular Bracket Sequence （思维）

最新文章

热门文章