大家好，我是小黄呀。

VJ题目传送门

题目大意

你正在专心码字，而电脑上的Home键和End键坏掉了会随机摁下（不知道这两个键的自行百度），用符号"[“代表Home，用符号”]"代表End，来模拟屏幕上的输出。

思路分析

方法一：模拟链表 设输入字符串是s[1~n]，则可以用next[i]表示在当前屏幕中s[i]右边的字符编号。同时，假设字符串s的最前面还有一个虚拟的s[0]，然后从s[1]开始存储第一个字符，用next[0]表示第一个字符（也就是屏幕中最左边开始的字符）。然后再用一个cur表示光标的位置，也就是当前s[cur]的右边，也就等于next[cur]。根据分析，头结点设为0，即next[0]=0,头结点只起到标记作用，而不表示真实位置，总是指向链表的第一个元素。链表的插入操作。next[i]=next[cur],当前元素的下一个元素指向当前cur指向的元素。next[cur]=i,更新cur的指向，指向新的下一个元素i。当遇到‘[’，当前结点变为0，遇到‘]’，当前结点变为last。

具体代码

#include <iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn = 100000 + 5; int last,cur;//光标位于cur号字符的后面 int next[maxn];//表示maxn的下一个字符 char s[maxn]; int main() { while(scanf("%s",s+1)==1)//输入保存从s[1]开始，s[0]作为虚拟开始结点 { int n= strlen(s+1); last =cur=0; next[0]=0; for(int i=1;i<=n;i++) { char ch=s[i];//取i号字符 if(ch=='[') cur=0;//遇到"["，头结点变为0 else if(ch==']') cur=last;//遇到"]",头结点变为1ast else{//模拟链表的插入 next[i]=next[cur]; next[cur]=i; if(cur==last) last=i;//更新尾结点 cur=i; } } for(int i=next[0];i!=0;i=next[i])//依据链表顺序打印 printf("%c",s[i]); printf("\n"); } return 0; }