题解 CF5C 【Longest Regular Bracket Sequence】

· · 题解

我也不知道用的什么算法，思维题？乱搞？首先就是和常规的括号匹配那样用栈存起来——遇到“（”放入栈里，遇到“）”栈顶高度减一，相当于成功找到一组括号匹配。变化的地方就在我们先建立一个a数组初始全部是Flase代表所有括号是独立的没有匹配，然后每次当遇到“）”时，把与当前“）”匹配的“（”和当前“）”对应的a数组中的元素分别赋值为True。这样做完之后，序列中匹配过的括号就是True，没有匹配的括号就是Flase。

还不懂？看例子

( ) ( ) ) ) ( ) )( ) ( ) (( )

1111001101111011

我们用1表示True，0表示False，然后就是这个样子

然后我们就可以直接求最长连续1就好了呀，也就是相当于求最长连续的已完成匹配的括号

1的长度自然是最长的合法括号长度，第一遍做按上面所描述的做法求出长度，然后再做一遍求出有多少个一样长的。————LuckyCloud.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int sum,tot,l,r,len,w,ans,stack[1001003],top;
bool a[1001003];
char s[1000103];
int main()
{
  scanf("%s",s);
  len=strlen(s);
  for (int i=0;i<len;i++)
  {
   if (s[i]=='(') stack[++top]=i;
   else {if (top){a[stack[top]]=true;a[i]=true;top--;}}
  }
  for (int i=0;i<=len;i++)
   if (a[i]) w++;
   else {ans=max(w,ans);w=0;}
 for (int i=0;i<=len;i++)
   if (a[i]) w++;
   else {if (w==ans)tot++;w=0;}
 if (ans)
  printf("%d %d\n",ans,tot);
 else puts("0 1\n");
  return 0;
}