题解 CF5C 【Longest Regular Bracket Sequence】

~~我也不知道用的什么算法，思维题？乱搞？~~首先就是和常规的括号匹配那样用栈存起来——遇到“（”放入栈里，遇到“）”栈顶高度减一，相当于成功找到一组括号匹配。变化的地方就在我们先建立一个a数组初始全部是Flase代表所有括号是独立的没有匹配，然后每次当遇到“）”时，**把与当前“）”匹配的“（”和当前“）”对应的a数组中的元素分别赋值为True。这样做完之后，序列中匹配过的括号就是True，没有匹配的括号就是Flase。** ------------ _还不懂？看例子_ ------------ **( ) ( ) ) ) ( ) )( ) ( ) (( )** **1111001101111011** ------------ 我们用1表示True，0表示False，然后就是这个样子 ------------ 然后我们就可以直接求最长连续1就好了呀，**也就是相当于求最长连续的已完成匹配的括号** ------------ 1的长度自然是最长的合法括号长度，第一遍做按上面所描述的做法求出长度，然后再做一遍求出有多少个一样长的。————LuckyCloud. ------------ ```cpp #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; } ``` ------------