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

MataGod · 2019-08-07 18:23:36 · 题解

emmmmm，这个做法就是入门经典那本书上一模一样的，写这个题解只是为了让自己确定自己真的看懂了

假如用数组的话 没遇到一次[ ]这个东西就是引起很大的数据移动 觉得会TLE 然后就想能不能用链表来做 这里说的链表并不是用指针实现而是用数组实现的链表。

就是我们用一个数组来存储光标的位置

然后按照光标位置来输出字符就好啦

emmmmmmmmm，我懂了

#include <iostream>
#include <cstdio>
#include <string.h>

using namespace std;

const int maxn = 100000 + 5;
int last;
int cur;
int Next[maxn];
char s[maxn];

int main()
{
    while (scanf("%s", s + 1) == 1)
    {
        int n = strlen(s + 1);
        last = 0;
        cur = 0;
        Next[0] = 0;
        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])
        {
            cout << s[i];
        }
        cout << endl;
    }
    return 0;
}