这一题是TsingHua OJ上的一道题目，学堂在线的一位数据结构老师的题目(原创)，所以我直接把题目先贴下来了，这道题对复习双向链表很有帮助，而且也对数据结构中List，也就是对列表的回顾也是很有帮助的。

祖玛(Zuma)

描述

祖玛是一款曾经风靡全球的游戏，其玩法是：在一条轨道上初始排列着若干个彩色珠子，其中任意三个相邻的珠子不会完全同色。此后，你可以发射珠子到轨道上并加入原有序列中。一旦有三个或更多同色的珠子变成相邻，它们就会立即消失。这类消除现象可能会连锁式发生，其间你将暂时不能发射珠子。

开发商最近准备为玩家写一个游戏过程的回放工具。他们已经在游戏内完成了过程记录的功能，而回放功能的实现则委托你来完成。

游戏过程的记录中，首先是轨道上初始的珠子序列，然后是玩家接下来所做的一系列操作。你的任务是，在各次操作之后及时计算出新的珠子序列。

输入

第一行是一个由大写字母'A'~'Z'组成的字符串，表示轨道上初始的珠子序列，不同的字母表示不同的颜色。

第二行是一个数字n，表示整个回放过程共有n次操作。

接下来的n行依次对应于各次操作。每次操作由一个数字k和一个大写字母Σ描述，以空格分隔。其中，Σ为新珠子的颜色。若插入前共有m颗珠子，则k ∈ [0, m]表示新珠子嵌入之后（尚未发生消除之前）在轨道上的位序。

输出

输出共n行，依次给出各次操作（及可能随即发生的消除现象）之后轨道上的珠子序列。

如果轨道上已没有珠子，则以“-”表示。

Example

Input

ACCBA

5

1 B

0 A

2 B

4 C

0 A

Output

ABCCBA

AABCCBA

AABBCCBA

-

A

限制

0 ≤ n ≤ 10^4

0 ≤ 初始珠子数量 ≤ 10^4

时间：2 sec

内存：256 MB

解题思路：

　　这道题考察的就是大家对列表的理解和DIY重构能力，模拟Zuma这一远近闻名的游戏中的色块序列。

　　我们来回顾一下数据结构的两个基本结构向量(vetor)和列表(List)，这两个数据结构非常类似，但是两种结构的优势和构造却也有很大差距，Vetor实质就是一个可以动态增长空间的数组，也就是通俗的动态数组，可以方便得对数据进行动态管理。

　　但是Vetor相对于List却让人觉得有些静态了，因为List的实质是一个双向链表，因此可以比Vetor更加高效得insert或者delete数据，但是List不能随意查询到其中的数据，需要通过指针一次次得遍历查找，即便可以从首部或者尾部查找，但总得来说，每一次遍历的时间度依然是O(n)。

　　Ps：另外有一个特别注意的地方，当数据量比较大的时候，每次输出都会调用一次I/O接口(即printf OR cout)，这样会造成大量调用，如果按照最坏情况，最大数组有20000个字符，最大输出有10000次，因此调用量可能会达到10^8次，如此大的调用量显然会在数据极端的时候爆出TLE，因此我们也应该对I/O调用的次数也要优化，我这里直接用一个非常大的数组存储所有情况，直到最后输出。

　　如果没有这个优化，在TsingHhua OJ上只能通过95%的数据，最后一个测试用例是过不了的。

　　Ps：然后注意数据中输入序列可以为空。(length==0的情况刚开始一直没注意，所以第二个测试用例一直过不了。。。ヾ(｡｀Д´｡)，做这道题就因为这个耗时一小时啊！！)

　　　　所以注意输入数据的时候用gets()之类读取行字符的函数。

　Ok，贴Code！

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 #define MAX 200000000

 /*祖玛色块类*/

 struct Zuma{

     char date;

     Zuma *up;

     Zuma *down;

     Zuma(){};

     Zuma(char s):date(s){};

 }*header,*tailer;    //首尾哨兵

 char s[MAX];

 int length;    //链表长度

 int k;    //记录数据长度

 /*双向链表-尾插法*/

 void Creat_zuma(char *s)

 {

     header = new Zuma();

     header->up = NULL;

     Zuma *rear = header;    //定义尾部指针-穿针

     for (int i = ; i < length; i++)

     {

         Zuma *p = new Zuma(s[i]);

         rear->down = p;

         p->up = rear;

         rear = p;    //换针

     }

     tailer = new Zuma();

     rear->down = tailer;

     tailer->up = rear;

     tailer->down = NULL;

 }

 /*遍历查找pos位置的指针*/

 Zuma* Find(int pos)

 {

     int counter = ;

     Zuma *p = header;

     if (length - pos >= pos)    //首部遍历

     {

         while (counter < pos && p->down != tailer)

         {

             p = p->down;

             counter++;

         }

     }

     else{                        //尾部遍历

         p = tailer;

         counter = length;

         while (counter >= pos && p->up != header)

         {

             p = p->up;

             counter--;

         }

     }

     return p;

 }

 /*消除*/

 Zuma* Remove(Zuma *cur,char c)

 {

     while ()

     {

         Zuma *pre = cur->down;

         int counter = ;

         while (cur != header && cur->date == c)    //向前查重

         {

             cur = cur->up;

             counter++;

         }

         while (pre != tailer && pre->date == c)    //向后查重

         {

             pre = pre->down;

             counter++;

         }

         if (counter >= )    //重复元素大于三个

         {

             length -= counter;

             Zuma *p1 = cur->down, *p2;

             while (p1 != pre)    //delete

             {

                 p2 = p1->down;

                 delete p1;

                 p1 = p2;

             }

             cur->down = pre;

             if (pre != NULL)

                 pre->up = cur;

             c = cur->date;

         }

         else break;

     }

     return cur;

 }

 /*插入*/

 void Insert(Zuma *p, char c)

 {

     Zuma *x = new Zuma(c);

     if (p->down != NULL)

     {

         x->up = p;

         x->down = p->down;

         p->down->up = x;

         p->down = x;

     }

     else{

         x->up = p;

         x->down = NULL;

         p->down = x;

     }

     length++;

 }

 int main()

 {

     int n;

     gets(s);

     scanf("%d", &n);

     length = strlen(s);

     /*搭建*/

     Creat_zuma(s);

     for (int t = ; t < n; t++)

     {

         char c[];

         int pos;

         scanf("%d%s", &pos, &c);

         Zuma *p = Find(pos);

         Insert(p, c[]);

         Zuma *flag = Remove(p, c[]);

         /*Record*/

         if (flag == header && flag->down == tailer)

         {

             s[k++] = '-';

             s[k++] = '\n';

         }

         else{

             flag = header;

             while (flag->down != tailer)

             {

                 s[k++] = flag->down->date;

                 flag = flag->down;

             }

             s[k++] = '\n';

         }

         /*Single Input*/

         if (t == n - )

         {

             s[k] = '\0';

             printf("%s", s);

             k = ;

         }

     }

     return ;

 }

巴特西

ACM/ICPC 之双向链表_构造列表-模拟祖玛 (TSH OJ-Zuma(祖玛))

这一题是TsingHua OJ上的一道题目，学堂在线的一位数据结构老师的题目(原创)，所以我直接把题目先贴下来了，这道题对复习双向链表很有帮助，而且也对数据结构中List，也就是对列表的回顾也是很有帮助的。

祖玛(Zuma)

描述

输入

输出

Example

限制

最新文章

热门文章

巴特西

ACM/ICPC 之 双向链表_构造列表-模拟祖玛 (TSH OJ-Zuma(祖玛))

这一题是TsingHua OJ上的一道题目，学堂在线的一位数据结构老师的题目(原创)，所以我直接把题目先贴下来了，这道题对复习双向链表很有帮助，而且也对数据结构中List，也就是对列表的回顾也是很有帮助的。

祖玛(Zuma)

描述

输入

输出

Example

限制

最新文章

热门文章

ACM/ICPC 之双向链表_构造列表-模拟祖玛 (TSH OJ-Zuma(祖玛))