1335: [蓝桥杯2017初赛]拉马车 【中 / 队列 / 栈 / map 】 有意思

1335: [蓝桥杯2017初赛]拉马车 【中 / 队列 / 栈  / map 】 有意思
http://oj.ecustacm.cn/problem.php?id=1335

其实本题的大致思路是非常的明显的。
就是里面有很多的细节需要注意。
比如谁赢了,谁就变先手了。
还有出栈的时候,是出到相等的元素时停止,不要以为可以一下出栈出完。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<map>
using namespace std;
int main(void)
{
	string str1,str2;
 	while(cin>>str1>>str2)
 	{
 		queue<char> q1,q2;//双方 
 		stack<char> st;//桌面
		map<char,int> mp; //用来映射桌面上的牌
		int n=0;
		/*************************/
		//初始化两者的(牌)队列 
 		for(int i=0;i<str1.length();i++)
 		{
 			q1.push(str1[i]);
 		}
 		for(int i=0;i<str2.length();i++)
 		{
 			q2.push(str2[i]);
 		}
 		/****************************/
 		
 		
 		/****************************/
 		//开始对局 
 		bool flag=true;//先手
 		bool flag2=true;//可不可以结束
 		while(!q1.empty()&&!q2.empty())
 		{
 			
 			/***********************/
			//1号手 
			if(flag)
			{
				char temp=q1.front();
				q1.pop();
				if(mp[temp]==0)//桌面还没有 
				{
					st.push(temp);//牌打到桌面上 
					mp[temp]=1;
				}
				else
				{
					mp[temp]=0; 
					q1.push(temp);//这张牌排到队列后。 
					while(!st.empty())
					{
						char a;
						a=st.top();
						mp[a]=0;
						st.pop();
						q1.push(a);
						if(a==temp)
						{	
							flag=!flag;
							break;
						}
					}
				}
			}
			else
			{	
				/***********************/
				//2号手 
				char temp2=q2.front();
				q2.pop();
				if(mp[temp2]==0)//桌面还没有 
				{
					st.push(temp2);//牌打到桌面上
					mp[temp2]=1; 
				}
				else
				{
					mp[temp2]=0; 
					q2.push(temp2);//这张牌排到队列后。 
					while(!st.empty())
					{
						char a;
						a=st.top();
						mp[a]=0;
						st.pop();
						q2.push(a);
						if(a==temp2)
						{	
							flag=!flag; 
							break;
						}
					}
				}
			}
			flag=!flag;//正常出牌
			n++;
			if(n>9999)
			{
				n=0;
				printf("-1\n");
				flag2=false;
				break;
			}
 		}
 		if(flag)
 		for(int i=0;!q1.empty();i++)
 		{
 			cout<<q1.front();
 			q1.pop();
 		}	
 		for(int i=0;!q2.empty();i++)
 		{
 			cout<<q2.front();
 			q2.pop();
 		}
		cout<<endl; 
 	}
	return 0;
} 
上一篇:Python习题《古典—兔子生兔子问题》


下一篇:P1294 高手去散步 (基础模板)(DFS,搜索最长路的模板,也可以改成搜索最短路)