UVA 11988 Beiju Text

时间:2021-11-11 09:57:02

https://vjudge.net/problem/UVA-11988

题目

你有一个破损的键盘。键盘上所有的键都可以正常工作,但有时候Home键或者End键会自动按下。你并不知道键盘存在这一问题,而是专心打稿子,甚至连显示器都没打开。当你打开显示器后,展现在你面前的是一段悲剧文本。你的任务是在打开显示器之前计算出这段悲剧文本。

输入包含多组数据。每组数据占一行,包含不超过100000个字母、下划线、字符“[”或者“]”。其中字符“[”表示Home键,“]”表示End键。输入结束标志为文件结束符(EOF)。输入文件不超过5MB。对于每组数据,输出一行,即屏幕上的悲剧文本。

样例输入:

This_is_a_[Beiju]_text
[[]][][]Happy_Birthday_to_Tsinghua_University

样例输出:

BeijuThis_is_a_text
Happy_Birthday_to_Tsinghua_University

题解

服了= =

两年前看见这题……看不懂

几个月前看了邓公的数据结构课的链表大概知道是怎么回事了……(“邓俊辉的数据结构,贵系授课质量最好的课”)

个人思路:

UVA 11988 Beiju Text

写个双向链表……在Start后(需要更新cur)或End处插入元素……

如果在start处还需要记录当前的字符位置:

UVA 11988 Beiju Text

比如已经输入1和2,将要插入3……

可以定义个node结构体,包含last、next和ch三个元素,然后定义个node数组,直接操作就好了……

但是紫书上告诉我可以用单向链表,不用定义结构体……代码量还很小,不用分别是否在讨论Start和End插入

紫书上的答案:

如果使用单向链表,尝试理解了下书上给的答案

UVA 11988 Beiju Text

如果使用单向,那么End节点作用就不大,不能用End来找出之前的元素,直接定义为-1……在最后插入仍然需要记录当前的位置(如d)

那么在Start和End处的插入操作可以统一

那么大概就懂了……开始编码

#include<bits/stdc++.h>
using namespace std; #define REP(i,x,y) for(register int i=x; i<y; i++)
#define REPE(i,x,y) for(register int i=x; i<=y; i++) char s[100007];
int nxt[100007];
int lst, cur;
int main() {
while(~scanf("%s", s+1)) {
nxt[0]=-1;
cur=0;
for(int i=1; s[i]; i++) {
if(s[i]=='[') {
lst = cur;
cur = 0;
} else if(s[i]==']') {
cur = lst;
} else {
nxt[i]=nxt[cur];
nxt[cur]=i;
cur=i;
}
}
for(int i=nxt[0]; ~i; i=nxt[i]) {
putchar(s[i]);
}
putchar('\n');
}
return 0;
}

然后就WA了……

看到标程,发现Home键可能不止按下一次……有点悲剧

AC代码:

#include<bits/stdc++.h>
using namespace std; #define REP(i,x,y) for(register int i=x; i<y; i++)
#define REPE(i,x,y) for(register int i=x; i<=y; i++) char s[100007];
int nxt[100007];
int lst, cur;
int main() {
while(~scanf("%s", s+1)) {
nxt[0]=-1;
cur=0, lst=0;
for(int i=1; s[i]; i++) {
if(s[i]=='[') {
cur = 0;
} else if(s[i]==']') {
cur = lst;
} else {
nxt[i]=nxt[cur];
nxt[cur]=i;
if(lst==cur) lst=i;
cur=i;
}
}
for(int i=nxt[0]; ~i; i=nxt[i]) {
putchar(s[i]);
}
putchar('\n');
}
return 0;
}

然后感叹: 刘老爷是真的牛批,邓公的数据结构课是真的毛……