残损的键盘(又名:悲剧文本)(Broken Keyboard(a.k.a Beiju Text),UVa11988)题解

偏执的太偏执、 2022-12-28 07:22 130阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入
     *  输出
 *  原题（PDF）
 *   *  算法分析
     *  解题标程( C )
     *  解题标程(CPP)
     *  错题总结

--------------------

# 题目描述 #

你在输入文章的时候，键盘上的Home键和End键出了问题，会不定时的按下。你却不知道此问题，而是专心致志地打稿子，甚至显示器都没开。当你打开显示器之后，展现你面前的数一段悲剧文本。你的任务是在显示器打开前计算出这段悲剧的文本。 给你一段按键的文本，其中’\[‘表示Home键，’\]'表示End键，输入结束标志是文件结束符（EOF）。  
输出一行，即这段悲剧文本。

输入包含多组数据，每组数据占一行，包含不超过100000个字母、下划线、字符"\[“或者”\]"。

## 输入 ##

This_is_a_[Beiju]_text  
    [[\]\][][]Happy_Birthday_to_Tsinghua_University

## 输出 ##

BeijuThis_is_a__text  
    Happy_Birthday_to_Tsinghua_University

--------------------

# 原题（PDF） #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]

--------------------

## 算法分析 ##

最简单的方法就是用**数组去存储**每次在首位输出的串和末尾的串，然后频繁的将尾部串strcat连接到首位串中，但是这样的**算法会超时**  
因此我们这里采用**链表**。  
*在C语言的算法中用数组来模拟链表，而CPP中可以直接使用STL中的list容器加上list迭代器解决问题*  
这里着重讲一下C语言的算法，用next数组去存储当前字符的下一位下标比如，next\[1\]=2,就意味着指向下标为2的字符，我们需要将next\[0\]单独拿出来作为没有数据存储的“头节点”，因此串s要的有效范围为1～n，并且用cur变量来记录光标位置，用last来记录当前的尾部位置，光标始终在s\[cur\]的右边。

*  当s\[i\]==’\['时，光标cur=0，光标到首部
 *  当s\[i\]==’\]'时，光标cur=last，光标到末尾
 *  当s\[i\]为字符时，根据光标的位置（模拟尾插法）next\[i\]=next\[cur\];next\[cur\]=i 然后让光标等于i，去处理下一个i，如果尾部和光标位置相同意味着最近的控制字符为’\]’，则尾部也同样移向i的位置。

## 解题标程( C ) ##

#include <stdio.h>
    using namespace std;
    #define maxl 100005
    
    int main()
    {
        
        char s[maxl];
        while(~scanf("%s",s+1))
        {
        
            int Next[maxl]={
        0};
            int cur=0,last=0;
    
            for (int i = 1; s[i]; ++i)
            {
        
                if(s[i]=='[')    cur=0;
                else if(s[i]==']')    cur=last; //last会停止在[的左边一个字符，让光标cur回到last来继续链接
                else
                {
        
                    //链表插入操作（就类似于尾插法）
                    Next[i]=Next[cur];  //（令i的后续等于cur的后续，i始终是大于cur的）（类似于p->next=l->next）
                    Next[cur]=i;  //（令cur的后续等于i）（类似与l->next=p）
    
                    //last的更新
                    if(cur==last)    last=i;
                    //cur的更新
                    cur=i;
                }
            }
    
            for (int i = Next[0]; i != 0; i = Next[i])
                if (s[i]!='['&&s[i]!=']')
                    printf("%c",s[i]);
            printf("\n");
        }
        return 0;
    }

## 解题标程(CPP) ##

#include <cstdio>
    #include <cstring>
    #include <list>
    #include <iostream>
    using namespace std;
    int main()
    {
        
        char str[100005];
        list <char> s;
        while (scanf("%s",str)!=EOF)
        {
        
            list <char>::iterator it=s.begin();
            int n=strlen(str);
            for (int i=0;i<n;i++)
            {
        
                char ch=str[i];
                if (ch=='[') it=s.begin();
                else if(ch==']') it=s.end();
                else
                {
        
                    it=s.insert(it,ch);
                    it++;
                }
            }
            for (it=s.begin();it!=s.end();it++)
                printf("%c",*it);
            s.clear();
            printf("\n");
        }
        return 0;
    }

--------------------

## 错题总结 ##

*  在数组中频繁移动元素是很低效的，如有可能，可以使用链表

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]: /images/20221120/b842085a53764630b328f802417ed2fa.png