括号串

NC222782. 括号串

描述

有一天，小 Y 正在研究括号串。
“给出一个括号串，判断括号是否匹配。”
小 Y 说：“这不是傻×题吗？”。于是，小 Y 加强了一下：
“给出一个括号串，判断括号是否匹配，如果不匹配，请补全该括号串。”
例如：())[]]( 的一种补全方式为 (())[][]()
不一会儿，小 Y 解决了这道题，然而，他发现，这道题目有多种解法！但是他不会写 SPJ 了，于是他只好向你求助。

输入描述

第一行一个正整数 $t$ ，表示数据组数。
接下来每组数据，
第一行两个正整数 $n$ , $m$ 。
第二行一个长度为 $n$ 的括号串 $S$ ，表示原来的括号串。
第三行一个长度为 $m$ 的括号串 $T$ ，表示补全后的括号串。

输出描述

对于每组数据，如果  是  的一种补全方式，输出 Accepted ， 否则输出 Wrong Answer 。
注意：如果  满足条件，并且存在长度为  的串  也满足条件，则  是也是符合条件的.

示例1

输入:

1
7 10	
())[]](		
()()[][]()

输出:

Accepted

示例2

输入:

2
7 10	
())[]](		
()[][]()()		
7 10		
())[]](	
[(())[]]()

输出:

Wrong Answer
Accepted

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 336ms, 内存消耗: 2116K, 提交时间: 2021-07-10 20:19:06

#include <bits/stdc++.h>
int n,m;
char s[1000001],t[1000001];
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);scanf("%s",s+1);scanf("%s",t+1);
		int g=1,x=0,y=0,p=1;
		bool ff=1;
		for(int i=1;i<=m;i++)
		{
			if(t[i]=='(')x++;
			if(t[i]==')'){if((--x)<0){ff=0;break;}}
			if(t[i]=='[')y++;
			if(t[i]==']'){if((--y)<0){ff=0;break;}}
			if(t[i]==s[p])p++;
		}
		if(ff&&p>n&&!x&&!y)puts("Accepted");
		else puts("Wrong Answer");
	}
	return 0;
}

上一题

下一题

详情