专栏文章

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

P12368题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mipgbtxb
此快照首次捕获于
2025/12/03 11:32
3 个月前
此快照最后确认于
2025/12/03 11:32
3 个月前
查看原文

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

解题思路

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

完整代码

C++:

代码写得有些繁琐,但思路是正确的。
CPP
#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 本身的优秀性能。
我们可以用其强大的功能来完成代码。
PY
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))

评论

2 条评论,欢迎与作者交流。

正在加载评论...