Almost Regular Bracket Sequence

https://codeforces.com/contest/1095/problem/E

C++版本一

题解：服了，WA了十几次，一边WA一边改

首先准备两个数组一个正向存储括号情况，一个反向存储括号情况。

记录异常开始时的下标（就是这里卡了）一个正向，一个反向的。

开始找可以改变的点应该从反向的异常开始点开始，这样才能改变反向异常的情况。同理到正向异常的开始点就应该结束了，因为，继续进行下去，不能改变正向异常的情况。

中间还有一些特判处理，比如异常的不可能大于某些值（正负2）

如果n为奇数不用辨别了，直接0

上面两个数组中正向数组最后一个和反向数组的第一个的绝对值肯定是2；否则，直接0处理就行了；

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=1000000+1000;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
char str[N];
int a[N];
int b[N];
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    scanf("%d",&n);
    scanf("%s",str);
    if(n%2){
        cout << 0 << endl;
        return 0;
    }
    for(int i=0;i<n;i++){
        if(i)a[i]=a[i-1];
        if(str[i]=='(')
            a[i]++;
        else
            a[i]--;
        if(a[i]<-2){
            cout << 0 << endl;
            return 0;
        }
    }
    int flag=0;
    for(int i=n-1;i>=0;i--){
        b[i]=b[i+1];
        if(str[i]=='(')
            b[i]++;
        else
            b[i]--;
        if(b[i]>0&&!flag){
            flag=i;
        }
        if(b[i]>2){
            cout << 0 << endl;
            return 0;
        }
    }
    if(abs(b[0])!=2){
        cout << 0 << endl;
        return 0;
    }
    int ans=0;

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

        if(i!=0&&str[i]=='('){
            if(a[i]-2+b[i+1]==0&&a[i]-2>=0&&b[i]-2<=0)
                ans++;
        }else if(i!=n-1&&str[i]==')'){
            if(a[i]+2+b[i+1]==0&&a[i]+2>=0&&b[i]+2<=0)
                ans++;
        }
        if(a[i]<0){
            break;
        }
    }
    cout<<ans<<endl;
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

某位大佬的AC代码

#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL _INF = 0xc0c0c0c0c0c0c0c0;
const LL mod =  (int)1e9+7;
const int N = 1e6 + 100;
char s[N];
int need[N];
int n;
int ans;
void solve1(){
    int l = 0;
    for(int i = 1; i <= n; ++i){
        need[i] = 0;
        if(s[i] == '(') l++;
        if(s[i] == ')') {
            if(!l) return ;
            l--;
            need[i] = l;
        }
        need[i] = l;
    }

    if(l != 2) return ;
    for(int i = n; i >= 1; --i){
        if(s[i] == ')' && need[i] < 2) return ;
        if(need[i]>1 && s[i] == '(') ans++;
    }
    //cout << "***" << endl;
}
int main(){
    scanf("%d", &n);
    scanf("%s", s+1);
    solve1();
    reverse(s+1, s+1+n);
    for(int i = 1; i <= n; ++i) {
        if(s[i] == '(') s[i] = ')';
        else s[i] = '(';
    }
    solve1();
    //for(int i =)
    printf("%d\n", ans);
    return 0;
}
/*
6
(())))
8


*/

C++版本三

还是某位大佬的代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll inff = 0x3f3f3f3f3f3f3f3f;
#define FOR(i,a,b) for(int i(a);i<=(b);++i)
#define FOL(i,a,b) for(int i(a);i>=(b);--i)
#define REW(a,b) memset(a,b,sizeof(a))
#define inf int(0x3f3f3f3f)
#define si(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define sd(a) scanf("%lf",&a)
#define ss(a) scanf("%s",a)
#define mod ll(6666666)
#define pb push_back
#define eps 1e-6
#define lc d<<1
#define rc d<<1|1
#define Pll pair<ll,ll>
#define P pair<int,int>
#define pi acos(-1)
int n,b[1000008],c[1000008],d[1000008];
string a;
int main()
{
    cin.tie(0);
    cout.tie(0);
    int s=0,l=0,r=0,is=0,er=0;
    cin>>n>>a;
    FOR(i,0,n-1)
    {
        if(a[i]=='(') l++;
        if(a[i]==')') r++;
        b[i]=l,c[i]=r;
        if(r>l&&!is) is=1,s=r,a[i]='(';
    }
    if(!is)
    {
        FOL(i,n-1,0)
        {
            if(b[i]-c[i]<2) {a[i+1]=')';break;}
            else if(a[i]=='(')s++;
        }
    }
    l=r=is=0;
    FOR(i,0,n-1)
    {
        if(a[i]=='(') l++;
        if(a[i]==')') r++;
        if(r>l) {is=1;break;}
    }
    if(is||s>n||l!=r) s=0;
    cout<<s<<endl;
    return 0;
}