题解 P1241 【括号序列】

· · 题解

原题传送门

0.几句闲话

NOIP/CSP初赛就要来了，听说在比赛前发题解可以加人品哦！

首先这个题面。。。真的让人无f**k说（自觉和谐，讲的真的是模糊不清。之前根本就理解不了题意。

顺便提一句，标签写 递推 是什么鬼啊，连个栈都没有。

毒瘤题的特点：

样例又水又少，我的错误代码还直接秒杀各位题解区大佬们的测试数据。

我反手一个提交，闷声63分（老63分了。

1.准备工作

前置芝士：栈

例题：

  1. 红-P1739
  2. 黄-P4387

本题是绿题。光学三基色

那么什么是栈呢？

该不会真的有不知道什么是栈的人做这题吧。

其实作者在自己早年P4387（没错就是例题）的恶臭题解中介绍过了。不清楚的童鞋可以看看，记得点赞哦（光速逃。

又打广告，你该不会以为真有人看你的题解吧。

审题很重要！

不过这题你还是直接看题解区的题面解释吧。

题面解释：

对于每一个右括号，找它左边还没死被弹掉的左括号，如果可以匹配，则出栈，否则补全该括号。

接下来就可以着手写了！

2.与\color{red}WA的斗争

在说正解之前，先看看本蒟蒻的错误。

思路：

各设一个栈存放无法匹配的两种括号，还有一个栈存放所有左括号。

对于每一个左括号，存放到对应的栈中，并记录出现的位置。对于每一个右括号，如果可以匹配，同时弹栈。否则存入对应栈中。

最后按类型输出即可。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>

using namespace std;
struct node{char c; int num;}lit[110],mid[110];//小括号，中括号栈
int ltop,mtop,lnow=1,mnow=1;
string a;
char lef[110];//离当前右括号最近的左括号
int leftop;
int main()
{
//  freopen("work.in","r",stdin);freopen("work.out","w",stdout);
    cin >> a;
    int n=a.length();
    for(int i=0;i<n;i++)
    {
        if(a[i] == '(')//左括号
        {
            lit[++ltop].num=i;
            lit[ltop].c=a[i];
            lef[++leftop]=a[i];
        }
        if(a[i] == ')')//右括号
        {
            if(ltop && lit[ltop].c == '(' && lef[leftop] == '(') ltop--,leftop--;
            else lit[++ltop].num=i,lit[ltop].c=a[i];
        }
     //下同
        if(a[i] == '[')
        {
            mid[++mtop].num=i;
            mid[mtop].c=a[i];
            lef[++leftop]=a[i];
        }
        if(a[i] == ']')
        {
            if(mtop && mid[mtop].c == '[' && lef[leftop] == '[') mtop--;
            else mid[++mtop].num=i,mid[mtop].c=a[i];
        }
    }
   //输出
    for(int i=0;i<n;i++)
    {
        bool f=false; 
        if(i == lit[lnow].num && lnow <= ltop)
        {
            f=true;
            if(lit[lnow].c == '(') printf("%c)",a[i]);
            else printf("(%c",a[i]);
            lnow++;//遍历
        }
        if(i == mid[mnow].num && mnow <= mtop)
        {
            f=true;
            if(mid[mnow].c == '[') printf("%c]",a[i]);
            else printf("[%c",a[i]);
            mnow++;
        }
        if(!f) printf("%c",a[i]);//如果可以匹配，直接输出
    }
//  fclose(stdin);fclose(stdout);
    return 0;
}

这就是传说中秒杀各位题解区大佬们的测试数据的神奇代码，但这是有问题的，各位可以自己想想哪里有问题。欢迎在评论区回答，评论我都会看的。

本地秒杀测试数据，但交到洛谷IDE就被hack了QwQ（还是我写题解的时候才想到去IDE上提交的

3.正解

被63分搞到心态爆炸之后，上B栈颓废了一会儿冷静下来，想到了优化空间的解法。当时还不确定是对的。

思路：

  1. 还是搞一个栈存放所有左括号；一个栈存放所有左括号出现的位置；一个数组存放匹配结果，匹配成功则为空格，输出时忽略。
  2. 如果是左括号则入栈，如果是右括号则看看最左边还没死的左括号，匹配成功则弹栈。修改该匹配成功的左括号的匹配结果。
  3. 最后按序输出即可。

感觉思路已经很清晰了，建议不要阅读以下代码，尝试自己写出来。实在写不出来可以参考一下，但请您确保您已经做了足够的思考。 为了让读者诸君有思考和理解的空间，以下代码将不做任何注释。

code

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>

using namespace std;
int top,w[110];
string a;
char s[110],c[110];
int main()
{
//  freopen("work.in","r",stdin);freopen("work.out","w",stdout);
    cin >> a;
    int n=a.length();
    for(int i=0;i<n;i++)
    {
        if(a[i] == '(' || a[i] == '[')
        {
            s[++top]=a[i];
            w[top]=i;
            if(a[i] == '(') c[i]=')';
            else c[i]=']';
        }
        if(a[i] == ')')
        {
            if(top && s[top] == '(') {c[w[top]]=' '; top--;}
            else c[i]='(';
        } 
        if(a[i] == ']')
        {
            if(top && s[top] == '[') {c[w[top]]=' '; top--;}
            else c[i]='[';
        }
    }
    for(int i=0;i<n;i++)
    {
        if(c[i] == '(' || c[i] == '[') printf("%c%c",c[i],a[i]);
        else if(c[i] == ')' || c[i] == ']') printf("%c%c",a[i],c[i]);
        else printf("%c",a[i]);
    }
//  fclose(stdin);fclose(stdout);
    return 0;
}

Thank you for your reading!

点个赞再走嘛。拒绝白嫖，从我做起。