自动搬运

查看原文

来自洛谷，原作者为

	Fake_Cry Last Time：2025年8月24日22时28分| 迎着朝阳，奔向远方|纱雾可爱|TaylorSwift万岁|代词请用她|彩笔|二次元|互关 /paste/2n9pjlfz

搬运于2025-08-24 22:28:16，当前版本为作者最后更新于2025-08-09 16:38:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解：P7269 [BalticOI 2005] Magic Parenthesis

题意

输入一个字符串，求每一个中括号要替换成多少个小括号才能使这个字符串变为一个合法括号串（合法括号串的定义在题目背景中）。

思路

定义一个变量记录右括号的个数，遇到左括号就减少这个变量。需要特判的是，如果当前的右括号数量小于左括号数量了（也就是此变量为负数），就是无解。输出部分的解释详见代码注释。

代码

#include<bits/stdc++.h>
using namespace std;
signed main()
{
	int n,m;
	cin>>n>>m;
	int cnt=0,t=0;
	while(t<n){//给定的序列可能不在一行，需要循环输入
		string s;
		cin>>s;
		for(int i=0;i<s.length();i++){
			if(s[i]=='(') cnt++;//出现左括号就计数
			else cnt--;//否则减少计数
			if(cnt<0){//右括号数量小于左括号数量
				cout<<0;//表示无解
				return 0;
			}
		}
		t+=s.length();
	}
	cout<<1<<'\n';//表示有解
	for(int i=1;i<m;i++)//除去最后一个
		cout<<1<<'\n';
	cout<<cnt+1;//补上刚才删掉的最后一个
	return 0;//好习惯
}