温馨提示：本题为深大OJ原题，深大的同学请勿直接抄袭，以免出现多个代码相同以致评0分的情况，代码和思路仅供参考，希望大家能逐步成长。
题目描述
祖玛是一款曾经风靡全球的游戏，其玩法是：在一条轨道上初始排列着若干个彩色珠子，其中任意三个相邻的珠子不会完全同色。此后，你可以发射珠子到轨道上并加入原有序列中。一旦有三个或更多同色的珠子变成相邻，它们就会立即消失。这类消除现象可能会连锁式发生，其间你将暂时不能发射珠子。
给定轨道上初始的珠子序列，然后是玩家所做的一系列操作。你的任务是，在各次操作之后及时计算出新的珠子序列。
输入
第一行是一个由大写字母'A'~'Z'组成的字符串，表示轨道上初始的珠子序列，不同的字母表示不同的颜色。
第二行是一个数字n，表示玩家共有n次操作。
接下来的n行依次对应于各次操作。每次操作由一个数字k和一个大写字母描述，以空格分隔。其中，大写字母为新珠子的颜色。若插入前共有m颗珠子，位置0-m-1，则k ∈ [0, m]表示新珠子嵌入在轨道上的位置。
输出
输出共n行，依次给出各次操作（及可能随即发生的消除现象）之后轨道上的珠子序列。
如果轨道上已没有珠子，则以“-”表示。
输入样例1
ACCBA 5 1 B 0 A 2 B 4 C 0 A
输出样例1
ABCCBA AABCCBA AABBCCBA - A
思路分析
原本想用list容器做的，发现它不是很好用，还是用自己写的List吧。
这道题关键在于消除，首先要注意到是三个或三个以上都能消，所以去判断连续三个或四个甚至五个的方法是不行的，所以我的解决方法是先去数有多少个相同的，大于等于三个的才去消除，因为有可能会出现连环反应，所以必须写成循环，每次先判断有没有大于等于三个的，消除到没有再退出循环。
AC代码
代码语言：javascript复制#include <iostream>
using namespace std;
class Node {
public:
char data;
Node * next = NULL;
};
class List {//带头结点的单链表，位置从0到n，0是头结点，1是首结点，n是尾结点
public:
Node * head; //头结点
int size; //表长
List(); //构造函数，创建头结点
~List(); //析构函数，逐个结点回收
int Insert(char item, int i); //第i位置插入元素，操作成功或失败返回OK或ERROR
void print();//打印单链表所有数据
int get(int i) {
Node*p = head->next;
int j = 1;
while (j < i) {
p = p->next;
}
return p->data;
}
int del(int i) {
Node*p = head, *q = head->next;
int j = 1;
while (j < i) {
p = p->next;
q = q->next;
}
p->next = q->next;
delete q;
size--;
return 0;
}
int same(int i) {
int count = 1;
Node*p = head->next;
int j = 1;
while (j < i) {
p = p->next;
}
while (p && p->next) {
if (p->data == p->next->data) {
count ;
p = p->next;
} else break;
}
return count;
}
};
List::List(): size(0) {
head = new Node();
}
List::~List() {
Node *p, *q;
p = head->next;
while (p != NULL) {
q = p;
p = p->next;
delete q;
}
size = 0;
head->next = NULL;
}
int List::Insert(char item, int i) {
Node*p = head;
int j = 0;
while (j < i) {
p = p->next;
}
Node*q = new Node();
q->data = item;
q->next = p->next;
p->next = q;
size ;
return 0;
}
void List::print() {
Node*p = head->next;
if (p)
for (int i = 1; i <= size; i ) {
cout << p->data;
p = p->next;
} else cout << '-';
cout << endl;
}
void Yezi(List&zuma) {
int flag = 1;
while (flag) {
flag = 0;
for (int i = 1; i < zuma.size - 1; i ) {
int count = zuma.same(i);
if (count > 2) {
flag = 1;
while (count--)
zuma.del(i);
}
}
}
}
int main() {
string temp;
cin >> temp;
List zuma;
for (int i = 0; temp[i]; i )
zuma.Insert(temp[i], i);
int n, pos;
char bead;
cin >> n;
while (n--) {
cin >> pos >> bead;
zuma.Insert(bead, pos);
Yezi(zuma);
zuma.print();
}
}
