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

难点：

1. 对逻辑关系的分析以及对细节的把握

其中最关键的突破点当属引入cur（光标位置）以及last（文末位置）

这样一来完全无需分类讨论那样的蒟蒻办法

这种思想相当于从特殊到一般找到一个一般化的通用方法所有情形都适用

in this case, 不论是'['(Home)后、']'(End)后共同点是都要往光标所在处插入最后end时再回到文末继续打字

this is actually a common sense method, but it is very clever!

解决了这个问题后剩下只用细心一点写链表插入了

#include <cstdio>
#include <cstring>
using namespace std;
char s[100005];
int next[100005];
int main(){
    int cur,len,last,i;
    while(scanf("%s",s+1)!=EOF){
        memset(next,0,sizeof(next));
        next[0]=0; //NOT next[0]=1!!! (what if the first char is '[')
        cur=0; //光标位置
        last=0; //文末位置
        len=strlen(s+1); //s默认从下标0开始 但我们需要从1开始 
        for(i=1;i<=len;i++){ 
            if(s[i]=='[')cur=0; 
            else if(s[i]==']')cur=last;
            else{
                next[i]=next[cur];
                next[cur]=i;
                //标准的链表元素插入 
                if(cur==last)last=i;
                cur=i; 
            }
        }
        for(i=next[0]; i!=0; i=next[i]) //标准的链表元素输出 
         printf("%c",s[i]);
        printf("
");
    }
    return 0;
}

盲点：

1. 1-based string读入方法及长度计算：

scanf("%s",s+1);
len=strlen(s+1);
for(i=1;i<=len;i++){
    s[i]...
}

2. next[0]=0而不是next[0]=1

s[o]这个虚拟位置不能与s[1]相连

否则在遇到s[1]='['时会出错

拓展练习：删除链表内元素

Open Judge 6378

山人不禁吐槽红字骗人！！！

不过练手为主刷题为辅

#include <cstdio>
using namespace std;
int a[200005],next[200005],prev[200005];
int main(){
    int n,i,m;
    scanf("%d",&n);
    next[0]=1;
    for(i=1;i<=n;i++){
        scanf("%d",&a[i]);
        prev[i]=i-1;
        next[i]=i+1;
    }
    next[n]=0; //necessary to avoid the extra '0' 
               //最后一个元素不能往后连 
    scanf("%d",&m);
    for(i=1;i<=n;i++){
        if(a[i]==m){
            next[prev[i]]=next[i];
            prev[next[i]]=prev[i];
            next[i]=0;
            //标准的列表元素删除 
            //analogy:牵手 
        }
    }
    for(i=next[0]; i!=0; i=next[i]) //标准的链表元素输出 
     printf("%d ",a[i]);
    return 0;
}

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

相关推荐