问题描述

在一个字符串 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 
#include 
#include 
using namespace std;
typedef pair PII;
const int N = 1e6 + 10;
char s[N];//存储字符串的数组 
int l[N], r[N];//前继与后继数组 
bool st[N];//存储标记的字符串位置（记录所有位置）值为false为未删除，true为已删除 
vectorpos;//边缘字符的位置存储在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中要删除的元素 {vectorp;//这个容器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
#include
#include
using namespace std;
int main()
{setq;string s1,s2;cin>>s1;while(true){for(int i=1; i