自动搬运

查看原文

来自洛谷，原作者为

	MY（一名蒟蒻） 你数据结构都用错了，怎么改都是没用的。

搬运于2025-08-24 21:22:48，当前版本为作者最后更新于2020-08-25 21:01:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

原题传送门

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!

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