【解題報告+思路拓展】藍橋杯 拉馬車 2017年C組真題

勵志用更少的代碼做更高效的表達

題目描述

小的時候，你玩過紙牌游戲嗎？
有一種叫做“拉馬車”的游戲，規則很簡單，卻很吸引小朋友，

其規則簡述如下：
假設參加游戲的小朋友是A和B，游戲開始的時候，他們得到的隨機的紙牌序列如下：
A方：[K, 8, X, K, A, 2, A, 9, 5, A]
B方：[2, 7, K, 5, J, 5, Q, 6, K, 4]

其中的X表示“10”，我們忽略了紙牌的花色，

從A方開始，A、B雙方輪流出牌，

當輪到某一方出牌時，他從自己的紙牌佇列的頭部拿走一張，放到桌上，并且壓在最上面一張紙牌上（如果有的話），

此例中，游戲程序：
A出K，B出2，A出8，B出7，A出X，此時桌上的序列為：

K,2,8,7,X

當輪到B出牌時，他的牌K與桌上的紙牌序列中的K相同，則把包括K在內的以及兩個K之間的紙牌都贏回來，放入自己牌的隊尾，注意：為了操作方便，放入牌的順序是與桌上的順序相反的，
此時，A、B雙方的手里牌為：
A方：[K, A, 2, A, 9, 5, A]
B方：[5, J, 5, Q, 6, K, 4, K, X, 7, 8, 2, K]

贏牌的一方繼續出牌，也就是B接著出5，A出K，B出J，A出A，B出5，又贏牌了，
5,K,J,A,5
此時雙方手里牌：
A方：[2, A, 9, 5, A]
B方：[Q, 6, K, 4, K, X, 7, 8, 2, K, 5, A, J, K, 5]

注意：更多的時候贏牌的一方并不能把桌上的牌都贏走，而是拿走相同牌點及其中間的部分，但無論如何，都是贏牌的一方繼續出牌，有的時候剛一出牌又贏了，也是允許的，

當某一方出掉手里最后一張牌，但無法從桌面上贏取牌時，游戲立即結束，

對于本例的初始手牌情況下，最后A會輸掉，而B最后的手里牌為：

9K2A62KAX58K57KJ5

本題的任務就是已知雙方初始牌序，計算游戲結束時，贏的一方手里的牌序，當游戲無法結束時，輸出-1，

輸入為2行，2個串，分別表示A、B雙方初始手里的牌序列，
輸出為1行，1個串，表示A先出牌，最后贏的一方手里的牌序，

樣例輸入1

96J5A898QA
6278A7Q973

樣例輸出1

2J9A7QA6Q6889977

樣例輸入2

25663K6X7448
J88A5KJXX45A

樣例輸出2

6KAJ458KXAX885XJ645

解題思想

看完題想都不用想，必是佇列，

這里使用雙端佇列（可以理解為堆疊+佇列），理由有二，
1 可以使用begin()和end()函式， 而queue佇列沒有
2 可以靈活的從佇列頭或佇列尾入隊、出隊，

程序：將兩個字串存入 佇列A和佇列B， 挨個放到佇列C中， 每放一次就用count()函式判斷， 若該字符在C佇列中出現兩次， 則從后往前遍歷C，直到出現這個字符，將這串序列出隊，入隊A或B，

使用bool變數 flag判斷下次對哪個佇列操作，

注意：

1 若某方收走牌后，則下一次還是由他先出牌

2 代碼中注釋的部分，是對佇列的遍歷的技巧， 其實遍歷佇列一直很讓人苦惱， 不能用for回圈， 也不能用迭代器， 但在C++11中， 可以用auto做變數， 好用！

優化：

1 代碼中存在一些冗余， 如果靈活運用函式， 可增加代碼復用性，

2 用遞回同樣可以達到上述效果，（but 不太純熟，于是沒有使用， 畢竟能AC的代碼都是好代碼， 哈哈）

代碼展示

代碼看似長， 但很好理解， 注釋都標記了，

#include<bits/stdc++.h>
using namespace std;

string s1, s2;		
deque<char>q1, q2, q3;						//普通佇列沒有begin和end函式 , q3存放結果序列 
bool flag = true; 							//決定哪個佇列出牌 
bool flag1 = true;							//決定最后輸出哪個佇列  
 
void Input_deque() {
	int len1 = s1.length(), len2 = s2.length();
	for(int i = 0; i < len1; i++) q1.push_back(s1[i]);
	for(int i = 0; i < len2; i++) q2.push_back(s2[i]);
}

void Output_deque(deque<char>q) {
	int siz = q.size();
	while(!q.empty()) {
		cout << q.front();
		q.pop_front();
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin>>s1>>s2;		//輸入、求長度 
	
	//將字串存入佇列
	Input_deque();
	
	
	while(1) {
//		容器的測驗輸出方式 
//		for(auto&j : q1) { cout << j << ' '; }
//		cout << endl;
//		
//		for(auto&j : q2) { cout << j << ' '; }
//		cout << endl;
//
//		for(auto&j : q3) { cout << j << ' '; }
//		cout << endl;
//		
//		cout << endl;
		
		if(flag == true) {
			
			char a = q1.front();   	q1.pop_front();   //q1彈出 
			q3.push_back(a);				//壓入q3 
			if(count(q3.begin(), q3.end(), a) >= 2) {	//個數>=2，說明存在首尾相同的序列 
				q3.pop_back();    q1.push_back(a);	 //先將最后一個入q1 
				while(1) {
					char c = q3.back();
					q3.pop_back();
					q1.push_back(c);
					if(c == a) break;
				}
				flag = true; continue;					//下次從這個佇列中先取 
			} 
		}
		flag = false;
		
		if(q1.empty()) { flag1=false; break;}
		else if(q2.empty()) break;	
		 
		 
		if(flag == false) {
			char b = q2.front();    q2.pop_front();
			q3.push_back(b);
			if(count(q3.begin(), q3.end(), b) >= 2) {
				q3.pop_back();    q2.push_back(b);	 //先將最后一個入q1 
				while(1) {
					char c = q3.back();
					q3.pop_back();
					q2.push_back(c);
					if(c == b) break;
				}
				flag = false; continue;					//下次從這個佇列中先取 
			}
		}
		flag = true;
		
		//最后判斷哪個佇列為空， 
		if(q1.empty()) { flag1=false; break;}
		else if(q2.empty()) break;	
		
	}
	
	if(flag1 == false) 		//輸出q2 
		Output_deque(q2);
	else Output_deque(q1);
	
	
return 0; } 

撥云見日 未來可期