ACM/ICPC 算法锻炼 之双向链表_构造列表-模拟祖玛 (TshingHua OJ-Zuma(祖玛))
这一题是TshingHua OJ上的一道题目，学堂在线的一位数据结构老师的题目(原创)，所以我直接把题目先贴下来了，这道题对复习双向链表很有帮助，而且也对数据结构中List，也就是对列表的回顾也是很有帮助的。
祖玛(Zuma)
Description
Let's play the game Zuma!
There are a sequence of beads on a track at the right beginning. All the beads are colored but no three adjacent ones are allowed to be with a same color. You can then insert beads one by one into the sequence. Once three (or more) beads with a same color become adjacent due to an insertion, they will vanish immediately.
Note that it is possible for such a case to happen for more than once for a single insertion. You can't insert the next bead until all the eliminations have been done.
Given both the initial sequence and the insertion series, you are now asked by the fans to provide a playback tool for replaying their games. In other words, the sequence of beads after all possible eliminations as a result of each insertion should be calculated.
Input
The first line gives the initial bead sequence. Namely, it is a string of capital letters from 'A' to 'Z', where different letters correspond to beads with different colors.
The second line just consists of a single interger n, i.e., the number of insertions.
The following n lines tell all the insertions in turn. Each contains an integer k and a capital letter Σ, giving the rank and the color of the next bead to be inserted respectively. Specifically, k ranges from 0 to m when there are currently m beads on the track.
Output
n lines of capital letters, i.e., the evolutionary history of the bead sequence.
Specially, "-" stands for an empty sequence.
Example
Input
ACCBA
5
1 B
0 A
2 B
4 C
0 A
Output
ABCCBA
AABCCBA
AABBCCBA
-
A
Restrictions
0 <= n <= 10^4
0 <= length of the initial sequence <= 10^4
Time: 2 sec
Memory: 256 MB
Hints
List
描述
祖玛是一款曾经风靡全球的游戏，其玩法是：在一条轨道上初始排列着若干个彩色珠子，其中任意三个相邻的珠子不会完全同色。此后，你可以发射珠子到轨 道上并加入原有序列中。一旦有三个或更多同色的珠子变成相邻，它们就会立即消失。这类消除现象可能会连锁式发生，其间你将暂时不能发射珠子。
开发商最近准备为玩家写一个游戏过程的回放工具。他们已经在游戏内完成了过程记录的功能，而回放功能的实现则委托你来完成。
游戏过程的记录中，首先是轨道上初始的珠子序列，然后是玩家接下来所做的一系列操作。你的任务是，在各次操作之后及时计算出新的珠子序列。
输入
第一行是一个由大写字母'A'~'Z'组成的字符串，表示轨道上初始的珠子序列，不同的字母表示不同的颜色。
第二行是一个数字n，表示整个回放过程共有n次操作。
接下来的n行依次对应于各次操作。每次操作由一个数字k和一个大写字母Σ描述，以空格分隔。其中，Σ为新珠子的颜色。若插入前共有m颗珠子，则k ∈ [0, m]表示新珠子嵌入之后（尚未发生消除之前）在轨道上的位序。
输出
输出共n行，依次给出各次操作（及可能随即发生的消除现象）之后轨道上的珠子序列。
如果轨道上已没有珠子，则以“-”表示。
样例
见英文题面
限制
0 ≤ n ≤ 10^4
0 ≤ 初始珠子数量 ≤ 10^4
时间：2 sec
内存：256 MB
提示
列表
话说最下面的Hint来一句提示居然就是列表，小生表示一直没注意啊！！
解题思路：
这道题考察的就是大家对列表的理解和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调用的次数也要优化，我这里直接用一个非常大的数组存储所有情况，直到最后输出。
如果没有这个优化，在TshingHhua OJ上只能通过95%的数据，最后一个测试用例是过不了的。
Ps：然后注意数据中输入序列可以为空。(length==0的情况刚开始一直没注意，所以第二个测试用例一直过不了。。。ヾ(｡｀Д´｡)，做这道题就因为这个耗时一小时啊！！)
所以注意输入数据的时候用gets()之类读取行字符的函数。
Ok，贴Code！
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 6 #define MAX 200000000 7 8 /*祖玛色块类*/ 9 struct Zuma{ 10 char date; 11 Zuma *up; 12 Zuma *down; 13 Zuma(){}; 14 Zuma(char s):date(s){}; 15 }*header,*tailer; //首尾哨兵 16 17 char s[MAX]; 18 int length; //链表长度 19 int k; //记录数据长度 20 21 /*双向链表-尾插法*/ 22 void Creat_zuma(char *s) 23 { 24 header = new Zuma(); 25 header->up = NULL; 26 27 Zuma *rear = header; //定义尾部指针-穿针 28 for (int i = 0; i < length; i++) 29 { 30 Zuma *p = new Zuma(s[i]); 31 rear->down = p; 32 p->up = rear; 33 34 rear = p; //换针 35 } 36 tailer = new Zuma(); 37 rear->down = tailer; 38 tailer->up = rear; 39 tailer->down = NULL; 40 } 41 42 /*遍历查找pos位置的指针*/ 43 Zuma* Find(int pos) 44 { 45 int counter = 0; 46 Zuma *p = header; 47 if (length - pos >= pos) //首部遍历 48 { 49 while (counter < pos && p->down != tailer) 50 { 51 p = p->down; 52 counter++; 53 } 54 } 55 else{ //尾部遍历 56 p = tailer; 57 counter = length; 58 while (counter >= pos && p->up != header) 59 { 60 p = p->up; 61 counter--; 62 } 63 } 64 return p; 65 } 66 67 /*消除*/ 68 Zuma* Remove(Zuma *cur,char c) 69 { 70 while (1) 71 { 72 Zuma *pre = cur->down; 73 int counter = 0; 74 while (cur != header && cur->date == c) //向前查重 75 { 76 cur = cur->up; 77 counter++; 78 } 79 while (pre != tailer && pre->date == c) //向后查重 80 { 81 pre = pre->down; 82 counter++; 83 } 84 if (counter >= 3) //重复元素大于三个 85 { 86 length -= counter; 87 Zuma *p1 = cur->down, *p2; 88 while (p1 != pre) //delete 89 { 90 p2 = p1->down; 91 delete p1; 92 p1 = p2; 93 } 94 cur->down = pre; 95 if (pre != NULL) 96 pre->up = cur; 97 c = cur->date; 98 } 99 else break; 100 } 101 return cur; 102 } 103 104 /*插入*/ 105 void Insert(Zuma *p, char c) 106 { 107 Zuma *x = new Zuma(c); 108 if (p->down != NULL) 109 { 110 x->up = p; 111 x->down = p->down; 112 p->down->up = x; 113 p->down = x; 114 } 115 else{ 116 x->up = p; 117 x->down = NULL; 118 p->down = x; 119 } 120 length++; 121 } 122 int main() 123 { 124 int n; 125 gets(s); 126 scanf("%d", &n); 127 length = strlen(s); 128 /*搭建*/ 129 Creat_zuma(s); 130 131 for (int t = 0; t < n; t++) 132 { 133 char c[2]; 134 int pos; 135 scanf("%d%s", &pos, &c); 136 137 Zuma *p = Find(pos); 138 Insert(p, c[0]); 139 Zuma *flag = Remove(p, c[0]); 140 /*Record*/ 141 if (flag == header && flag->down == tailer) 142 { 143 s[k++] = '-'; 144 s[k++] = '\n'; 145 } 146 else{ 147 flag = header; 148 while (flag->down != tailer) 149 { 150 s[k++] = flag->down->date; 151 flag = flag->down; 152 } 153 s[k++] = '\n'; 154 } 155 /*Single Input*/ 156 if (t == n - 1) 157 { 158 s[k] = '\0'; 159 printf("%s", s); 160 k = 0; 161 } 162 } 163 return 0; 164 }