消除游戏C++（2022年十三届蓝桥杯真题F）
问题描述
在一个字符串 S 中, 如果Si=Si−1 且 Si≠Si+1, 则称 Si和Si+1 为边缘字符。如果 Si ≠Si−1 且 Si =Si+1, 则 Si−1 和 Si 也称为边缘字符。其它的字符 都不是边缘字符。
对于一个给定的串 S, 一次操作可以一次性删除该串中的所有边缘字符 (操作后可能产生新的边缘字符)。
请问经过 2^64 次操作后, 字符串 S 变成了怎样的字符串, 如果结果为空则 输出 EMPTY。
输入格式
输入一行包含一个字符串 S。
输出格式
输出一行包含一个字符串表示答案，如果结果为空则输出 EMPTY。
样例输入 1
edda
样例输出 1
EMPTY
样例输入 2
sdfhhhhcvhhxcxnnnnshh
样例输出 2
s
评测用例规模与约定
对于 25% 的评测用例, ∣S∣≤10^3, 其中∣S∣ 表示 S 的长度;
对于 50%的评测用例, ∣S∣≤10^4;
对于 75% 的评测用例, ∣S∣≤10^5;
对于所有评测用例, ∣S∣≤10^;S 中仅含小写字母。
运行限制
- 最大运行时间：5s
- 最大运行内存: 512M
我的这个代码是参考了蓝桥杯官网的的一位大哥贡献的pass答案，后来我在方思源同学的思路，下对本代码注释。仅供学习参考交流分享，并无其他用途。感谢你们。
先根据样例，手推算一遍。
这里用到前继数组，后继数组。还要容器Vector的知识点，Vector是动态不定长数组，在查找，删除，添加等运算速度比普通的快，因此在计算大数据量时使用可以节省时间。
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e6 + 10;
char s[N];//存储字符串的数组
int l[N], r[N];//前继与后继数组
bool st[N];//存储标记的字符串位置（记录所有位置）值为false为未删除，true为已删除
vector<int>pos;//边缘字符的位置存储在pos容器中
void check(int i)//判断该字符的位置是否越界或者满足相邻字符的条件，若满足，将这两个字符的位置压入pos容器中
{if(s[l[i]] == '?' || s[r[i]] == '?')return;if(s[i] == s[l[i]] && s[r[i]] != s[i])pos.push_back(i), pos.push_back(r[i]);if(s[i] == s[r[i]] && s[i] != s[l[i]])pos.push_back(i), pos.push_back(l[i]);
}
//更新删除元素位置的前继与后继数组，比如说下标 456，将下标为5的元素删除后,将4的后继原本是5，改为6.
//6的前继原本是5，改为4.所以 l[6]=4,r[4]=6
void Remove(int i)
{r[l[i]] = r[i];l[r[i]] = l[i];
}
int main()
{scanf("%s", s + 1);int n = strlen(s + 1);s[0] = s[n + 1] = '?';//将输入的字符串从s[1]开始存储，s[0]和s[n+1]赋值为 '?',作为临界判断条件 for(int i = 1;i <= n;i ++)l[i] = i - 1, r[i] = i + 1;//前继数组与后继数组的初始化 for(int i = 1;i <= n;i ++)check(i);//第一遍对每个字符依次遍历判断是否越界或者为边缘字符 int i = 0;int cnt = 0;//删除元素的个数 while(i < pos.size())//遍历容器pos中要删除的元素 {vector<int>p;//这个容器p是临时的，每次while循环都会初始化为空，它存储的是 每次标记确认要删除元素位置 的前继和后继的位置，//后面再遍历这个容器p里的字符是否为边缘字符，形成循环 for(;i < pos.size();i ++){if(!st[pos[i]])//若st[k]==true，则下标位置k的已经确认被删除，若为false，为未删除 {Remove(pos[i]);//删除元素后调整它的前继和后继的数组 p.push_back(l[pos[i]]);//将删除位置的前继压入容器p中 p.push_back(r[pos[i]]);//将删除位置的后继压入容器p中 st[pos[i]] = true;//将pos[i]位置在st数组中标记为删除 cnt ++;//删除个数+1 }}for(int j = 0;j < p.size();j ++)//对容器p遍历检查刚刚删除字符的 前继和后继 判断是否为边缘字符或者越界 {if(!st[p[j]])check(p[j]);}}if(cnt == n)//若删除数达到输入字符的长度，则全删了，输出为EMPTY{puts("EMPTY");}else{for(int i = 1;i <= n;i ++){if(!st[i])printf("%c", s[i]);}printf("\\n");}return 0;
} 
最后再分享另一份代码，大概能过66.7%的样例。
#include<iostream>
#include<set>
#include<cstring>
using namespace std;
int main()
{set<int>q;string s1,s2;cin>>s1;while(true){for(int i=1; i<s1.length()-1; i++){if(s1[i] == s1[i-1] && s1[i] != s1[i+1]){q.insert(i);q.insert(i+1);}if(s1[i] != s1[i-1] && s1[i] == s1[i+1]){q.insert(i);q.insert(i-1);}}if(q.empty()){cout<<s1;break;}s2.clear();for(int i=0;s1[i]!='\\0';i++){if( q.find(i) == q.end() ) s2 += s1[i];}s1 = s2;q.clear();if(s1.length() == 0){cout<<"EMPTY";break;}}return 0;
}
