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

今天我們來看看CF1095E
題目連結

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

前言

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

想法

只要維護左括號為$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