蓝桥杯2022年第十三届省赛真题-消除游戏

解题思路:（百度搜的，自己理解了一下）
  题目的2^64是废条件，只需判断一次操作后字符是不变（则以后再操作也不会变）或者为空（则直接输出EMPTY）。

  代码不直接删除字符，而是建立一个isdel数组，若对应下标 i 的字符被删除，则对应isdel[i] = true；由于这样，被删除元素左右两边的元素实际上的下一个或上一个元素就不能再是这个被删除的字符了，则建立前继、后继数组，l[i]为str[i]的左边的字符的下标。

  由于一次操作要把当前字符串的所有边缘字符找到，则不能一边判断一边删除(如令相应isdel为true)，那么就开一个变长数组vector来存放待删除边缘字符的下标，待一次操作完成后，将这些下标对应的isdel变为true。这里的循环也要注意一下，挺独特的，它每次操作完后并没有pop_back掉vector的元素，而是直接 i++并再后面继续累加待删除字符，由于 i 也增加，以后也不会再处理之前未删掉的元素。

注意事项:
注意不要超时。
参考代码:

#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>//strlen、strcmp 
#include <cmath>
#include <algorithm>
using namespace std;

const int Max = 1e+6 + 1;
char str[Max];//字符数组 
bool isdel[Max];//为true，则str[i]删除
vector<int> pos;//边缘字符存在里面待删除 
int l[Max],r[Max];//前继后继，l[i]为str[i]的左边的字符的下标，r[i]为右边，因为其中间可能某些字符被删除，不存在
int len;
void isbian(int i){//判断第i位是否为边缘字符 
if(l[i] == -1 || r[i] == len)//第0位和最后一位的删除是第1位和倒数第二位删除连带了的 
return;
if(str[i] == str[l[i]] && str[i] != str[r[i]]){
pos.push_back(i);
pos.push_back(r[i]);
}
if(str[i] == str[r[i]] && str[i] != str[l[i]]){
pos.push_back(i);
pos.push_back(l[i]);
}
}
void makelr(int i){//删除i后更新l[]、r[] 
r[l[i]] = r[i];
l[r[i]] = l[i];
}
int main() {
scanf("%s",str);
len = strlen(str);
for(int i = 0;i < len;i++){
isdel[i] = false;
l[i] = i-1;
r[i] = i+1;
}
int i,j,cnt = 0;
for(i = 0;i < len;i++){
isbian(i);
}
i = 0;
while(i < pos.size()){
vector<int> p;
for(;i<pos.size();++i){
if(!isdel[pos[i]]){
makelr(pos[i]);
p.push_back(l[pos[i]]);//将删除字符的前继后继放入p中 
p.push_back(r[pos[i]]);//p中元素 待判断是否为边缘字符
//因为一次遍历后，删除这次的边缘字符，删除字符左右的字符的前后继发生变化，其他的字符前后继不变，依然不可能是边缘字符 
isdel[pos[i]] = true;
++cnt;
}
}
for(j = 0;j < p.size();++j){//判断p中元素是否为边缘字符 
if(!isdel[p[j]])
isbian(p[j]);
}
}
if(cnt == len)
puts("EMPTY");
else{
for(i = 0;i < len;i++){
if(!isdel[i])
printf("%c",str[i]);
}
putchar('\n');
}
return 0;
}