题解：P12368 [蓝桥杯 2022 省 Python B] 消除游戏

海洋守卫者 · 2025-04-30 16:24:14 · 题解

P12368 [蓝桥杯 2022 省 Python B] 消除游戏

解题思路

将连续的相同字符看作一个整体，用链表维护，不断操作至结果不改变为止。思路很简单，主要考察的是对链表的操作。

完整代码

C++：

代码写得有些繁琐，但思路是正确的。

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iterator>
#include<list>
#include<map>
using namespace std;
const int MAXN=1e6+7;
char S[MAXN];
typedef pair<char,int> P;
int n;
list<P>l;
list<P>::iterator it,p,q;
int main()
{
    scanf("%s",S+1);
    n=strlen(S+1);
    for(int i=1;S[i];i++)if(S[i]==S[i-1])(--l.end())->second++;
    else l.push_back(P(S[i],1));
    bool changed=1;
    while(changed)
    {
        changed=0;
        bool bp=0;
        for(it=l.begin();it!=l.end();){    //删除该串中的所有边缘字符
            if(it!=--l.end())
            {
                if((it->second==1&&bp)||it->second>1||next(it)->second>1){
                    it->second--;
                    (++it)->second--;
                    changed=1;
                    bp=1;
                }
                else ++it,bp=0;
            }
            else break;
        }
        for(it=l.begin();it!=l.end();++it)    //去掉已经被完全删除的字符（串）
        {
            if(it->second<=0)
            {
                it=l.erase(it);
                --it;
            }
        }
        for(it=l.begin();it!=l.end();){    //将链表上相同且连续的单位合并
            if(it!=--l.end())
            {
                p=it,q=++it;
                if(p->first==q->first)
                {
                    p->second+=q->second;
                    l.erase(q);
                    it=p;
                }
            }
            else break;
        }
    }
    if(l.size()==0)puts("EMPTY");
    else for(it=l.begin();it!=l.end();++it)for(int i=1;i<=it->second;i++)putchar(it->first);
    return 0;
}

Python：

基于 Python 本身的优秀性能。

我们可以用其强大的功能来完成代码。

s=list(str(input()))
f=[False for i in range(len(s))]
while True:
    n=len(s)
    change=False
    for i in range(1,n-1):
        if s[i]==s[i-1] and s[i]!=s[i+1]:
            f[i]=True
            f[i+1]=True
        if s[i]!=s[i-1] and s[i]==s[i+1]:
            f[i-1]=True
            f[i]=True
    for i in range(n):
        if f[i]:
            f[i]=False
            s[i]=''
            change=True
    s=list(''.join(s))
    if not change:
        break
if len(s)==0:
    print('EMPTY')
else:
    print(''.join(s))