Problem J42 : Poker Shuffle / 扑克洗牌问题

**版权信息： · 模拟与置换问题

---

任务总览

任务名称	时间限制	内存限制	分数
扑克洗牌问题	1 sec	1024 MB	10 points

---

题目描述

你手上有 $2n$ 张牌，初始顺序为 $1, 2, 3, dots, 2n$。

现在对这些牌进行一种特定的“洗牌操作”：

• 将前半部分牌编号为 $1, 2, \dots, n$；
• 将后半部分牌编号为 $n + 1, n + 2, \dots, 2n$；
• 洗牌后的顺序为：$n + 1, 1, n + 2, 2, n + 3, 3, \dots, 2n, n$。

即第 $k$ 次洗牌操作的结果为：

• 原本第 $k$ 张牌（$1 \leq k \leq n$）被放到新序列的第 $2k$ 个位置；
• 原本第 $n + k$ 张牌（$1 \leq k \leq n$）被放到新序列的第 $2k - 1$ 个位置。

请编程求出：对于任意输入的正整数 $n$（$1 \leq n < 10000$），最少需要洗多少次，才能使牌重新回到初始顺序。同时，输出每次洗牌后的牌序。

---

输入格式

一行一个整数 $n$，表示牌的一半数量（总共 $2n$ 张牌）。

---

输出格式

*第一行为初始牌序；

• 接下来每一行为一次洗牌后的结果，格式为：i:（第几次洗牌）和本轮的牌序；
• 最后一行为：m=X，表示共洗牌 $X$ 次才回到原来的顺序。

---

输入输出样例

输入示例

5

输出示例

1 2 3 4 5 6 7 8 9 10
1:6 1 7 2 8 3 9 4 10 5
2 : 3 6 9 1 4 7 10 2 5 8
3 : 7 3 10 6 2 9 5 1 8 4
4 : 9 7 5 3 1 10 8 6 4 2
5 : 10 9 8 7 6 5 4 3 2 1
6 : 5 10 4 9 3 8 2 7 1 6
7 : 8 5 2 10 7 4 1 9 6 3
8 : 4 8 1 5 9 2 6 10 3 7
9 : 2 4 6 8 10 1 3 5 7 9
10 : 1 2 3 4 5 6 7 8 9 10
m = 10

---

题目分析与解法

✅ 模拟方法分析：

1. 初始化原始牌序：$[1, 2, 3, \dots, 2n]$；
2. 实施如下洗牌过程，直到牌序恢复为初始状态：

• 新牌序的第 $2k$ 个位置放置原牌序的第 $k$ 张；
• 新牌序的第 $2k - 1$ 个位置放置原牌序的第 $n + k$ 张；
• 循环计数，记录每次洗牌结果并与初始牌序比较；

3. 若相同，则输出总次数 $m$。

---

边界细节说明

*当 $n = 1$ 时，即 $[1, 2]$，第一次洗牌为 $[2, 1]$，第二次即还原；

• $n$ 最大为 $9999$，程序需要在合理时间内完成；
• 洗牌次数上限可设为 $10000$ 以防死循环。

---

时间复杂度分析

操作	复杂度
每次洗牌	$O(n)$
最多洗牌次数	$O(n \cdot m)$
最坏情况下总复杂度	$O(n \cdot 10000)$

---