题解：P7269 [BalticOI 2005] Magic Parenthesis

S_Y_B_S · 2025-08-12 22:10:35 · 题解

P7269 Magic Parenthesis 题解

题目大意

给定一个括号串，只含 (，) 和 ]，其中 ] 可替换为若干个 )。

判断此括号串是否合法，若合法，分别求出每个 ] 应替换为几个 )。

注意：若有解，答案不一定唯一。

思路

• Part 1:

  判断括号序列是否合法。

  考虑将每个 ] 都替换为一个 )。

  若在任一时刻未匹配的 ) 数量大于未匹配的 ( 数量，则说明序列不合法。

• Part 2：

  思路如上，过程中我们开一个 cnt 变量统计目前还有多少个 ( 未匹配并动态更新。

  若统计过程中出现 cnt < 0，则说明序列不合法。

  否则 cnt 即为在每个 ] 都替换为一个 ) 后还需添加的 ) 的数量。

  而这个数量只需添加在最后一个 ] 处即可，正确性显然。

Tips

• 题目中输入的字符串不一定都在同一行，注意特殊处理。

AC code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
string x,s;
int main()
{
    cin>>n>>m;
    while(cin>>x) s+=x; // 读入
    int cnt = 0; // cnt统计还有多少个未配对的 '('
    for(int i = 0;i<n;i++){
        if(s[i] == '(') cnt++;
        else{
            cnt--;
            if(cnt<0)
                return cout<<0,0;
        }
    }
    cout<<"1\n";
    for(int i = 1;i<m;i++)
        cout<<"1\n";
    cout<<1+cnt;
    return 0;
}