【CF5C Longest Regular Bracket Sequence】题解

题目链接

题目

This is yet another problem dealing with regular bracket sequences.

We should remind you that a bracket sequence is called regular, if by inserting ?+? and ?1? into it we can get a correct mathematical expression. For example, sequences ?(())()?, ?()? and ?(()(()))? are regular, while ?)(?, ?(()? and ?(()))(? are not.

You are given a string of ?(? and ?)? characters. You are to find its longest substring that is a regular bracket sequence. You are to find the number of such substrings as well.

思路

拿个栈来维护括号序列，最后剩下在栈里的就是不能合并的。

总结

这道题是道pj-的题，却生生折腾我一个月。

他其实涉及的是一个很经典的括号匹配问题。对于这类问题，这里是其中用栈解决的一大问题。

其实，不仅左括号可以塞进栈里，右括号也可以。

同时，运用栈里剩下不能匹配的，也能求最长匹配的。

Code

// Problem: CF5C Longest Regular Bracket Sequence
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF5C
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
using namespace std;
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
//#define M
//#define mo
#define N 1000010
int n, m, i, j, k; 
int zhan[N], top, t[N], ans; 
char s[N]; 

signed main()
{
//	freopen("tiaoshi.in", "r", stdin); 
//	freopen("tiaoshi.out", "w", stdout); 
	scanf("%s", s+1); n=strlen(s+1); 
	for(i=1; i<=n; ++i)
	{
		if(s[i]=='(')
			zhan[++top]=i, t[top]=1; 
		if(s[i]==')')
		{
			if(top&&t[top]==1) --top; 
			else zhan[++top]=i, t[top]=2; 
		}
	}
	zhan[0]=0; zhan[++top]=n+1; 
	for(i=1; i<=top; ++i) 
	{
		m=zhan[i]-zhan[i-1]-1; 
		// printf("%d\n", m); 
		if(m>ans) ans=m, k=0; 
		if(m==ans) ++k; 
	}
	if(!ans) printf("0 1"); 
	else printf("%d %d", ans, k); 
	return 0; 
}