(蓝桥杯)拉马车 题解 两种判定游戏无法结束的方法

题目:http://lx.lanqiao.cn/problem.page?gpid=T447
大致题意:每人开局有相同张数(小于等于30)固定顺序的卡牌,每人依次出最先那张入栈,如果出牌后栈里有两张重复的牌,则一直在栈顶取牌放到自己的牌的队尾直到这两张牌都被拿走。当一个玩家出牌后牌空结束游戏,输出另一个玩家的牌。

方法一:(这是目前普遍的解法)当玩家总出牌次数大于一个大数(如10000)时,认定为游戏无法结束,这种方法的正确性比较玄学,代码如下:

#include <bits/stdc++.h>
using namespace std;
vector<char> pt[2],p;
map<char,int> ps;
string tmp;
int n,lp,cnt;
char c,cc;
signed main()
{
	for(int i=0;i<2;++i)
	{
		cin>>tmp;
		n=tmp.size();
		for(int j=0;j<n;++j) pt[i].push_back(tmp[j]);
	}
	for(;true;lp^=1,++cnt)
	{
		c=pt[lp].front();
		p.push_back(c);
		++ps[c];
		pt[lp].erase(pt[lp].begin());
		if(ps[c]>1)
		{
			while(ps[c])
			{
				cc=p.back();
				pt[lp].push_back(cc);
				--ps[cc];
				p.pop_back();
			}
			lp^=1;
		}
		if(!pt[lp].size()) break;
		if(cnt>10000) return printf("-1")&0;
	}
	lp^=1,n=pt[lp].size();
	for(int i=0;i<n;++i) printf("%c",pt[lp][i]);
	return 0;
}

评测结果如下:
(蓝桥杯)拉马车 题解 两种判定游戏无法结束的方法

方法二:每次出牌(且判定完赢牌)后,记录下两个玩家的牌(可以加上桌上序列),合起来存map,如果这种情况之前(不包括这次)出现了超过一次(如果只是出现一次过不了第三个测试点),那么判定出现了重复,代码如下:

#include <bits/stdc++.h>
using namespace std;
vector<char> pt[2],p;
map<char,int> ps;
map<string,int> m;
string tmp;
int n,lp;
char c,cc;
signed main()
{
	for(int i=0;i<2;++i)
	{
		cin>>tmp;
		n=tmp.size();
		for(int j=0;j<n;++j) pt[i].push_back(tmp[j]);
	}
	for(;true;lp^=1)
	{
		c=pt[lp].front();
		p.push_back(c);
		++ps[c];
		pt[lp].erase(pt[lp].begin());
		if(ps[c]>1)
		{
			while(ps[c])
			{
				cc=p.back();
				pt[lp].push_back(cc);
				--ps[cc];
				p.pop_back();
			}
			lp^=1;
		}
		if(!pt[lp].size()) break;
		tmp="";
		for(int h=0;h<2;++h)
		{
			n=pt[h].size();
			for(int i=0;i<n;++i) tmp+=pt[h][i];
		}
		if(m.find(tmp)!=m.end()&&m[tmp]>1) return printf("-1")&0;
		++m[tmp];
	}
	lp^=1,n=pt[lp].size();
	for(int i=0;i<n;++i) printf("%c",pt[lp][i]);
	return 0;
}

评测结果如下:
(蓝桥杯)拉马车 题解 两种判定游戏无法结束的方法
第一次写题解qwq,如有错误,欢迎指出~

上一篇:数据结构之树


下一篇:392. 判断子序列