P7269 Magic Parenthesis 题解

题目大意

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

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

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

思路

Part 1:

判断括号序列是否合法。

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

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

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

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

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

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

Tips

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

AC code

CPP

#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;
}

题解：P7269 [BalticOI 2005] Magic Parenthesis

文章操作

P7269 Magic Parenthesis 题解

题目大意

思路

Tips

AC code

相关推荐

评论

题解：P7269 [BalticOI 2005] Magic Parenthesis