故事开端

忆昔当年泪不干，在这么一个平凡的夜晚，我在牛客打了一发小白月赛。当时的我并不知道这场比赛将会对现在的我造成多大的影响，以至于如今我时常怀念那个无所不能的自己。**

（好像也不是很厉害）

比赛

可以看到，七道题目我过了五题，水平还算好吧，看看最后两题过的人这么少（自豪）

好了也不多bb，开始进入正题

初次相遇

括号弱化

我当时一看到这题，脑子里面浮现好几种做法，其中就有栈(有关栈的描述请看oi wiki 栈)，但是最后我选择用数组来做，我也不知道我怎么想的，可能是因为以前在洛谷做过类似的题，比如P1739 表达式括号匹配（用栈来验证左右括号是否完全匹配），就想用没做过的办法来写，于是就用了字符数组来做。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define NO cout<<"NO"<<endl
#define YES cout<<"YES"<<endl
char a[2000500];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//解绑
	int n,k,num1,num2;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]=='I')//记录光标位置，删掉左边括号就是num1--,删掉右边括号就是num2++，不用再处理中间的部分，也相当于“删除”
			num1=i-1,num2=i+1;
	}
	for(int i=1;i<=k;i++){
		string b;
		cin>>b;
		if(b=="backspace"){
            //回车删除判断左右括号是否匹配
			if(a[num1]=='('){
				if(a[num2]==')'){
					num1--;
					num2++;
				}
				else
					num1--;
			}
            //判断光标左边的括号是右括号的情况
			else
				if(a[num1]==')')
					num1--;
		}
        //delete键删除，只会删除光标右边的括号，判断一下右边是否存在括号
		else{
			if(a[num2]=='('||a[num2]==')')
				num2++;
		}
	}
    //顺序输出字符串
	for(int i=1;i<=num1;i++)
		cout<<a[i];
	cout<<'I';
	for(int i=num2;i<=n;i++)
		cout<<a[i];	
	return 0;
}

这题也是十分简单的一题，不过字符串的题总是特别会给自己加戏，比如这里一个特判那里一个特判，我就是因为忘记判断delete删除时光标右边是否存在括号直接wa2发，罚时上天，哭了OVO

本来做到这里我就想润了，因为我其实是一边打游戏一边比赛的，而且这题是第三题，已经浪费了我许多宝贵的游戏时间了，但是挑战自我的想法猛地从我内心窜出来，我决定再写十分钟（其实是不想被别人比下去）

灵感大爆发!

括号强化

一刻也没有为上一题哀悼，随着赶到战场的是——hard 删除括号！

这题相对于上题，难度就在于这个新增的操作：光标左右移。我当时觉得如果仍然采用上题的思路来写，会导致一个很棘手的问题：（以光标左边为例）光标左移后，原先的一个括号移动到光标右侧，那变动的这个括号该如何处理?（好像这玩意也可以用a[num2-1]来处理，然后num2- -，相当于变动的括号移到右边，不过我当时没想到这个，这个对不对我也没检验过）

然后我就想啊想，想了一会就想下播了，已经不想打力。然后我都打开游戏界面了，但突然想起来栈这玩意，我当时就在想，判断一序列括号是否合法不就可以用栈进出来做吗，脑海里就浮现出一张图，光标左移就是把左边的栈的栈顶取出，栈内括号数量减一，那这个出栈的括号又没有删除，怎么处理呢？那不就是放到右边的栈吗？！（此时把题目输入的字符串分为两个栈，一个栈存光标左边的括号，另一个存右边的括号，两个栈一个进栈序列是顺序，一个是逆序，就相当于两个栈的出口相对，也就是对顶栈）

来不及解释了，我一边思考着这个问题，一边敲代码测试，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define NO cout<<"NO"<<endl
#define YES cout<<"YES"<<endl
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n,k,flag=0,num1,num2,num;
	string c="";
	cin>>n>>k;
	stack<char> ds1,ds2;
	for(int i=1;i<=n;i++){
		char a;
		cin>>a;
		if(a=='I')
			flag=1;
		if(flag==0)
			ds1.push(a);//栈ds1存光标左边括号
		if(flag==1&&a!='I')
			c+=a;//存光标右边的所有括号
	}
	for(int i=c.length()-1;i>=0;i--)
		ds2.push(c[i]);//将光标右边所有括号逆序存进栈ds2中，这样删除操作才是正确顺序
	for(int i=1;i<=k;i++){
		string b;//b接收输入判断操作
		cin>>b;
		if(b=="backspace"){
			char tmp1='1',tmp2='1';
			if(!ds1.empty())//回车删除判断左边括号是否存在，只要存在，不管左右是否对应，左边括号必须删除
				tmp1=ds1.top(),ds1.pop();
			if(!ds2.empty())//判断右边括号是否存在
				tmp2=ds2.top();
			if(tmp1=='('&&tmp2==')')//判断左右括号配对
				ds2.pop();
		}
		else if(b=="delete"){//delete只用判断右边括号是否存在
			if(!ds2.empty())
				ds2.pop();
		}
		else if(b=="<-"){
			if(!ds1.empty()){//左移，左边括号出栈，进到右边的栈，没括号就不移
				char tmp1=ds1.top();
				ds1.pop();
				ds2.push(tmp1);
			}
		}
		else{
			if(!ds2.empty()){//右移，右边括号出栈，进到左边的栈，没括号就不移
				char tmp1=ds2.top();
				ds2.pop();
				ds1.push(tmp1);
			}
		}
	}
	string a="",b="";//栈ds1的出栈序列是反的，所以需要字符串存一下再逆序输出
	while(!ds1.empty()){
		char tmp=ds1.top();
		a+=tmp;
		ds1.pop(); 
	}
	for(int i=a.length()-1;i>=0;i--)
		cout<<a[i];
	cout<<'I';//光标处于两个栈中间
	while(!ds2.empty()){//栈ds2进栈序列是反的，那出栈序列就是正的，直接出栈输出
		char tmp=ds2.top();
		cout<<tmp;
		ds2.pop();
	}
	return 0;
}

第一次交的时候wa了，当时我心脏都停跳了，这么完美的想法居然是错的？本着写都写了的理念，我开始找样例调试，然后发现：我当时ds2也用了一个字符串存出栈序列来逆序输出，这就导致了光标右边的括号都是反的，而题目给的样例都是要么括号删完了，要么光标移动到最右边了，所以能过样例。改完之后我忐忑地点了提交，过了几秒就出现那个死牛和死人音效，悬着的心终于放下来了O.o

死牛

尾声

总的来说，这两道字符串其实不是很难，只要你能想到怎么处理那就很简单了，但是赛场上能及时想出正确的解法也是一件不容易的事，事后我去看了讲解，才知道我写的这玩意叫对顶栈，很简单的栈的运用，但是是我在比赛中灵感一现写出来的，对我来说也有很大的纪念意义，写这篇文章也算是回顾比赛加深知识理解了，以后我还会记录更多的奇思妙想，加纳。