消除游戏（寒假每日一题+模拟、优化）

题目

在一个字符串?S?中，如果?Si=Si?1 且?Si≠Si+1，则称?Si和?Si+1 为边缘字符。

如果?Si≠Si?1?且?Si=Si+1，则?Si?1?和?Si 也称为边缘字符。

其它的字符都不是边缘字符。

对于一个给定的串?S，一次操作可以一次性删除该串中的所有边缘字符（操作后可能产生新的边缘字符）。

请问经过?264264?次操作后，字符串?S 变成了怎样的字符串，如果结果为空则输出?EMPTY。

输入格式

输入一行包含一个字符串?S。

输出格式

输出一行包含一个字符串表示答案，如果结果为空则输出?EMPTY。

数据范围

对于?25%?的评测用例，|S|≤10^3，其中?|S|表示?S?的长度；
对于?50%?的评测用例，|S|≤10^4；
对于?75%?的评测用例，|S|≤10^5；
对于所有评测用例，|S|≤10^6，S?中仅含小写字母。

样例

输入样例1

edda

输出样例1

EMPTY

输入样例2

sdfhhhhcvhhxcxnnnnshh

输出样例2

s

题目思路

? ? ? ? 该题目的重点在于如何对其进行优化。从题目中可以清楚的看出，如果我们使用暴力做法的话会TLE，如果每一次只删除一个字符，那么时间复杂度：n、n-1、n-2、n-3……1.；如此时间复杂度为O(n^2)，在这题中最多能过50%的数据。

? ? ? ? 优化只要添加一个备选数，在备选数中去查找边缘数。

源代码?

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1e6+10;

char g[N];
int l[N],r[N];
vector<int> q,w;
bool st[N];
int n;

void insert(int k){
    if(!st[k]){
        st[k]=true;
        w.push_back(k);
    }
}

void filter_dels(){
    w.clear();
    
    for(int k:q){
        int a=l[k],b=k,c=r[k];
        
        if(g[a]==g[b] && g[b]!=g[c] && g[c]!='*'){
            insert(b);
            insert(c);
        }
        if(g[c]==g[b] && g[b]!=g[a] && g[a]!='*'){
            insert(b);
            insert(a);
        }
    }
}

int main()
{
    scanf("%s",g+1);
    n=strlen(g+1);
    
    g[0]=g[n+1]='*';
    for(int i=1;i<=n;i++){
        q.push_back(i);
        l[i]=i-1,r[i]=i+1;
    }
    r[0]=1,l[n+1]=n;
    
    while(true){
        filter_dels();
        
        if(w.empty()) break;
        
        q.clear();
        for(int k:w){
            int a=l[k],b=k,c=r[k];
            
            //q.back()!=a这个条件保证了不会出现备选数，当然如果删除也是可以的
            //如：xxoo其中中间两个xo被添加了两次，如果不加条件的话
            if (!st[a] && a && (q.empty() || q.back()!=a)) q.push_back(a);
            if (!st[c] && c != n + 1) q.push_back(c);
            
            //删除k节点
            r[a]=c,l[c]=a;
        }
    }
    
    if(r[0]==n+1) puts("EMPTY");
    else{
        for(int i=r[0];i!=n+1;i=r[i]) printf("%c",g[i]);
    }
    
    return 0;
}

没有优化的代码——这个代码只能过33.3%的数据

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1e6+10;

char g[N];
int l[N],r[N];
queue<int> q;
bool st[N];
int n;

//查找边缘字符，只要记录前一个节点即可
void insert(int x){
    if(x==1 || x==n) return;

    int left=l[x],right=r[x];
    if(g[left]!=g[x] && g[right]==g[x]) q.push(left),q.push(x);
    else if(g[right]!=g[x] && g[left]==g[x]) q.push(x),q.push(right);
}

void deletes(int x){
    l[r[x]]=l[x];
    r[l[x]]=r[x];
}

int main()
{
    scanf("%s", g+1);
    n=strlen(g+1);

    g[0]=g[n+1]='*';;
    for(int i=1;i<=n;i++){
        l[i]=i-1,r[i]=i+1;
    }
    r[0]=1,l[n+1]=n;

    while(true){
        for(int i=r[0];i!=n+1;i=r[i]) insert(i);

        if(q.empty()) break;

        while(!q.empty()){
            auto x=q.front();
            q.pop();
            if(!st[x]) deletes(x);
            st[x]=true;
        }
    }

    if(r[0]==n+1) puts("EMPTY");
    else{
        for(int i=r[0];i!=n+1;i=r[i]) printf("%c",g[i]);
    }
    return 0;
}