时间限制 | 内存限制 |
---|---|
1000 ms |
65536 KB |
# 题目描述
Baymax 有一个破旧的键盘,键盘上所有的键都可以正常工作,但有时「Home」键或者「End」键会自动按下。Baymax 并不知道键盘的问题,而是专心地打着稿子,甚至连显示器都没打开。现在给出键盘的输入,请你计算出 Baymax 打开显示器之后显示的文本。
# 输入格式
不定组数据输入,保证数据组数不超过 组。
每组数据一行,一个字符串 ,保证 的长度 ,且 中不含有空格。
其中,字符 [
表示「Home」键,按下之后输入光标将移动到本行最前端;字符 ]
表示「End」键,按下之后输入光标将移动到本行最尾端。
# 输出格式
对于每组数据,输出一行,即显示器显示的文本。
# 输入样例
love[I_]_BUAA | |
[[]][][]Baymax_is_sad_for_the_broken_keyboard |
# 输出样例
I_love_BUAA | |
Baymax_is_sad_for_the_broken_keyboard |
# 样例解释
对于第一组数据,当遇到 [
之前,输入 love
,文本为 love
,随后,光标移动到最前端,输入 I_
后文本变为 I_love
,当遇到 ]
后,光标移动到文本末尾,输入 _BUAA
,最终输出文本为 I_love_BUAA
。
# 题解:链表
依题意,建一个链表模拟操作过程即可。
时间复杂度:,其中 为所有字符串的长度之和。
参考代码:
#include <stdio.h> | |
#include <string.h> | |
int head, tail, size; | |
char str[100010]; | |
struct Node | |
{ | |
int prev, next; | |
char c; | |
} node[100010]; | |
int Insert(int ind, char c) | |
{ | |
node[ ++ size].c = c; | |
node[size].prev = ind, node[size].next = node[ind].next; | |
node[node[ind].next].prev = size, node[ind].next = size; | |
return size; | |
} | |
void print() | |
{ | |
int i = head; | |
while (node[i].next != tail) | |
{ | |
i = node[i].next; | |
putchar(node[i].c); | |
} | |
puts(""); | |
return; | |
} | |
int main() | |
{ | |
// freopen("O.in", "r", stdin); | |
// freopen("O.out", "w", stdout); | |
while (~scanf("%s", str)) | |
{ | |
int len = strlen(str); | |
head = 1, tail = 2, size = 2; | |
node[head].next = tail, node[tail].prev = head; | |
int ind = head; | |
for (int i = 0; i < len; ++ i) | |
{ | |
if (str[i] == '[') | |
ind = head; | |
else if (str[i] == ']') | |
ind = node[tail].prev; | |
else | |
ind = Insert(ind, str[i]); | |
} | |
print(); | |
} | |
return 0; | |
} |