专栏文章

题解:P7269 [BalticOI 2005] Magic Parenthesis

P7269题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqdrvv7
此快照首次捕获于
2025/12/04 03:09
3 个月前
此快照最后确认于
2025/12/04 03:09
3 个月前
查看原文
首先,先说一句闲话,这个题的翻译有一点问题

思路

从题目描述当中我们可以看出,这个题有两种情况,一个是——有答案,一个是无答案。

有答案时

不需要考虑右括号的个数变化,因为前面的左小括号会与右小括号匹配,所以我们只要考虑把每个可操作的右中括号替换成 xx 个左小括号。

没有答案时

我们可以直接愉快的输出 00 并且退出程序即可。

AC Code

CPP
#include <iostream>
#include <string>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cstdio>
using namespace std;
#define ll long long
ll n,m,sum;//把变量写在外面是个好习惯 。 
string s; 
int main()
{
	int i,j;
	cin >> n >> m;//输入。 
	for(i = 0;i < n;i += s.size())
	{
		cin >> s;//重复输入。 
		for(j = 0;j < s.size();j++)//字符串下表从0开始,j = 0。
		{
			if(s[j] == '(')
			{
				sum++;//有多少左括号。 
			}
			else
			{
				sum--;//否则用中括号把小括号代替,与左括号抵消。 
			}
			if(sum < 0)//当右括号比左括号多,就说明无解。相当于一个特判,节省时间。 
			{
				cout << 0;//所以输出0。 
				return 0;//直接退出程序。 
			} 
		} 
	}
	cout << 1 << "\n";//没有退出程序说明有解。
	for(i = 1;i < m;i++)
	{
		cout << 1 << "\n";
	} 
	cout << sum + 1;//因为重复所以会有一个小括号抵消,在输出前加回来。
	return 0;
}  

警钟

这道题数据很恶心,不知道为啥,在换行时用 endl 第 13 个测试点会 TLE!因此必须用 \n 或其他的。别问我怎么知道的,他卡了我一下午!!!

评论

0 条评论,欢迎与作者交流。

正在加载评论...