Uva11988 Broken Keyboard (a.k.a. Beiju Text) 题解【模拟链表】

题目：

思路：

1.next[i]表示真实屏幕中字符s[i]右边字符的编号（即在s中的下标），next[0]表示第一个字符的编号， s[next[0]]表示屏幕中应出现的第一个字符，next[最后一个]=0，用（i=next[0];i!=0;i=next[i]），输出应输出的字符s[i]。 2.光标cur表示要插入位置的左边那个，比如i=4时出现’[’，说明下一个字符(s[i=5])要插入到第1个位置，那么先将cur置为0，执行下一次i++，i=5；next[i=5]=next[cur=0];next[cur=0]=5; cur=5移动光标。 3.last表示显示屏中最后一个字符的编号，s[last]为最后一个字符。

不多废话了，上lrj代码，多看几遍代码也就明白了

代码：

#include <cstdio> #include <cstring> const int maxn=100000+5; int last,cur,next[maxn]; char s[maxn]; int main() { while(scanf("%s",s+1)==1) {//输入字符从s[1]开始， int n=strlen(s+1); last=cur=0; next[0]=0; memset(next, 0, sizeof(next)); for(int i=1;i<=n;i++) { char ch=s[i]; if(ch=='[') cur=0; else if(ch==']') cur=last; 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; }