自动搬运

查看原文

来自洛谷，原作者为

	海洋守卫者 不积跬步，无以至千里；不积小流，无以成江海。

搬运于2025-08-24 23:15:00，当前版本为作者最后更新于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))