藍橋杯第八屆省賽JAVA真題----拉馬車

标題：拉馬車

小的時候，你玩過紙牌遊戲嗎？

有一種叫做“拉馬車”的遊戲，規則很簡單，卻很吸引小朋友。

其規則簡述如下：

假設參加遊戲的小朋友是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先出牌，最後赢的一方手裡的牌序。

例如，

輸入：

96J5A898QA

6278A7Q973

則程式應該輸出：

2J9A7QA6Q6889977

再比如，

輸入：

25663K6X7448

J88A5KJXX45A

則程式應該輸出：

6KAJ458KXAX885XJ645

我們約定，輸入的串的長度不超過30

資源約定：

峰值記憶體消耗（含虛拟機） < 256M

CPU消耗  < 1000ms

請嚴格按要求輸出，不要畫蛇添足地列印類似：“請您輸入...” 的多餘内容。

所有代碼放在同一個源檔案中，調試通過後，拷貝送出該源碼。

不要使用package語句。不要使用jdk1.7及以上版本的特性。

主類的名字必須是：Main，否則按無效代碼處理。

----------------------------

笨笨有話說：

    不斷删除前邊的，又要後邊添加.... 如果用數組，需要開一個大點的，請佛祖保佑在遊戲結束前，不會用到數組的邊緣。

歪歪有話說：

    反正串也不長，不如每次操作都傳回一個新的串。

默默有話說：

    我一般都不吱聲，這是典型的隊列結構，動态數組最好，沒有？自己造一個呗！

在做這一題時，一定要注意看清楚題目,要注意這一句話:

    當輪到B出牌時，他的牌K與桌上的紙牌序列中的K相同，則把包括K在内的以及兩個K之間的紙牌都赢回來，放入自己牌的隊尾。注意：為了操作友善，放入牌的順序是與桌上的順序相反的。

牌桌上的牌在收回是，是倒叙的 ，就是因為沒有看清楚這一點，debug了好久都沒用，結果一看題目，才發現自己被坑呢！

import java.util.*;

public class Main extends Object {

	private static final HashMap<String, String> repeat = new HashMap<>();

	public static void main(String[] args) {
		Scanner cache = new Scanner(System.in);
		String a = cache.next();
		String b = cache.next();
		ArrayList<Character> pai = new ArrayList<>();
		ArrayList<Character> A = new ArrayList<>();
		ArrayList<Character> B = new ArrayList<>();
		char[] temp = a.toCharArray();
		for (char c : temp) {
			A.add(c);
		}
		temp = b.toCharArray();
		for (char c : temp) {
			B.add(c);
		}

		boolean flag = true;
		int ok;

		while (true) {

			if (flag) {
				char data1 = A.get(0);
				chuPai(pai, A);
				ok = doYouHava(pai, data1);
				if (ok == -1) {
					char data2 = B.get(0);
					chuPai(pai, B);
					ok = doYouHava(pai, data2);
					if (ok != -1) {
						shouPai(pai, B, ok, A, B);
						flag = false;
					}
				} else {
					shouPai(pai, A, ok, A, B);
					flag = true;
				}
			} else {
				char data1 = B.get(0);
				chuPai(pai, B);
				ok = doYouHava(pai, data1);
				if (ok == -1) {
					char data2 = A.get(0);
					chuPai(pai, A);
					ok = doYouHava(pai, data2);
					if (ok != -1) {
						shouPai(pai, A, ok, A, B);
						flag = true;
					}
				} else {
					shouPai(pai, B, ok, A, B);
					flag = false;
				}
			}

			if (A.size() == 0) {
				break;
			}

			if (B.size() == 0) {
				break;
			}
		}

		if (A.size() != 0) {
			for (int x = 0; x < A.size(); x++) {
				System.out.print(A.get(x));
			}
		} else {
			for (int x = 0; x < B.size(); x++) {
				System.out.print(B.get(x));
			}
		}

		cache.close();
		System.exit(0);
	}

	public static void shouPai(ArrayList<Character> pai, ArrayList<Character> temp, int index, ArrayList<Character> A,
			ArrayList<Character> B) {

		// 判斷有沒有陷入死循環
		String sum = new String();
		sum += String.valueOf(A) + " ";
		sum += String.valueOf(B) + " ";
		sum += String.valueOf(pai);
		if (repeat.get(sum) != null) {
			System.out.println(-1);
			System.exit(0);
		} else {
			repeat.put(sum, sum);
		}

		// 将倒叙牌收入
		for (int x = (pai.size() - 1); x >= index; x--) {
			char data = pai.get(x);
			temp.add(data);
		}
		int length = pai.size();
		for (int x = index; x < length; x++) {
			pai.remove(pai.size() - 1);
		}

	}

	// 判斷前面有沒有重複的
	public static int doYouHava(ArrayList<Character> pai, char temp) {
		for (int x = 0; x < pai.size() - 1; x++) {
			if (pai.get(x).equals(temp)) {
				return x;
			}
		}
		return -1;
	}

	// 玩家出牌
	public static void chuPai(ArrayList<Character> pai, ArrayList<Character> temp) {
		char data = temp.get(0);
		pai.add(data);
		temp.remove(0);
	}

}