每次刷 UVa 的题目，总能在评论区看到“10行代码AC”这种字样，一开始我是不太信的，直到我自己把 UVa 10940(Throwing cards away II) 这道题看明白，才发现有些题确实不需要长篇大论。这道题表面上叫你“扔卡片”，明明白白写的是“Throwing cards”，但你真正动手去模拟的时候，数据范围一上来，队列直接爆掉，这时候你就知道得靠数学规律。它和约瑟夫环有着极深的渊源，但又不是那种标准的、需要递推公式去硬啃的约瑟夫环，更像是一个披着约瑟夫环外衣的找规律题。这篇文章我就把自己从暴力模拟开始，一步一步找到规律，最后用极简代码通过的全过程写出来，包括我踩过的坑和一些容易被忽视的细节。不论你是刚开始刷题的新手，还是被大数据范围卡过时间复杂度的人，这篇内容应该都能给你一点启发。
1. 题目到底在干什么：理解扔卡片的游戏规则
1.1 题意拆解与数据范围
这道题的题意其实特别简单，简单到小学生都能听懂。有一堆牌，编号从 1 到 N，从上到下按顺序排列。每次操作你先把最上面那张牌扔掉，然后把接下来那张牌放到整堆牌的最下面。重复这个过程，直到只剩一张牌，问你最后剩下的那张牌编号是多少。
例如 N = 4 的时候，初始状态是 [1,2,3,4]。第一轮扔掉 1，把 2 放到最下面，牌堆变成 [3,4,2]。第二轮扔掉 3，把 4 放到最下面，牌堆变成 [2,4]。第三轮扔掉 2，把 4 放到最下面，牌堆变成 [4]。答案就是 4。看起来人畜无害，直接用队列模拟就能写。但问题在于数据范围，UVa 10940 的 N 可以给到多大呢？题面里没写得很死，但你要是按着原题第一问 Throwing cards away I 的习惯去写，也就是直接打印每次扔掉的牌，那必然卡时间。这道题只问你最后一张，却允许一个非常大的 N，这就逼着你不能老老实实模拟。
我记得我做这道题的时候，第一反应是“这不就是队列嘛，一小时能写完”。结果提交的时候看到时间是按照毫秒算的，我下意识觉得不对，马上回去翻了原题的数据范围。N 最大可以到多少我记不太清了，但保守估计，如果你用队列去模拟一个几十万甚至上百万的 N，虽然也能跑，但时间上已经有点危险了。更别提有些 OJ 的数据其实给得很恶意，直接用暴力模拟去碰撞，等待你的就是 TLE(Time Limit Exceeded)。
1.2 为什么说它和约瑟夫环相关
很多新手看到“Throwing cards away II”这题，第一反应就是“约瑟夫环”。说实话，它确实算约瑟夫环的一个变种。在标准约瑟夫环问题中，围成一圈的人每隔 k 个杀掉一个，求最后幸存者的编号。这道题里，“扔掉一张牌”相当于杀掉一个人，“把下一张牌放到最底下”相当于把这个人挪到圆圈的最后面，等待后续的“处决”。整个过程完全符合“环形结构中按固定步长剔除元素”的定义。
但它又不是纯粹的约瑟夫环。标准约瑟夫环通常给出人数 N 和步长 k，让你用递推公式 f(N) = (f(N-1) + k) % N 去求幸存者。这里 k 其实等于 2，而且操作顺序是“先剔除，再后移”，所以它本质上是一个“k = 2 的约瑟夫环问题”。既然如此，为什么我们不能直接用约瑟夫环的递推式呢？很简单，因为那需要你用数组模拟一个循环链表，或者用动态规划递推，虽然可行，但这道题有更简洁的规律。你可以把这道题理解成“约瑟夫环家族里一个规律极其明显、可以用数学公式直接秒杀的特例”。如果你死记约瑟夫环递推公式，反而绕了远路。
为了直观理解这个“环形剔除”的过程，我建议把牌堆想象成一个环形队列，有一个指针永远指着当前要处理的牌。每次操作，指针指向的牌被拿走，然后指针顺时针移动一步。这和我们熟悉的丢手绢游戏几乎一模一样——只是每一次都必须把“手绢”往后传一格。理解了这一点，后面找规律的时候思路就顺了。
2. 从暴力模拟到规律初现：小数据铺路
2.1 用队列模拟的常规思路
先说说最笨的办法。写一个队列，初始化压入 1 到 N，然后循环：把队首弹出并记录，再把新队首弹出并压入队尾。重复直到队列只剩一个元素。这套逻辑本身没有任何问题，而且对于 N 比较小的情况完全够用。我还记得我第一次用 C++ 写的时候，代码大概长这样：
#include <bits/stdc++.h> using namespace std; int main() { int n; while (cin >> n && n) { queue<int> q; for (int i = 1; i <= n; i++) q.push(i); while (q.size() > 1) { q.pop(); // 扔掉最上面的 int top = q.front(); q.pop(); // 取下一张 q.push(top); // 放到最下面 } cout << q.front() << endl; } return 0; }你拿去跑 N = 7，输出 6；跑 N = 10，输出 4。一切都符合直觉。但问题来了：如果 N 的量级到 1e6，队列操作虽然是 O(N) 的，但每轮操作涉及出队、入队、指针移动，常数不小。O(N) 的时间复杂度对于这种题其实能过，但空间复杂度也很伤脑筋，队列要开一个大小为 N 的容器。最关键的是，很多老 OJ 的时限极其苛刻，哪怕 O(N) 也可能被卡在某个边缘。这就是为什么我们要去寻找隐藏的数学结构。
2.2 手算小数据：寻找打印序列里的秘密
为了找到规律，我手工列了一张表，从 N=1 到 N=20，把答案一个个算出来。这里我强烈建议你也自己算一遍，因为只有在纸上画过，才能体会规律出现时的那种兴奋感。我列出的结果如下：
| N | 最后剩下的牌 |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 2 |
| 4 | 4 |
| 5 | 2 |
| 6 | 4 |
| 7 | 6 |
| 8 | 8 |
| 9 | 2 |
| 10 | 4 |
| 11 | 6 |
| 12 | 8 |
| 13 | 10 |
| 14 | 12 |
| 15 | 14 |
| 16 | 16 |
这张表一出来，规律其实已经写在脸上了。你看 N=1、2、4、8、16 这些 2 的幂次方，答案等于它本身。而在相邻两个 2 的幂之间，答案是从 2 开始逐渐递增的偶数。举个例子，N=9 到 N=16 之间，答案依次是 2、4、6、8、10、12、14、16。N=5 到 N=8 之间，答案依次是 2、4、6、8。也就是说，答案序列在每个“2 的幂”区间里，都会重新从 2 开始走一遍。
这个规律可以用一句话说清楚：找到小于等于 N 的最大的 2 的幂 P，那么答案就是 2 * (N - P) + 2，但有一个例外——当 N 正好等于 P 时，答案是 N。其实这个例外也符合公式：如果 N=P，那么 2 * (N - P) + 2 = 2，显然不对。所以要把公式稍微修正一下，或者单独判断 N 是否为 2 的幂。另一个等价的说法是：令 ans = 2 * (N - P)，如果 ans 为 0 则答案为 N，否则答案为 ans。这两种说法本质是一样的，只是写法不同。
2.3 为什么答案会呈现这种“重新计数”的规律
在解释公式之前，我想说说这个过程为什么会产生这样漂亮的规律。核心在于，每次扔掉第一张、再把第二张移到底部，本质上是在把原本的偶数牌保留下来，奇数牌全部丢掉。你仔细想一想，第一轮操作之后，编号为奇数的牌全部被扔掉，剩下的全是偶数。然后在下一轮，这些偶数牌又按照同样的规则被处理，此时它们的相对编号相当于“除以 2”。这就意味着问题 N 可以递归地归结为 N/2 的问题。用数学语言表达就是：如果 N 是偶数，那么答案为 2 * f(N/2)；如果 N 是奇数，那么答案为 2 * f((N-1)/2)，但具体细节还需要微调。不管怎么说，这个递归特性告诉我们，最终答案只与 N 的二进制表示中最高位的位置有关。
我自己琢磨这个问题的时候，打了个比方。这个过程就像你手头有一张名单，第一次筛选把奇数行全划掉，留下偶数行，然后给这些偶数重新编号成 1、2、3……接着再做一轮筛选。每一轮都会把规模减半，直到只剩一个。所以答案其实就是原编号经过若干次“乘以 2 再调整”之后的结果。理解了这一点，你就明白为什么 2 的幂次方附近会出现规律性的重复了。这比单纯记公式牢靠得多，因为你知道了公式是“怎么长出来”的。
3. 从规律到代码：寻找最高位 2 的幂
3.1 如何快速求出不超过 N 的最大 2 的幂
既然规律依赖于“小于等于 N 的最大 2 的幂 P”，那么怎么高效求出这个 P 就成了关键。新手最容易想到的办法是循环：
int p = 1; while (p * 2 <= n) p *= 2;这个循环在 N 很大的时候也很快，因为循环次数是 O(log N)。但对于追求极致简洁的人来说，可以用位运算一行搞定。比如：
int p = 1 << (int)log2(n);用 log2 求得 N 的二进制位数，然后左移得到对应幂次。不过考虑到浮点数误差，我更推荐用循环，或者用 C++ 的内置函数：int p = 1; while ((p << 1) <= n) p <<= 1;。这个方法不需要引入任何头文件，也不会有精度问题，是我个人最喜欢的写法。
还有一种技巧叫做“把最高位之后的所有位都变成 1”，然后加 1。比如 N=21，二进制是 10101，我们把最高位之后的位全部置成 1 得到 11111（十进制 31），再右移一位得到 15，但这是“小于 N”的最大 2 的幂吗？不是，15 不是 2 的幂，所以这个思路在这个问题里不完全适用。更直接、更稳妥的做法还是用 while 循环找最高位。
3.2 极简代码：完整实现
把上面这些综合起来，完整的核心代码可以写成这样：
#include <iostream> using namespace std; int main() { int n; while (cin >> n && n) { int p = 1; while ((p << 1) <= n) p <<= 1; int ans = (n == p) ? n : (n - p) * 2; cout << ans << endl; } return 0; }这个代码量确实不足 10 行，跑起来飞快，因为每次输入只做 O(log N) 的计算。我看到有人的写法是cout << (n == p ? n : (n - p) * 2) << endl;，甚至可以把 cout 放在条件表达式里，但可读性会差点。我个人还是喜欢拆开写，因为这样调试的时候方便打日志。
如果你用的是 Java，道理完全一样：
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNextInt()) { int n = sc.nextInt(); if (n == 0) break; int p = 1; while ((p << 1) <= n) p <<= 1; System.out.println(n == p ? n : (n - p) * 2); } } }Python 版本就更简单了，只是注意输入是多行，直到 0 结束：
import sys for line in sys.stdin: n = int(line.strip()) if not n: break p = 1 while (p << 1) <= n: p <<= 1 print(n if n == p else (n - p) * 2)你可能会问，为什么要特判 n == p？因为当 N 是 2 的幂时，不用公式也能推断出答案是它本身。如果你懒得特判，也可以用另一个等价写法：int ans = (n - p) * 2;但当 n == p 时 ans 为 0，需要额外处理。两者没有本质差别，看你喜欢哪种。我个人觉得，特判 n == p 的写法语义最清晰，因为它直接点出了“2 的幂次方是特殊情况”的本质。
3.3 为什么 10 行代码就够：复杂度与雅致性
这道题用 O(1) 或 O(log N) 的解法，理论上无论 N 给到什么量级（哪怕是 1e9），都能眨眼间算出来。队列模拟虽然好写，但要开 O(N) 的容器，时间复杂度也是 O(N)，丢到极端数据里很容易超时。这里我还想多说一句，有些人在 OJ 上提交时用位运算int p = 1 << (int)log2(n);然后发现答案错误或者偶发的精度问题。原因是 log2 返回浮点数，如果 N 刚好是 2 的幂，log2(N) 可能在浮点表示下变成 3.9999999，强制转换成 int 就变成 3，导致 p 算错。所以在竞赛里，能用位运算和整数运算解决的事，不要依赖浮点数，这是我的一个铁律。
如果你坚持想用微软风格的_BitScanReverse或者 GCC 的__builtin_clz来求最高位，也可以，但对这道题来说没有必要。代码的“雅致”不在于用了多少高级函数，而在于逻辑简洁、边界处理干净、别人一看就懂。10 行代码 AC 的“10 行”说法，其实是一个象征，代表你在理解了数学本质之后，代码自然就短了。这就像你知道了一个房子的承重结构，就不需要堆砌多余的柱子一样。
4. 常见易错点与排查思路：这题坑在哪里
4.1 边界的 0 与极大的 N
UVa 的题目惯例是输入以 0 结束，所以循环里首先要判断 n 是否为 0。很多新手一上来忘了判断 0 就进入主逻辑，导致输入 0 时输出一个错误的数字，或者直接死循环。还有一个小细节：虽然这题 N 是正整数，但你要想到，如果输入类似于 2147483647 这种接近 int 最大值的数怎么办？求 P 的过程中，p <<= 1有可能会溢出。
举例来说，假设 N 是 1073741824，这个数是 2 的 30 次方，那么 p 一直左移到 1073741824 时，p << 1等于 2147483648，这已经超过了 int 能表示的最大值 2147483647，此时有符号整数的左移是未定义行为，在多数编译器上会变成负数，从而跳出循环，但结果可能出问题。稳妥的做法是把 p 声明成 long long，或者用p = p * 2 <= n这种写法，乘法在溢出边缘同样危险，但 long long 至少能撑到 2^62，完全覆盖 int 的所有正数情况。我习惯把 p 开成 long long，反正题目也没要求省那么一点内存。
4.2 表观的“约瑟夫环递推公式”误用
这题在网上搜题解的时候，能看到有人用标准约瑟夫环的递推来解：f(1) = 0，f(n) = (f(n-1) + 2) % n，最后答案是 f(N) + 1。这个方法算出来的结果对几个例子是对的吗？我们验证一下。N=5 时，f(1)=0，f(2)=(0+2)%2=0，f(3)=(0+2)%3=2，f(4)=(2+2)%4=0，f(5)=(0+2)%5=2，答案 f(5)+1=3。但实际上 N=5 的正确答案是 2。为什么会差 1？因为标准约瑟夫环的定义是每人数到 k 就出局，而这道题是“先扔一张，再移一张”，操作错开了一个身位。如果你硬套公式，会在 N 的奇偶性上出错。这个案例告诉我们，针对具体问题的规则要具体分析，不能背一个模板就到处套。
如果你喜欢研究约瑟夫环，不妨把这道题和标准形式对比一下。标准形式里，k=2 时幸存者编号的规律是：把 N 写成二进制，把最高位去掉，然后在后面补一个 1，得到的二进制就是答案。比如 N=5（101），去掉最高位 1 剩下 01，再补一个 1 在最前面得到 011，也就是 3。但这是我们这道题的答案吗？不是，五分钟前我们验证过正确答案是 2。所以这两个问题尽管表面相似，底层的移位方向、剔除顺序略有不同，导致结果差了一位。这正好印证了那句话：做算法题，读题比做题更重要，差之毫厘谬以千里。
4.3 打印中间过程时被误导
我在推导规律时，有一段时间试图打印出每轮的牌堆状态，结果发现牌堆的顺序很混乱，尤其是在 N 是奇数的情况下，很难直观看出规律。后来我统计了“每轮保留的牌编号序列”，而不是“牌堆顺序”，才看出端倪。好比你想理解一个随机过程，盯着每一步的中间产物是看不清的，但把它抽象成函数映射，规律立刻浮现。
如果你也想自己找规律，我建议你用纸笔列这样的表：
- N=1 到 32 的答案
- 每个答案减去 2 的倍数，看余项
- 把 N 转换成二进制，与答案的二进制对比
这个过程非常培养数感，也是真正把这道题“变成自己的”所必需的。
5. 扩展思考：从这道题到其他“找规律”题型
5.1 找规律题的通用方法论
做多了 OJ 题目你就会发现，有一大类题根本不需要你设计复杂的算法，而是考察你能不能从数据中看出重复性和周期。它们的共同套路是：先暴力模拟小数据，列出输出序列，然后观察序列与输入的关系，最后总结成公式或递推。这个方法在 UVa 10940 上适用，在其他题目上同样适用。我记得自己第一次独立推导出这类公式时，那种兴奋感远远超过直接看题解，因为这代表了一种可持续的能力，而不仅仅是记忆。
具体怎么操作呢？给你一个推荐流程：
- 先用最朴素的模拟代码，把 N=1 到 20 的结果全部算出来。
- 把结果排成一行，观察增长趋势、周期、突变点。
- 当 N 翻倍时，看答案值如何变化。
- 试着把答案写成“关于 N 的某个简单函数”，比如分段函数。
- 用几个手算的例子验证公式，尤其要验证边界（2 的幂、2 的幂附近、N=1）。
- 最后才写极简代码。
这套流程看似费时间，但对于 UVa 这类老题极其有效，因为这些题目大多有简洁的数学背景，出题人根本不想考你复杂数据结构，而是考你有没有“数感”。
5.2 约瑟夫环家族的变式总结
约瑟夫环问题本身有很多版本，我大致整理一下，帮助你往后遇到同类题时有个框架：
- 标准约瑟夫环：围成一圈，固定间隔 k，问最后幸存者编号。解法是递推 O(N)。
- 每次先杀再移位：也就是这道题的变式，本质上可以看成 k=2 的约瑟夫环，但移位方向有讲究。
- 每次先移位再杀：操作顺序不同，公式也略有差异。
- 输出被杀顺序：这时你必须用线段树或树状数组来优化区间查询。
- N 巨大但询问很少：往往可以二分答案或找周期。
- 双人博弈版本：每次可以取走若干张，谁拿到最后一张谁赢，这类问题又变成巴什博弈或威佐夫博弈。
掌握这些分类，你看到“Throwing cards away II”就能迅速判断出它属于“约瑟夫环家族中的规律型”，然后对症下药。很多人觉得算法难，其实难在不会归类，不知道题目在考什么。见的多了，大脑自然会像搜索引擎一样，看到题目关键词就映射到对应解法。
5.3 这题还能怎么变：如果我改成每隔两张扔一张呢
如果将来有人把这道题改一改，变成“每次扔掉一张，然后移动两张到底部”或者“每次直接扔掉最上面两张”，那么规律会不会改变？当然会变，而且变得很有意思。你自己动手模拟一下就会发现，新的序列会呈现出另一种基于更高阶幂次的规律，可能是 3 的幂，可能是 2 的幂的变体。这正是数学的乐趣所在，从 1 到 2 到 3，每一次推进都会打开新的视野。
我个人认为，算法竞赛里最珍贵的能力不是背板子，而是迁移。你把 UVa 10940 的规律总结成“N 除以最高位 2 的幂之后的余数决定答案”，那么下次看到类似的扔牌题，你至少会想到去算余数，而不是一头扎进队列。这种思考方式是可以复利的。今天你花半小时分析这道看似简单的题目，未来可能帮你在一道更复杂的赛题里节省半小时甚至更多。
6. 个人体会：从一个卡题者的角度聊聊挣扎与突破
在真正看懂这道题之前，我其实卡了一阵子。当时我一直在纠结队列模拟能不能卡过时限，在网上搜了各种优化，比如用 deque（双端队列）代替 queue，甚至想过用循环数组。这些方法确实比最朴素的队列稍微快一点，但根本问题没有解决。直到我偶然把 N=1 到 16 的答案全部列出来，那个“偶数递增”的规律一下子击中了我。那一刻我意识到，自己之前一直在错误的方向上拼命优化，就像一辆车离家出走，越踩油门距离目标越远。
我做题的经验是，如果一道简单题你想了超过半小时还没有头绪，立刻停下来，别硬刚。去做点别的题，或者跟你身边的朋友讨论一下。很多算法的灵感不是坐在那里逼出来的，而是在放松的状态下突然跳出来的。UVa 10940 教会我的就是这个。不要因为别人 10 行代码 AC 就觉得自己笨，那只是因为他们比你早一步找到了规律。你需要的不是羡慕，而是动手列出那张表。
最后再分享一个小技巧。如果你跟我一样，平时习惯用 Python 打表、用 C++ 提交，那么你可以写一个生成数据的脚本，把 N=1 到 100 的答案全部跑一遍，然后把结果粘贴到 C++ 代码里作为查表答案。这在某些只要求一次询问的题里甚至可以直接 AC。但对于这道题，因为 N 的范围可能很大，而且输入有多组，查表就不现实了。作为一个临时调试工具、验证你的数学公式是否正确，它倒是非常好用。这种“打表找规律、写代码验证、再精简实现”的流程，适用于很多数学规律题，你也可以试试。
