C/C++教程

Bracket Sequence CodeForces - 223A

本文主要是介绍Bracket Sequence CodeForces - 223A,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

原题链接
考察:栈,模拟
  模拟栈匹配,不匹配的留入栈里.然后栈里都是不匹配的坐标,相邻之间都是匹配的.

#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
char s[N],res[N];
int match[N],top,stk[N],sum[N];
int main()
{
	scanf("%s",s+1);
	int len = strlen(s+1);
	//这样栈存储的都是不配对的下标,这之间都是配对的. 
	for(int i=1;i<=len;i++)
	{
		if(s[i]=='[') sum[i]++;
		sum[i] += sum[i-1];
	}
	for(int i=1;i<=len;i++)
	{
		if(!top) stk[++top]  = i;
		else if(s[stk[top]]=='('&&s[i]==')') top--;
		else if(s[stk[top]]=='['&&s[i]==']') top--;
		else stk[++top] = i;
	}
	stk[++top] = len+1;
	int ans = -1,ansl,ansr;
	for(int i=1;i<=top;i++)
	{
		int l = stk[i-1],r = stk[i]-1;
		if(sum[r]-sum[l]>ans)
		{
			ans = sum[r]-sum[l];
			ansl = l+1,ansr = r;
		}
	}
	printf("%d\n",ans);
	for(int i=ansl;i<=ansr;i++)
		res[i-ansl] = s[i];
	res[ansr+1] = '/0';
	printf("%s\n",res);
	return 0;
}
这篇关于Bracket Sequence CodeForces - 223A的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!