题解：P7269 [BalticOI 2005] Magic Parenthesis

Fake_Cry · 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;//好习惯
}