henrytb 的博客

henrytb 的博客

题解 UVA11988 【破损的键盘 Broken Keyboard (a.k.a. Beiju Text)】

posted on 2019-02-07 12:03:25 | under 题解 |

刘汝佳大法好!

发现前面的题解都是什么模拟、指针、STL什么的

所以我来这里介绍一波刘汝佳大法:

  • 用数组模拟链表,对于每一个字符存一个next值表示下一个元素的下标

  • 对于字符[,将当前下标改为0

  • 对于字符],将当前下标改为last就是我们存的最后的下标

  • 对于其他字符,更新next即可

附代码:

#include <bits/stdc++.h>
using namespace std;
char s[100005];
int last,now,nxt[100005];
int main(){
    while(~scanf("%s",s+1)){
        int n=strlen(s+1);
        last=0;
        now=0;
        nxt[0]=0;
        for(int i=1;i<=n;i++){
            char ch=s[i];
            if(ch=='[')now=0;
            else if(ch==']')now=last;
            else{
                nxt[i]=nxt[now];
                nxt[now]=i;
                if(now==last)last=i;
                now=i;
            }
        }
        for(int i=nxt[0];i!=0;i=nxt[i])printf("%c",s[i]);
        printf("\n");
    }
    return 0;
}