题目描述

塔子哥组织宿舍的同学们玩消消乐小游戏, 游戏可由$N$人参与, 总共有$M$张卡片平均分成$N$份, 保证$M$能被$N$整除。

1. 游戏从"塔子哥"开始，然后依次轮到其他牌友。出牌顺序是：塔子哥 -> 同学1 -> 同学2 -> ... -> 同学N -> 塔子哥 -> ...
2. 每位同学每次出牌时，只能打出手中的第一张牌，并将其放在桌面的牌上。如果桌面上没有牌，则直接将牌打在桌面上。
3. 如果某人打出的牌与桌面上的某张牌面相同，那么可以将两张相同牌面的牌及其夹在其中的所有牌拿走，并且将这些牌按照桌面上从上到下的顺序依次放回自己手牌的末尾。
4. 当有人手中的牌全部出完时，即判出局，不再参与后续游戏。直到倒数第二位同学将手中的牌出完时，游戏立即结束。

输入描述

第一行输入为一个正整数$N (2\le N\le 4)$，表示参与的人数, 包括塔子哥在内;

第二行输入为一个正整数$M(4\le M\le104)$，用例保证$M$能被$N$整除

接下来一行，$M/N$个数字，表示一开始塔子哥手中的牌面 $num(1 \le num\le13)$

接下来$N - 1$行，每行$M/N$个数字，分别表示一开始各位同学手中的牌面 $num(1 \le num\le13)$

输出描述

第一行输出为产生获胜者的轮数;

第二行为获胜者编号，塔子哥编号为1，同学1编号为2，同学2编号为3, 以此类推;

第三行输出获胜者最后手中的牌，顺序为出牌的顺序

样例

输入1

2
4
2 4
4 1

输出1

2
1
4 4

说明

第一轮:塔子哥出2，同学1出4，桌上牌从上到下为[4 2]，塔子哥手中牌剩余4，牌友1手中牌剩余1; 第二轮:塔子哥出4，桌面有相同牌4，塔子哥将桌面的2张4拿回来，塔子哥手中牌剩余[4 4]，同学1出1，与桌面的牌不同，同学2手中无牌、游戏结束，塔子哥胜出，手中剩余的牌为[4 4]。

输入2

2
6
2 4 1
3 2 1

输出2

3
2
1 2 4 3 2

题面描述

塔子哥组织了一场消消乐小游戏，共有 ( N ) 名玩家参与，手中各有 ( M/N ) 张卡片，游戏由塔子哥开始，玩家依次出牌，若出牌与桌面上的牌相同，则可以将相同牌及其夹在其中的牌拿走并放回手牌中。游戏持续进行，直到倒数第二位玩家出完手牌，最终输出获胜者的轮数、编号以及最后手中的牌顺序。

题解：模拟

使用双端队列+哈希表来模拟整个游戏的过程 玩家手里面的牌可以使用双端队列来模拟，出牌操作就是弹出队头元素，用哈希表记录当前桌面上的牌，如果哈希表检测到玩家打出的牌桌面上存在，则需要把桌面的部分牌回收到当前玩家手中，并更新哈希表中的元素。

某一个玩家被淘汰就说明队列为空，游戏结束说明在场的玩家数量cnt=1

代码分析

1. 输入部分：

   • 代码首先读取参与游戏的人数和总卡片数，确保玩家的手牌能够均分。

2. 玩家手牌初始化：

   • 使用双端队列来存储每位玩家的手牌，这样可以方便地进行出牌和回收操作。手牌的读取通过循环完成，确保每位玩家的初始手牌正确存储。

3. 桌面牌管理：

   • 使用哈希表来记录桌面上每张牌的出现次数。这个结构有助于快速判断出牌是否能够触发回收操作。同时，还使用一个数组模拟桌面上的牌堆，按顺序存储出牌的结果。

4. 游戏进行循环：

   • 通过一个主循环来控制游戏的进行，直到剩下的玩家数量为一。在每轮中，轮数加一，遍历所有玩家进行出牌。

5. 出牌逻辑：

   • 每位玩家依次出牌，检查其手牌是否为空。如果不为空，则获取并移除队首的牌。出牌的逻辑首先判断这张牌是否在桌面上存在。

6. 牌匹配与回收：

   • 如果出牌与桌面上的牌匹配，则会将桌面上的所有匹配牌及其夹在中间的牌回收并放回出牌玩家的手牌。这个过程需要更新哈希表中的牌的出现次数，并保持桌面牌的顺序。

7. 淘汰逻辑：

   • 在出牌过程中，如果玩家的手牌出完，减少剩余玩家的数量，并在合适的情况下终止游戏。

8. 游戏结果输出：

   • 最后，代码会输出游戏进行了多少轮，最后一个出局的玩家的编号，以及该玩家最后手中剩余的牌的顺序。

C++

#include <bits/stdc++.h>  // 引入 C++ 标准库。

using namespace std;  // 使用 "std" 命名空间，表示使用标准库组件。

int main() {
    int n, m;
    cin >> n >> m;  // 从标准输入读取两个整数 n 和 m。

    vector<deque<int>> a(n);  // 创建一个二维数组 a，每个元素是一个 deque 容器，用于存储每个玩家的手牌。

    for (int i = 0; i < n; i++) {  // 针对每个玩家：
        int x;
        for (int j = 0; j < m / n; j++) {  // 读取该玩家的手牌，每个玩家的手牌数为 m/n。
            cin >> x;
            a[i].push_back(x);  // 将读取的牌添加到玩家 i 的手牌 deque 中。
        }
    }

    unordered_map<int, int> mp;  // 创建一个无序 map，用于存储每张牌在桌面上出现的次数。

    vector<int> s;  // 创建一个 vector，模拟桌面上的牌堆。

    int cnt = n;  // 初始化一个计数器，记录还剩下多少玩家。
    int r = 0;  // 初始化一个计数器，记录已经进行了多少轮游戏。

    while (cnt > 1) {  // 当还有多于一个玩家时：
        r++;  // 轮数加一。

        for (int i = 0; i < n; i++) {  // 针对每个玩家：
            if (a[i].empty()) {  // 如果该玩家的手牌已经出完：
                continue;  // 跳过该玩家。
            }

            int cur = a[i].front();  // 获取当前玩家的手牌的第一张牌。
            a[i].pop_front();  // 从玩家手牌中移除该牌。

            if (mp[cur] > 0) {  // 如果这张牌在桌面上已经出现过：
                vector<int> s1 = {cur};  // 初始化一个列表，用于存储需要拿走的牌。

                while (s.back() != cur) {  // 当模拟桌面上的最后一张牌不是当前牌时：
                    s1.push_back(s.back());  // 将模拟桌面上的最后一张牌添加到列表 s1 中。
                    mp[s.back()]--;  // 减少该牌在桌面上出现的次数。
                    s.pop_back();  // 从模拟桌面上移除该牌。
                }

                s1.push_back(s.back());  // 将模拟桌面上的最后一张牌（即当前牌）添加到列表 s1 中。
                s.pop_back();  // 从模拟桌面上移除当前牌。
                mp[s1.back()]--;  // 减少当前牌在桌面上出现的次数。

                for (int &x : s1) {  // 针对列表 s1 中的每张牌：
                    a[i].push_back(x);  // 将牌添加回玩家 i 的手牌中。
                }
            } else {  // 如果这张牌在桌面上未出现过：
                s.push_back(cur);  // 将这张牌添加到桌面上。
                mp[cur]++;  // 增加该牌在桌面上出现的次数。

                if (a[i].empty()) {  // 如果玩家 i 的手牌已经出完：
                    cnt--;  // 减少剩余的玩家数量。
                    if (cnt == 1) {  // 如果只剩下一个玩家：
                        break;  // 退出循环。
                    }
                }
            }
        }
    }

    int pos = -1;  // 初始化一个变量，用于记录最后一个出局的玩家的位置。

    for (int i = 0; i < n; i++) {  // 针对每个玩家：
        if (!a[i].empty()) {  // 如果该玩家的手牌还未出完：
            pos = i;  // 记录该玩家的位置。
            break;
        }
    }

    cout << r << endl;  // 输出已经进行的轮数。
    cout << pos + 1 << endl;  // 输出最后一个出局的玩家的位置（由于玩家的编号从 1 开始，所以需要加一）。

    while (!a[pos].empty()) {  // 当最后一个出局的玩家的手牌不为空时：
        cout << a[pos].front() <<" "; 
        a[pos].pop_front();
    }
    return 0;
}

Java

import java.util.*;  // 导入 Java 标准工具包的所有内容，包括 Scanner、List、Deque、Map、ArrayList、LinkedList 和 HashMap 等。

public class Main {  // 定义名为 Main 的公共类。
    public static void main(String[] args) {  // 主函数，程序的入口。
        Scanner scanner = new Scanner(System.in);  // 创建一个新的 Scanner 对象，用于从标准输入读取用户输入的内容。
        int n = scanner.nextInt();  // 读取输入中的整数并存储在变量 n 中。
        int m = scanner.nextInt();  // 读取输入中的整数并存储在变量 m 中。

        List<Deque<Integer>> a = new ArrayList<>();  // 创建一个空的列表，用于存储每个玩家的手牌，列表中的每个元素都是一个双端队列。
        for (int i = 0; i < n; i++) {  // 针对每个玩家：
            Deque<Integer> playerHand = new LinkedList<>();  // 创建一个新的双端队列，用于存储当前玩家的手牌。
            for (int j = 0; j < m / n; j++) {  // 针对每个玩家的每张手牌：
                int x = scanner.nextInt();  // 从标准输入读取整数并将其存储在变量 x 中。
                playerHand.add(x);  // 将读取的整数添加到当前玩家的手牌中。
            }
            a.add(playerHand);  // 将当前玩家的手牌添加到列表 a 中。
        }

        Map<Integer, Integer> mp = new HashMap<>();  // 创建一个空的 HashMap 对象，用于存储每张牌在桌面上出现的次数。
        List<Integer> s = new ArrayList<>();  // 创建一个空的列表，用于模拟桌面上的牌堆。
        int cnt = n;  // 初始化一个计数器，用于记录还剩下多少玩家。
        int r = 0;  // 初始化一个计数器，用于记录已经进行了多少轮游戏。

        while (cnt > 1) {  // 当仍然有多于一个玩家时，执行循环。
            r++;  // 每次循环轮数加一。
            for (int i = 0; i < n; i++) {  // 针对每个玩家执行循环：
                if (a.get(i).isEmpty()) {  // 如果当前玩家手中没有牌，则跳过该玩家。
                    continue;
                }
                int cur = a.get(i).poll();  // 从当前玩家的手牌中移除并返回第一张牌。
                if (mp.getOrDefault(cur, 0) > 0) {  // 如果桌面上已经有与当前牌相同的牌，则执行下面的操作。
                    List<Integer> s1 = new ArrayList<>();  // 创建一个空的列表，用于存储需要拿走的牌。
                    s1.add(cur);  // 将当前牌添加到列表 s1 中。
                    while (!s.isEmpty() && !s.get(s.size() - 1).equals(cur)) {  // 当桌面上最后一张牌不是当前牌时，执行循环。
                        s1.add(s.remove(s.size() - 1));  // 将桌面上的最后一张牌添加到列表 s1 中，并从列表 s 中移除。
                        mp.put(s1.get(s1.size() - 1), mp.get(s1.get(s1.size() - 1)) - 1);  // 桌面上最后一张牌出现次数减一。
                    }
                    s1.add(s.remove(s.size() - 1));  // 将桌面上的最后一张牌添加到列表 s1 中，并从列表 s 中移除。
                    mp.put(s1.get(s1.size() - 1), mp.get(s1.get(s1.size() - 1)) - 1);  // 桌面上最后一张牌出现次数减一。
                    a.get(i).addAll(s1);  // 将列表 s1 中的牌添加回当前玩家的手牌中。
                } else {  // 如果桌面上没有与当前牌相同的牌，则执行下面的操作。
                    s.add(cur);  // 将当前牌添加到桌面上。
                    mp.put(cur, mp.getOrDefault(cur, 0) + 1);  // 增加当前牌在桌面上出现的次数。
                    if (a.get(i).isEmpty()) {  // 如果当前玩家的手牌已经出完，则执行下面的操作。
                        cnt--;  // 减少剩余的玩家数量。
                        if (cnt == 1) {  // 如果只剩下一个玩家，则退出循环。
                            break;
                        }
                    }
                }
            }
        }

        int pos = -1;  // 初始化一个变量，用于记录最后一个出局的玩家的位置。
        for (int i = 0; i < n; i++) {  // 针对每个玩家执行循环：
            if (!a.get(i).isEmpty()) {  // 如果当前玩家的手牌还未出完，则执行下面的操作。
                pos = i;  // 记录当前玩家的位置。
                break;
            }
        }

        System.out.println(r);  // 输出已经进行的轮数。
        System.out.println(pos + 1);  // 输出最后一个出局的玩家的位置（由于玩家的编号从 1 开始，所以需要加一）。

        StringBuilder output = new StringBuilder();
        while (!a.get(pos).isEmpty()) {  // 当最后一个出局的玩家的手牌不为空时，执行循环。
            output.append(a.get(pos).peek()).append(" ");  // 将当前玩家手牌的第一张牌添加到输出中。
            a.get(pos).poll();  // 从当前玩家的手牌中移除第一张牌。
        }
        System.out.println(output.toString().trim());  // 输出最后一个出局的玩家的手牌。
    }
}

Python3

from collections import defaultdict  # 导入 defaultdict，它是内置 dict 类的子类，它重写了一个方法并添加了一个可写的实例变量。其余的功能与 dict 类相同。

n = int(input())  # 读取玩家的数量
m = int(input())  # 读取牌的数量

a = []  # 初始化一个空列表，用于存储每个玩家的手牌
for _ in range(n):  # 对于每个玩家
	a.append(list(map(int , input().split())))  # 读取该玩家的手牌，并将其添加到列表 a 中

s = []  # 初始化一个空列表，用于存储桌面上的牌
mp = defaultdict(int)  # 初始化一个默认字典，用于存储每张牌在桌面上出现的次数

cnt = n  # 初始化一个计数器，用于记录还剩下多少玩家
r = 0  # 初始化一个计数器，用于记录已经进行了多少轮

while cnt > 1:  # 当还有多于一个玩家时
	r += 1  # 轮数加一
	for i in range(n):  # 对于每个玩家
		if not a[i]:  # 如果该玩家的手牌已经出完
			continue  # 则跳过该玩家
		now = a[i].pop(0)  # 否则，该玩家打出他的第一张牌
		if mp[now] != 0:  # 如果这张牌与桌面上的某张牌相同
			seq = [now]  # 则初始化一个列表，用于存储需要拿走的牌
			while s[-1] != now:  # 当列表 s 的最后一张牌不是当前牌时
				seq.append(s.pop())  # 将列表 s 的最后一张牌添加到列表 seq 中，并从列表 s 中移除
				mp[seq[-1]] -= 1  # 将这张牌在桌面上的出现次数减一
			seq.append(s.pop())  # 将列表 s 的最后一张牌（即当前牌）添加到列表 seq 中，并从列表 s 中移除
			mp[seq[-1]] -= 1  # 将当前牌在桌面上的出现次数减一
			a[i] += seq  # 将列表 seq 中的牌添加到玩家 i 的手牌中
		else:  # 如果这张牌与桌面上的所有牌都不相同
			s.append(now)  # 则将这张牌添加到桌面上
			mp[now] += 1  # 并将这张牌在桌面上的出现次数加一
		
		if not a[i]:  # 如果玩家 i 的手牌已经出完
			cnt -= 1  # 则剩余的玩家数量减一
			if cnt == 1:  # 如果只剩下一个玩家
				break  # 则跳出循环

pos = -1  # 初始化一个变量，用于记录最后一个出局的玩家的位置
for i in range(n):  # 对于每个玩家
	if a[i]:  # 如果该玩家还未出局
		pos = i  # 则记录该玩家的位置

print(r)  # 输出已经进行的轮数
print(pos + 1)  # 输出最后一个出局的玩家的位置（由于玩家的编号从 1 开始，所以需要加一）
print(" ".join(map(str , a[pos])))  # 输出最后一个出局的玩家的手牌