codeforce 459DIV2 C题

题意

一串括号字符串，里面存在一些‘？’，其中‘？’既可以当作 '(' 又可以当作 ')' ，计算有多少对(l,r)，在s中[sl,s(l+1),s(l+2),.....sr],内的括号是匹配的。n=strlen(s)<=5000。

分析

这个题还是卡了很久的，我果然是很菜的。

（错误思路）
一开始的时候想，用一个变量cur表示还未匹配的左括号 '(' ，用变量num记录‘?’的数量，‘？’尽量当右括号使用，在判断(l,r)是否匹配的时候从左往右扫，遇到'(' 的时候cur++，遇到 ')'cur--，如果最左边的字符是'?'那么直接将其变成'(' num--,cur++;因为它如果是')'不再有作用。当cur==num的时候说明当前长度是匹配的。如果num>cur，且（num-cur）%2==0则说明问好可以和‘（’匹配，剩下的‘？’自己互相匹配。

错误代码：

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <iostream>

 using namespace std;

 const int maxn=+;

 char s[maxn];

 int n;

 int main(){

     scanf("%s",s);

     n=strlen(s);

     int ans=;

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

         int cur=,num=;

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

         else cur++;

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

             bool jud=;

             if(s[j]=='(')cur++;

             if(s[j]==')')cur--;

             if(s[j]=='?')num++;

             if(cur==&&num==)jud=;

             else if(cur==&&num){cur++;num--;}

             if(cur==num)jud=;

             else if(num>cur&&(num-cur)%==)jud=;

             if(jud)ans++;

         }

     }

     cout<<ans<<endl;

     return ;

 }

思路纠正：

上面一开始我考虑最左边的'?'只能被当作（使用，可以在深入考虑一下，如果当前？的数量大于（的数量，那么多的？就只能被当作（使用否则没法匹配。这样可以消除对于右边的影响 "(??(()"也就是‘？’当作‘）’来匹配左边的‘（’。

正确代码：

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <iostream>

 using namespace std;

 const int maxn=+;

 char s[maxn];

 int n;

 int main(){

     scanf("%s",s);

     n=strlen(s);

     int ans=;

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

         int cur=,num=;

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

         else cur++;

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

             bool jud=;

             if(s[j]=='(')cur++;

             if(s[j]==')')cur--;

             if(s[j]=='?')num++;

             if(cur==&&num==)jud=;

             else if(cur==&&num){cur++;num--;}

             if(cur==num)jud=;

             else if(num>cur&&(num-cur)%==)jud=;

             if(jud)ans++;

         }

     }

     cout<<ans<<endl;

     return ;

 }

巴特西

codeforce 459DIV2 C题

最新文章

热门文章