【模拟, 栈, 队列】拉马车【蓝桥杯】

题目

试题 历届真题 拉马车【第八届】【省赛】【C组】

3160. 拉马车

---

小的时候，你玩过纸牌游戏吗？

有一种叫做“拉马车”的游戏，规则很简单，却很吸引小朋友。

其规则简述如下：

假设参加游戏的小朋友是 $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$ 先出牌，最后赢的一方手里的牌序。

数据范围

输入的两个串的长度都不超过 $30$，
保证两人是拿一副牌玩的，所以总牌数不超过 $52$ 张，且同一种牌最多只有 $4$ 张。
公平起见，开始时两人手中的牌数相等。

输入样例1：

96J5A898QA
6278A7Q973

输出样例1：

2J9A7QA6Q6889977

输入样例2：

25663K6X7448
J88A5KJXX45A

输出样例2：

6KAJ458KXAX885XJ645

解题

方法一：模拟

思路

$A$ 、$B$ 两方手里的牌用队列模拟(queueA、queueB)，牌山中的牌用栈模拟(stack)，再维护一个哈希表(has)记录当前牌山中存在的牌，然后就根据题目给出的步骤循环模拟即可，知道某一方没有手牌了停止并打印胜者手牌。

注意：游戏可能存在无法结束的情况，所以维护一个 cnt 用来计数，当计数大于一个较大的值时判断这场游戏无法结束，直接输出 $-1$ 并返回。

代码

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String A = in.readLine();
        String B = in.readLine();
        Queue<Character> queueA = new LinkedList<>(); // A的手牌
        for (char ch : A.toCharArray()) queueA.offer(ch);
        Queue<Character> queueB = new LinkedList<>(); // B的手牌
        for (char ch : B.toCharArray()) queueB.offer(ch);
        Deque<Character> stack = new LinkedList<>(); // 牌山
        Map<Character, Boolean> has = new HashMap<>(); // 牌山中存在的牌
        boolean flag = true; // 用于标识本回合是由谁出牌
        int cnt = 0; // 计数
        while (!queueA.isEmpty() && !queueB.isEmpty()) {
            Queue<Character> curr = flag ? queueA : queueB; // 当前出牌方
            char currPoke = curr.poll(); // 要出的牌
            stack.push(currPoke);
           	// 只要牌山中存在要出的牌就循环下去
            while (has.getOrDefault(currPoke, false)) {
                curr.offer(stack.pop());
                has.put(currPoke, false);
                // 把从当前位置到上一次出现该牌的位置之间的牌全取出来放到当前出牌方那里
                while (stack.peek() != currPoke) {
                    char poke = stack.pop();
                    has.put(poke, false);
                    curr.offer(poke);
                }
                // 再次出牌
                curr.offer(stack.pop());
                currPoke = curr.poll();
                stack.push(currPoke);
            }
            has.put(currPoke, true);
            flag = !flag;
            // 计数过大 判断当前游戏无法结束
            if (++cnt > 1e5) {
                System.out.println(-1);
                return;
            }
        }
        // 判断胜者
        Queue<Character> winner = queueA.isEmpty() ? queueB : queueA;
        int sz = winner.size();
        char[] ans = new char[sz];
        // 取出牌序并输出
        for (int i = 0; i < sz; ++i) ans[i] = winner.poll();
        System.out.println(String.valueOf(ans));
    }
}