Solution
直接模拟
需要关注的问题:
每次删除完边缘字符后,哪些字符会成为新的边缘字符?
只有可能是边缘字符左右两边的字符会成为新的边缘字符,因为其他地方的字符相对关系都没有发生变化,若左右两边的字符也是边缘字符被删掉了的话,就向两边扩展找到没有被删掉的第一个字符就是可能成为新的边缘字符
因此,我们模拟操作的时候,只需要关注“可能成为新的边缘字符”的字符即可,其他的字符不用管
边缘字符的规则:
如果是oox形式的话,那么将中间的o与其右边的x加入待删集合中
如果是xoo形式的话,那么将中间的o与其左边的x加入待删集合中
初始定义字符串里的所有字符都是“有可能成为边缘字符”,加入到备选集合中
想要快速地删掉字符串里的字符,可以用set
,删除效率为$O(nlogn)$;也可以用双链表,删除效率为$O(1)$
这里选择效率更高的双链表来做
讲的比较抽象,详细看代码
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
char s[N];
/*
l表示当前节点左边是谁
r表示当前节点右边是谁
*/
int l[N],r[N]; // 双链表
vector<int> w; //待删的边缘字符用vector来存
vector<int> q; //“有可能成为边缘字符”的集合,即备选集合
bool bz[N]; // 标记当前字符有没有被删掉,即有没有加入到待删集合中
void insert(int k)
{
if (!bz[k]) // 若当前字符没有被删
{
bz[k] = true;
w.push_back(k);
}
}
void filter_dels()
{
w.clear();
for (auto &k: q)
{
//将当前字符k的左右两侧字符取出来(用下标表示)
int a = l[k],b = k,c = r[k];
//判断是否为边缘字符
if (s[a] == s[b] && s[b] != s[c] && s[c] != '#')
{
//将边缘字符加入到待删集合中
insert(b);
insert(c);
} else if (s[a] != '#' && s[a] != s[b] && s[b] == s[c]){
//将边缘字符加入到待删集合中
insert(a);
insert(b);
}
}
}
void remove(int k)
{
// 双链表的删除操作
r[l[k]] = r[k];
l[r[k]] = l[k];
//判断k的左右两边字符是否要加入到备选集合中
//判重很简单,因为是从左到右扫,所以若是重复插入,则一定是当前待删字符左边的字符等于前一个待删字符右边的字符,即备选集合里最后插入的哪个字符
if (!bz[l[k]] && s[l[k]] != '#' && (q.empty() || q.back() != l[k])) q.push_back(l[k]); //若k的左边没有被删掉,且不是边界,则加入到备选集合中,注意判重。
if (!bz[r[k]] && s[r[k]] != '#') q.push_back(r[k]); //若k的右边没有被删掉,且不是边界,则加入到备选集合中,注意判重。
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin >> s + 1;
int n = strlen(s + 1);
s[0] = s[n + 1] = '#'; //给s加个左右边界
//构建双链表
for (int i = 1;i <= n;i ++)
{
l[i] = i - 1,r[i] = i + 1;
q.push_back(i);//一开始每一个元素都有可能成为边缘字符,因此都放入备选集合
}
//0是双链表的左端点边界,n + 1是右端点边界
r[0] = 1;
l[n + 1] = n;
while (1)
{
///死循环,每次从备选集合中找到待删集合
filter_dels();
//若当前待删集合为空,则说明本轮没有产生新的边缘字符
if (w.empty()) break;
q.clear();
for (auto k: w)
remove(k);
}
if (r[0] == n + 1) puts("EMPTY");
else {
for (int i = r[0]; i != n + 1;i = r[i])
cout << s[i];
}
}