第十三届省赛真题-消除游戏（字符串问题）

这题没有题解，写了好久，终究还是太菜（前三种解法可能会有与你差不多的，第四种解法为最终AC代码及思路）

一.暴力（1/4的数据时间超限）

思路：依次对两种情况进行判断并删除所对应的字符，后再对删除的部分与后字符串相连可能产生的情况进行特判

代码如下：

#include#includeusing namespace std;
string a;
int main()
{
    int i=1,j;
    cin>>a;
    long long t=0;
    while(t++<9223372036854775807)
    {
        int p=0;
        char b;
        int x=a.size();
        for(i=0; i<a.size(); i++)
        {
            if(p==1)//特判
            {
                int q=0;
                if(i+1<a.size()&&b!=a[i]&&a[i]==a[i+1])
                {
                    b=a[i];
                    a.erase(i,1);
                    q=1;
                }
                else if(b==a[i]&&a[i]!=a[i+1])
                {
                    b=a[i+1];
                    a.erase(i,2);
                    q=1;
                    i--;
                }
                if(q==0) {i--;p=0;}
            }
            else//最开始的判断
            {
                if(i+2<a.size()&&a[i]!=a[i+1]&&a[i+2]==a[i+1])
                {
                    b=a[i+1];
                    a.erase(i,2);
                    i--;
                }
                else if(i+2<a.size()&&a[i]==a[i+1]&&a[i+2]!=a[i+1])
                {
                    b=a[i+2];
                    a.erase(i+1,2);
                    p=1;
                }
            }

        }
        int y=a.size();
        if(x==y)
            break;
    }

    if(a.size()==0)
    {
        cout<<"EMPTY"<<endl;
    }
    else
        cout<<a<<endl;
    return 0;
}

二.思路优化

思路：采用标记，对字符串数组进行遍历，对不需要的字符下标加入一个集合中，然后遍历在集合中的就删除

代码如下：

#include#includeusing namespace std;
string a;
vectorv;
int main()
{
    int i=1,j;
    cin>>a;
    long long t=0;

    while(t++<92233720368)
    {
        int n=a.size();
        for(i=1;i<n;i++)
        {
            if(a[i-1]==a[i]&&a[i]!=a[i+1])
            {
                v.push_back(i);
                v.push_back(i+1);
            }
            else if(a[i-1]!=a[i]&&a[i]==a[i+1])
            {
                v.push_back(i-1);
                v.push_back(i);
            }
        }

        if(v.size()==0)//若需删除的集合为0，则不用删除退出
        {
            cout<<a<<endl;
            break;
        }
        n=v.size();
        int p=0;

        for(i=0;i<n;i++)
        {
            if(i<2||v[i]!=v[i-1]&&v[i]!=v[i-2])//避免重复
            {
                a.erase(v[i]-p,1);
                p++;
                if(a.size()==0)
                break;
            }
        }
        if(a.size()==0)
        {
            cout<<"EMPTY"<<endl;
            break;
        }
        v.clear();
    }

    return 0;
}

三.函数优化

1.更换较快的函数，大致思路相同；

2.采用scanf，printf，输入与输出；

3.减去使用string存储字符串，由于string 为动态分配空间，时间消耗大，删去了erase函数，该字符串删除函数时间复杂度为O(n)；

悲惨的是终究还是时间超限，虽然又多对了一组样例

代码如下：

#include#include#includeusing namespace std;
char a[1000001];

int main()
{
    int i=1,j;
    scanf("%s",a);
    long long t=0;

    while(t++<1000001)
    {
        bool b[1000001]={};
        int n=strlen(a);
        int x=n;
        for(i=1;i<n;i++)
        {
            if(i+1<n&&a[i-1]==a[i]&&a[i]!=a[i+1])
            {
                b[i]=1;
                b[i+1]=1;
            }
            else if(i+1<n&&a[i-1]!=a[i]&&a[i]==a[i+1])
            {
                b[i-1]=1;
                b[i]=1;
            }
        }
        
        int p=0;
        for(i=0;i<n;i++)
        {
            if(b[i]==0)
                a[p++]=a[i];//采用之前的用的内存保存有用信息
        }
        a[p]='\0';

        if(x==strlen(a))//判断进行删减操作后是否与原字符串长度相等，相等则退出
        {
            printf("%s",a);
            break;
        }
        if(a[0]=='\0')
        {
            printf("EMPTY\n");
            break;
        }
    }

    return 0;
}

四.思路再优化（最终AC）

我便想到了可能有特殊样例，我便还是下载了数据，还真有一组样例为：几十万个a，与几十万个b，所以导致循环很难通过，每次都得对n进行遍历，时间复杂度被升到了O（n²）

优化思路：

1.在每次查找到连续三个以上的话就可以连着标记删除，不用等下一次遍历再删，因为不会影响到下一次删除

2.为了不影响下一次删除，则需保留左右分别至少两个的连续的字符

3.而且每次查找相同的到最后时（就是右边全是相同的时候），需停止查找，直接跳出循环，否则又会将时间复杂度降到O（n²）（这个问题想了好久才出来，哭死）

加入上一个函数的代码为：

int j=1;
            while(i+j3)
                while(y+j3)
            {
                if(c[y]>c[i])
                {
                    for(int k=1+2; k<=c[i]; k++)
                    {
                        b[i+k-2]=1;
                        b[y+k-3]=1;
                    }
                }
                else
                {
                    for(int k=1+2; k<=c[y]; k++)
                    {
                        b[i+k-2]=1;
                        b[y+k-3]=1;
                    }
                }
                i=y+c[y]-2;
            }
            c[I]=0;
            c[y]=0;

最终完整AC代码为

#include#include#includeusing namespace std;
char a[1000001];
int c[1000001];

int main()
{
    int i=1,j,I;
    scanf("%s",a);
    long long t=0;

    while(t++<200)
    {
        bool b[1000001]= {};
        int n=strlen(a);
        int x=n;
        for(i=1; i<n; i++)
        {

            if(i+1<n&&a[i-1]==a[i]&&a[i]!=a[i+1])
            {
                b[i]=1;
                b[i+1]=1;
            }
            else if(i+1<n&&a[i-1]!=a[i]&&a[i]==a[i+1])
            {
                b[i-1]=1;
                b[i]=1;
            }
            //一下为加入的特判
            int j=1;
            while(i+j3)//若前面有大于三的连续字符，则再判断后面的连续字符有多少
                while(y+j3)//后面连续字符也大于三，则可进行删除操作，并保留两边字符个数至少为2
            {
                if(c[y]>c[i])
                {
                    for(int k=1+2; k<=c[i]; k++)
                    {
                        b[i+k-2]=1;
                        b[y+k-3]=1;
                    }
                }
                else
                {
                    for(int k=1+2; k<=c[y]; k++)
                    {
                        b[i+k-2]=1;
                        b[y+k-3]=1;
                    }
                }
                i=y+c[y]-2;
            }
            c[I]=0;//初始化
            c[y]=0;
        }

        int p=0;
        for(i=0; i<n; i++)
        {
            if(b[i]==0)
                a[p++]=a[i];
        }
        a[p]='\0';
        if(x==strlen(a))
        {
            printf("%s",a);
            break;
        }
        if(a[0]=='\0')
        {
            printf("EMPTY\n");
            break;
        }
    }

    return 0;
}

看我写了这么长，要是有帮助的话给个好评吧，感谢