首页 > 其他 > 详细

Uva11988 Broken Keyboard (a.k.a. Beiju Text)

时间:2017-09-21 17:27:58      阅读:218      评论:0      收藏:0      [点我收藏+]

题目链接:传送门

分析:涉及到大量元素移动的题,如果用数组来保存,每一次修改操作一定会超时,解决这个问题的方法就是用链表,记录每个元素的下一个元素是啥,插入元素的过程:假设有i,j,我们要在i,j之间插入k,那么k的下一个就是i的下一个,i个下一个就变成了k,这道题遇到[或者]移动当前要插入的位置就好了.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

char s[100010];
int nextt[100010], cur,last;

int main()
{
    while (scanf("%s", s + 1) == 1)
    {
        cur = nextt[0] = last =0;
        int sizee = strlen(s + 1);
        for (int i = 1; i <= sizee; i++)
        {
            if (s[i] == [)
                cur = 0;
            else
                if (s[i] == ])
                cur = last;
                else
                {
                    nextt[i] = nextt[cur];
                    nextt[cur] = i;
                    if (cur == last)
                        last = i;
                    cur = i;
                }
        }
        for (int i = nextt[0]; i; i = nextt[i])
            printf("%c", s[i]);
        printf("\n");
    }

    return 0;
}

 

Uva11988 Broken Keyboard (a.k.a. Beiju Text)

原文:http://www.cnblogs.com/zbtrs/p/7569453.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!