祖瑪

【问题描述】

祖玛是一款曾经风靡全球的游戏，其玩法是：在一条轨道上初始排列着若干
个彩色珠子，其中任意三个相邻的珠子不会完全同色。此后，你可以发射珠子到
轨道上并加入原有序列中。一旦有三个或更多同色的珠子变成相邻，它们就会立
即消失。这类消除现象可能会连锁式发生，其间你将暂时不能发射珠子。
开发商最近准备为玩家写一个游戏过程的回放工具。他们已经在游戏内完成
了过程记录的功能，而回放功能的实现则委托你来完成。
游戏过程的记录中，首先是轨道上初始的珠子序列，然后是玩家接下来所做
的一系列操作。你的任务是，在各次操作之后及时计算出新的珠子序列。

【输入格式】
第一行是一个由大写字母'A'~'Z'组成的字符串，表示轨道上初始的珠子序列，
不同的字母表示不同的颜色。
第二行是一个数字n，表示整个回放过程共有n次操作。
接下来的n行依次对应于各次操作。每次操作由一个数字k和一个大写字母ngs
描述，以空格分隔。其中， ngs为新珠子的颜色。若插入前共有m颗珠子，则k ∈ [0,m]
表示新珠子嵌入之后（尚未发生消除之前）在轨道上的位序。

【输出格式】
输出共n行，依次给出各次操作（及可能随即发生的消除现象）之后轨道上
P74
第 3 页共 6 页
的珠子序列。
如果轨道上已没有珠子，则以“-”表示。

【样例输入】
ACCBA//這裡可以只有一個換行符，So不能用cin。
5
1 B
0 A
2 B
4 C
0 A
【样例输出】
ABCCBA
AABCCBA
AABBCCBA
-
A
【样例解释】
你以为山里又有座庙？//不用管，鐘神在賣萌。
【数据规模与约定】
100%的数据满足1 ≤ n≤ 10 3 ,1 ≤m ≤ 2× 10 3 。

首先，用某種奇技淫巧把初始狀況讀入，存在ch中。使用另一種奇技淫巧消除三個或三個以上連續出現的字符。

注意只有字符被同色彈入值撞擊或間接撞擊或者是字符移動時才能被消除。

代碼實現：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 int n,a,b,c,d,e,l;
 6 char ch[3010],cn;
 7 void gz(int x,char y){
 8 b=x;c=x;
 9 while(ch[b]==y&&b>=0) --b;
10 while(ch[c]==y&&c<l-1) ++c;
11 if(c-b>3){
12 for(int i=1;i<l-c+2;i++) ch[b+i]=ch[c+i-1];
13 l-=c-b-1;
14 gz(b+1,ch[b+1]);//從消除點的後一個搜索。
15 }
16 }
17 void jz(int x,char y){
18 b=x;c=x;
19 while(ch[b]==y&&b>=0) --b;//另一種奇技淫巧。
20 while(ch[c]==y&&c<l-1) ++c;
21 if(c-b>3){
22 for(int i=1;i<l-c+2;i++) ch[b+i]=ch[c+i-1];
23 l-=c-b-1;
24 gz(b+1,ch[b+1]);
25 }
26 }
27 int main(){
28 while(1){//奇技淫巧。
29 scanf("%c",&ch[a]);
30 if(ch[a]=='
') break;
31 a++;
32 }
33 l=strlen(ch);scanf("%d",&n);
34 for(int i=1;i<=n;i++){
35 cin>>a>>cn;l++;
36 for(int i=l;i>a;i--) ch[i]=ch[i-1]; ch[a]=cn;
37 jz(a,cn);
38 if(l==1) printf("-");//空則輸出“-”（其實有一個'
')。
39 for(int i=0;i<l;i++) printf("%c",ch[i]);
40 }
41 return 0;
42 }

View Code

好坑好坑的模擬題~