【解題報告+思路拓展】藍橋杯 拉馬車 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; }
撥雲見日 未來可期
