Codeforce 1095 E. Almost Regular Bracket Sequence 解析(思維)

今天我們來看看CF1095E

題目連結

題目

給你一個括號序列，求有幾個字元改括號方向能夠讓整串變成合法。

前言

這題能幫助熟悉有關Regular Bracket Sequence的能夠維護的狀態。

@copyright petjelinux 版權所有

觀看更多正版原始文章請至petjelinux的blog

想法

只要維護左括號為\(1\)，右括號為\(-1\)的前(後)綴和，並維護一個前(後)綴有沒有可能是某個Regular Bracket Sequence的前(後)綴(如果想要前綴\([0,i]\)可以是某個Regular Bracket Sequence的前綴，只需要\([0,i-1]\)可以且\([0,i]\)的前綴和大於等於零)，那麼對於每個字元\(s_i\)，我們只需要\([0,i-1]\)可能是前綴且\([i+1,n]\)可能是前綴且整串的左右括號數量一樣多，即可。

程式碼:

const int _n=1e6+10;
int t,n,preB[_n],sufB[_n];
bool preC[_n],sufC[_n];
char s[_n];
main(void) {cin.tie(0);ios_base::sync_with_stdio(0);
  cin>>n>>(s+1);
  rep(i,1,n+1){
    if(s[i]=='(')preB[i]=preB[i-1]+1;
    else preB[i]=preB[i-1]-1;
  }
  per(i,1,n+1){
    if(s[i]=='(')sufB[i]=sufB[i+1]+1;
    else sufB[i]=sufB[i+1]-1;
  }preC[0]=sufC[n+1]=1;
  rep(i,1,n+1){
    if(preC[i-1] and preB[i]>=0)preC[i]=1;
    else break;
  }
  per(i,1,n+1){
    if(sufC[i+1] and sufB[i]<=0)sufC[i]=1;
    else break;
  }ll ans=0;
  rep(i,1,n+1){
    int tmp=(s[i]=='('?-1:1);
    if(preC[i-1] and sufC[i+1] and preB[i-1]+tmp+sufB[i+1]==0)ans++;
  }cout<<ans<<'\n';
  return 0;
}

標頭、模板請點Submission看

Submission