Codeforces 918C The Monster（括号匹配+思维）

题目链接：http://codeforces.com/contest/918/problem/C

题目大意：给你一串字符串，其中有'('、')'、'?'三种字符'?'可以当成'('或者')'来用，问该字符串中有多少子串符合括号匹配的规则。

解题思路：根据括号匹配原始版进行改进，设置high和low分别表示未匹配左括号数的上限和下限，当遇到'('时low++,high++，遇到')'时low--,high--，遇到'?'时由于既可以表示'('又可以表示')'，所以high++，low--。

原始版括号匹配（top为未匹配左括号数）：

 bool check(string s) {

     int top = ;

     for(int i = ; i < s.size(); ++i) {

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

         else top--;

         if(cnt < ) return false;

     }

     return cnt == ;

 }

本题代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int main(){

     int low,high,size;

     string str;

     cin>>str;

     size=str.size();

     int ans=;

     for(int i=;i<size;i++){

         low=high=;

         for(int j=i;j<size;j++){

             if(str[j]=='(') high++,low++;

             if(str[j]==')') high--,low--;

             if(str[j]=='?') high++,low--;

             if(high<)

                 break;

             if(low<) low=;

             if((j-i)%&&low==)

                 ans++;

         }

     }

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

     return ;

 }

巴特西

Codeforces 918C The Monster（括号匹配+思维）

最新文章

热门文章