题解 CF5C 【Longest Regular Bracket Sequence】

2018-05-14 17:35:45


我也不知道用的什么算法,思维题?乱搞?首先就是和常规的括号匹配那样用栈存起来——遇到“(”放入栈里,遇到“)”栈顶高度减一,相当于成功找到一组括号匹配。变化的地方就在我们先建立一个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;
}