题目: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,如有错误,欢迎指出~