题解：P7269 [BalticOI 2005] Magic Parenthesis

· · 题解

首先，先说一句闲话，这个题的翻译有一点问题。

思路

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

有答案时

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

没有答案时

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

AC Code

#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 或其他的。别问我怎么知道的，他卡了我一下午!!!