Educational Codeforces Round 161 D题,和这道题很像,而且那道题用set就可以过,这道题的set会被卡。链接: https://codeforces.com/contest/1922/problem/D
C++ 代码
#include<bits/stdc++.h>
using namespace std;
void solve()
{
string s;
cin>>s;
int n=s.size();
s="#"+s+"#";
int l[n+2],r[n+2];
for(int i=0;i<n+2;i++)
{
l[i]=i-1,r[i]=i+1;
}
int visited[n+2]={0};
vector<int> see;
vector<int> temp;
for(int i=1;i<=n;i++) see.push_back(i);
while(see.size())
{
for(auto i:see)
{
if(visited[i]) continue;
if(l[i]>0 && r[i]<=n)
{
if(s[l[i]]==s[i] && s[i]!=s[r[i]])
{
temp.push_back(i);temp.push_back(r[i]);
}
if(s[l[i]]!=s[i] && s[i]==s[r[i]])
{
temp.push_back(i);temp.push_back(l[i]);
}
}
}
see.clear();
for(auto i:temp)
{
if(visited[i]) continue;
visited[i]=1;
if(l[i]>0) see.push_back(l[i]);
if(r[i]<=n) see.push_back(r[i]);
r[l[i]]=r[i],l[r[i]]=l[i];
}
temp.clear();
}
if(r[0]==n+1) cout<<"EMPTY"<<endl;
else
{
for(int i=1;i<=n;i++)
{
if(!visited[i]) cout<<s[i];
}
}
}
int main(void)
{
solve();
return 0;
}