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

传送门

题意：

　　给你一个只包含 '(' 和 ')' 的长度为 n 字符序列s；

　　给出一个操作：将第 i 个位置的字符反转（'(' ')' 互换）；

　　问有多少位置反转后，可以使得字符串 s 变为"Regular Bracket Sequence"；

　　输出满足条件的位置的个数；

题解：

　　令 '(' = 1 , ')' = -1；

　　定义 sum[i]:括号序列的前缀和；

　　一个合法的括号匹配串的充要条件是：

　　　　[1] 对于任何 i，sum[i] ≥ 0；

　　　　[2] sum[n]=0；

 int n;

 char s[maxn];

 int sum[maxn];///前缀和

 int a[maxn];///a[i]:min{sum[1,..,i]}

 int b[maxn];///b[i]:min{sum[i,..,n]}

　　枚举位置 i，判断将位置 i 反转后序列是否变为 "Regular Bracket Sequence"；

 ///i位置反转只会影响[i,n]的sum值

 ///首先要确保[1,i-1]序列满足条件[1]

 ///接着判断将i位置反转后

 ///①sum[n]±2是否为0

 ///②b[i]±2是否≥0

 bool isSat(int i)///判断i位置反转后序列是否可以变为RBS

 {

     if(a[i-] < )

         return false;

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

         return b[i]+ >=  && sum[n]+ ==  ? true:false;

     else

         return b[i]- >=  && sum[n]- ==  ? true:false;

 }

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define INF 0x3f3f3f3f

 const int maxn=1e6+;

 int n;

 char s[maxn];

 int sum[maxn];

 int a[maxn];

 int b[maxn];

 ///i位置反转只会影响[i,n]的sum值

 ///首先要确保[1,i-1]序列满足条件[1]

 ///接着判断将i位置反转后

 ///①sum[n]±2是否为0

 ///②b[i]±2是否≥0

 bool isSat(int i)///判断i位置反转后序列是否可以变为RBS

 {

     if(a[i-] < )///[1,i-1]不满足条件[1]

         return false;

     if(s[i] == '(')///'('变为')' i及其之后的sum-2

         return b[i]- >=  && sum[n]- ==  ? true:false;

     else

         return b[i]+ >=  && sum[n]+ ==  ? true:false;

 }

 int Solve()

 {

     sum[]=;

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

         sum[i]=sum[i-]+(s[i] == '(' ? :-);

     a[]=INF;

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

         a[i]=min(sum[i],a[i-]);

     b[n+]=INF;

     for(int i=n;i >= ;--i)

         b[i]=min(sum[i],b[i+]);

     int ans=;

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

         if(isSat(i))

             ans++;

     return ans;

 }

 int main()

 {

     scanf("%d%s",&n,s+);

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

     return ;

 }

Codeforces Round #529 (Div. 3) E. Almost Regular Bracket Sequence（思维）的相关教程结束。