UVa11988 Broken Keyboard (a.k.a. Beiju Text) [链表]

题目链接:https://vjudge.net/problem/UVA-11988

设输入的字符串是s[1~n]

next[i]表示在当前显示屏中s[i]右边的字符编号(即在s中的下标)

假设字符串s的最前面还有一个虚拟的s[0],则next[0]就可以表示显示屏中最左边的字符。

cur表示光标位置,即当前光标位于s[cur]的右边,cur=0表示光标位于“虚拟字符”s[0]的右边,即显示屏的最左边。last表示显示屏的最后一个字符是s[last]。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

const int maxn=100005;

int len,last,cur,next[maxn];
char str[maxn];

int main(){
//	freopen("temp.in","r",stdin);
	while(scanf("%s",str+1)==1){
		len=strlen(str+1);
		last=cur=0;
		next[0]=0;
		for(int i=1;i<=len;i++){
			char ch=str[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;i=next[i])
			putchar(str[i]);
		putchar('\n');
	}
	return 0;
}

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

您正在使用您的 WordPress.com 账号评论。 注销 /  更改 )

Google photo

您正在使用您的 Google 账号评论。 注销 /  更改 )

Twitter picture

您正在使用您的 Twitter 账号评论。 注销 /  更改 )

Facebook photo

您正在使用您的 Facebook 账号评论。 注销 /  更改 )

Connecting to %s

%d 博主赞过: