首页 > 代码库 > 【Tsinghua OJ】祖玛(Zuma)问题
【Tsinghua OJ】祖玛(Zuma)问题
描述
祖玛是一款曾经风靡全球的游戏，其玩法是：在一条轨道上初始排列着若干个彩色珠子，其中任意三个相邻的珠子不会完全同色。此后，你可以发射珠子到轨 道上并加入原有序列中。一旦有三个或更多同色的珠子变成相邻，它们就会立即消失。这类消除现象可能会连锁式发生，其间你将暂时不能发射珠子。
开发商最近准备为玩家写一个游戏过程的回放工具。他们已经在游戏内完成了过程记录的功能，而回放功能的实现则委托你来完成。
游戏过程的记录中，首先是轨道上初始的珠子序列，然后是玩家接下来所做的一系列操作。你的任务是，在各次操作之后及时计算出新的珠子序列。
输入
第一行是一个由大写字母‘A‘~‘Z‘组成的字符串，表示轨道上初始的珠子序列，不同的字母表示不同的颜色。
第二行是一个数字n，表示整个回放过程共有n次操作。
接下来的n行依次对应于各次操作。每次操作由一个数字k和一个大写字母Σ描述，以空格分隔。其中，Σ为新珠子的颜色。若插入前共有m颗珠子，则k ∈ [0, m]表示新珠子嵌入之后（尚未发生消除之前）在轨道上的位序。
输出
输出共n行，依次给出各次操作（及可能随即发生的消除现象）之后轨道上的珠子序列。
如果轨道上已没有珠子，则以“-”表示。
输入样例
ACCBA51 B0 A2 B4 C0 A
输出样例
ABCCBAAABCCBAAABBCCBA-A
限制
0 ≤ n ≤ 10^4
0 ≤ 初始珠子数量 ≤ 10^4
时间：2s，内存：256MB
提示
列表
【Solution】
先贴源码：
1 #include <stdio.h> 2 #include "string.h" 3 #include <stdlib.h> 4 5 typedef char ElemType; 6 typedef struct node 7 { 8 ElemType data; 9 struct node *next; 10 struct node *front; 11 }List, *pList; 12 13 pList pHead = (pList)malloc(sizeof(List)); 14 pList pTail = (pList)malloc(sizeof(List)); 15 16 void creat(char *a, int n) 17 { 18 int i; 19 pList pt = pHead; 20 21 pTail->front = pHead; 22 pTail->next = NULL; 23 pHead->next = pTail; 24 pHead->front = NULL; 25 pHead->data = http://www.mamicode.com/pTail->data = ‘-‘; 26 27 for (i = 0; i < n; i++) 28 { 29 pList pNew = (pList)malloc(sizeof(List)); 30 pNew->data =http://www.mamicode.com/ a[i]; 31 pNew->front = pt; 32 pNew->next = pt->next; 33 pt->next->front = pNew; 34 pt->next = pNew; 35 pt = pNew; 36 } 37 } 38 39 void insert(int m, char ch) 40 { 41 int i = -1; 42 pList pt = pHead, pNew = (pList)malloc(sizeof(List)); 43 44 while (i++ < m) pt = pt->next; 45 46 pNew->data =http://www.mamicode.com/ ch; 47 pNew->next = pt; 48 pNew->front = pt->front; 49 pt->front->next = pNew; 50 pt->front = pNew; 51 } 52 53 void del(int m) 54 { 55 pList p1 = NULL, p2 = NULL, p3 = NULL, p4 = NULL, pt = pHead; 56 pList begin = pHead, end = pTail; 57 bool boo = true; 58 int repeat, i = -1; 59 60 // find position 61 while (i++ < m - 2) pt = pt->next; 62 63 //init for ‘begin‘ and ‘end‘ 64 begin = pt; end = pt; i = 0; 65 while (i++ < 4 && end->next != pTail) end = end->next; 66 67 while (boo && pt != pTail) 68 { 69 boo = false; repeat = 1; 70 while (pt != end) 71 { 72 pt = pt->next; 73 74 if (pt->front->data =http://www.mamicode.com/= pt->data) repeat++; 75 else repeat = 1; 76 77 if (repeat == 3) 78 { 79 boo = true; 80 if (pt->data =http://www.mamicode.com/= pt->next->data) 81 { 82 repeat++; 83 pt = pt->next; 84 } 85 86 if (repeat == 3) 87 { 88 p3 = pt; p2 = p3->front; p1 = p2->front; 89 p1->front->next = p3->next; 90 p3->next->front = p1->front; 91 pt = pt->next; 92 delete p1; delete p2; delete p3; 93 } 94 else 95 { 96 p4 = pt; p3 = p4->front; p2 = p3->front; p1 = p2->front; 97 p1->front->next = p4->next; 98 p4->next->front = p1->front; 99 pt = pt->next;100 delete p1; delete p2; delete p3; delete p4;101 }102 103 break;104 }105 }106 107 if (boo && pt != pTail)108 {109 begin = pt; i = 0;110 while (i++ < 2 && begin->front != pHead) begin = begin->front;111 end = pt; i = 0;112 if (i++ < 1 && end->next != pTail) end = end->next;113 pt = begin;114 }115 }116 }117 118 void show()119 {120 pList pt = pHead->next;121 122 if (pt == pTail) printf("-");123 else124 {125 while (pt->next != NULL)126 {127 printf("%c", pt->data);128 pt = pt->next;129 }130 }131 132 printf("\n");133 }134 135 int main(void)136 {137 char a[10005];138 int n, k;139 pList pHead = NULL;140 141 gets(a);142 scanf("%d\n", &n);143 144 creat(a, strlen(a));145 146 for (k = 0; k < n; k++)147 {148 int m;149 char ch;150 151 scanf("%d ", &m);152 do153 {154 ch = getchar();155 } while (!((ch >= ‘A‘) && (ch <= ‘Z‘)));156 157 // insert ch158 insert(m, ch); 159 160 // delete all 3-same block, making it the right string161 del(m);162 163 // print the string164 show();165 }166 167 return 0;168 }
可以过 Tsinghua OJ 95%的数据，最后一个点超时，听说要把缓存区调大才能过，暂时无解。
这一类题属于模拟题，也就是按照题意一步一步模拟操作即可，对现实事物的合理抽象以及模拟操作的效率是解决问题的关键。
要注意的几个点：
1、注意列表与向量数据结构的差别。向量可以直接 “循秩访问(call-by-rank)”，所以对于查找操作是O(1)的，插入和删除都是O(n)的，对于二分查找等这样十分依赖于“秩”的算法很重要；而列表是“循位置访问(call-by-position)”，所以对于 插入、删除都是O(1)的操作，而查找操作是O(n)的。要充分注意它们的特点。实际上，对于这道题，虽然提示里写了“列表”，由于每次都要遍历输出和查找，已经是O(n)的了，不见得比用向量做会快多少。
2、列表处理的一个特别好的小技巧：在列表的前面和后面各放置一个哨兵，如果把列表比作一条“绳子”，那么就相当于两头各放置一个手抓的地方，这样无论列表内部会有哪些动态操作（即改变本身结构的操作，比如插入删除，而相应的查找等不改变自己结构的操作则称为静态操作），都可以从一而终地从两头把列表给“拉”出来。好处在于，有很多需要考虑边界情况的问题可以自动化的化为一般化的处理。之前做这道题并未这样考虑的结果就是代码里面各种判断是否为NULL以防止边界情况出错，有了哨兵这样的判断很多时候可以一般化处理，判断大大减少。同时也防止了越界错误的放生。
3、像Python那样，总是从一而终地考虑[a, b)这样的左闭右开区间是很有必要的，即区间左界桩总是被问题范围所包含，而右界桩在当前状态则不被包含。它可以大大的减少你思考问题的复杂度。遵循统一的标准也减少了犯错的可能。
4、同样，对于列表所对应的具体的数据结构链表，总是要尤其注意边界情况。要注意的是：抽象数据类型是对数据结构更高层次的抽象。它是一种抽象定义，表现为逻辑上的特征和一些基本操作及语义，并不涉及数据的具体存储方式。比如向量和列表。最常见的对应于这两种抽象数据类型的具体数据类型也就是 数组 和 链表了。抽象有利于定义统一的借口和规范以便更一般化的归纳、使用和处理。
5、对于这道题，自己的一点小优化：
考虑到每次需要删除的部分一定包含插入点，所以每次删除的时候就直接定位到插入点以及它附近。
假设 插入点是k，第一次则考察k-2~k+2这五个点，
假设 有删除操作，设删除区段的后继元素为m，
之后考察 m-2 ~ m+1这四个点。
重复以上两步直到扫描这个区间不再有删除操作。
这样就不需要每次都扫描整个列表来判断需不需要删除了。
这一切都基于，列表的“微创切除手术”只可能发生在插入点附近，并且一定包含插入点。
【Tsinghua OJ】祖玛(Zuma)问题