如果让我选一道“题目很短、坑很深”的 UVA 老题我会投 UVa 151 Power Crisis。它看起来就是约瑟夫环给你 n 个编号区域找到一个最小的 m让 13 号区域最后停电。可如果你拿标准约瑟夫递推去套连样例 n17 都过不了。原因在于题面里 1 号区域是固定先停的之后的“每隔 m 个停一个”才真正开始。这篇文章会把“先拿走 1 号”这个变形讲透包括递推式的来源、手算 17 的完整过程以及能直接提交的 C 和 Python 代码。1. 重新读题这不是标准的“数到 m 被杀”而是“1 号先出局”1.1 题面规则里最关键的一行UVa 151 Power Crisis 的输入很简单每行一个 n读到 0 结束。输出是一个 m要求在这个 m 下最终停下来时剩下的那个区域编号是 13。真正的坑在规则描述里。题面并不是让你从 1 号开始数 1、2、3……数到 m 再停掉第 m 个。它说的是1 号区域第一个被停掉然后从 2 号区域开始在仍然供电的区域里继续数 m 个再停掉第 m 个。也就是说1 号是“内定”的第一刀后面才开始做约瑟夫环。这一行如果漏看后面全错。我当年就是先写了标准约瑟夫函数跑样例 17 的时候得到了一个完全不同的数字先是一脸懵后来才回去逐字读题。1.2 标准约瑟夫 vs 本题变体假设 n17m7。如果按标准约瑟夫“从 1 号开始数 7 个停掉第 7 个”那么第一刀切在 7 号递推算下来最后幸存的是 2 号。如果按本题规则“1 号先停然后从 2 号开始数 7 个”第一刀切完 1 号之后第二刀会切在 8 号最终幸存者正好是 13 号。规则n17, m7 的第一刀最终幸存标准约瑟夫72UVa 151 变体113所以这个题的解题思路必须从一开始就改成先把 1 号从环里拿走再对剩下的 n-1 个节点做约瑟夫问题。1.3 样例反推17 对应 7 不是巧合实际手动模拟 n17, m7按本题规则的停电顺序是1 - 8 - 15 - 6 - 14 - 7 - 17 - 11 - 5 - 3 - 2 - 4 - 10 - 16 - 9 - 12最后剩下 13 号。这条顺序如果能在草稿纸上推一遍你对这个题的理解会比直接背代码深很多。注意中间会有跨过结尾继续数的情况比如数到 17 之后会回到 2、3、4……这也是约瑟夫环最核心的“循环取模”思想。2. 把区域重新编号为什么代码里判断的是 11而不是 132.1 拿走 1 号后剩下的区域是什么1 号已经先出局所以剩下的节点是2, 3, 4, ..., n这串节点一共有 n-1 个。如果给它们重新编号从 0 开始0 号对应原区域 21 号对应原区域 32 号对应原区域 4...11 号对应原区域 13所以“13 号区域最后幸存”等价于“在新编号里下标 11 幸存”。这个映射关系就是整个代码里 11的来源。如果这里直接写 13哪怕递推式写对了答案也一定错。2.2 约瑟夫递推式到底怎么来的现在的问题变成有 N n-1 个节点按环形排列每轮从当前位置开始数 m 个杀掉第 m 个求最后幸存者的 0 基下标。设J(i)表示当环里还剩 i 个节点时最后幸存者在当前环中的下标0 基。显然i 1 时只剩一个人幸存者下标是 0i 1 时第一刀会杀到下标(m-1) % i的位置杀掉这个位置后下一轮从它后面的那个节点开始数。如果把剩下的 i-1 个节点重新从 0 编号那么幸存者的新编号是J(i-1)。把新编号映射回旧编号时需要加上第一刀后面的偏移也就是m mod i。所以J(i) (J(i-1) m) % i这个式子不需要死记。你只需要记住每杀一个人环的长度减一但起点往后挪了 m 个位置取模就是为了处理循环绕圈。2.3 这里用 n 还是 n-1是最大的分水岭很多帖子里的代码写的是for (int i 2; i n; i) s (s m) % i;这是标准约瑟夫适用范围是“从第 1 个人开始数 m 个然后杀掉”。但本题一开始就强制把 1 号杀了所以不能直接对 n 个节点套。正确做法是只对 n-1 个剩余节点做递推for (int i 1; i n - 1; i) s (s m) % i;i从 1 到 n-1代表剩余节点数逐渐从 1 增长到 n-1。这实际上是在做动态规划式的递推而不是真的去模拟删除。3. 手推 n17答案为什么是 73.1 先看 m1 到 m7 的最终结果因为题目要求最小的 m所以从 m1 开始逐层检查。我只列出递推到最后一轮时J(16)的最终值也就是在新编号下最后幸存者的下标。mJ(16)对应原区域115172023794025576121471113可以看到 m6 的时候其实已经很接近了最后幸存的是 14 号就差一位。但 m7 的时候J(16)11对应原区域 13 号所以最小答案就是 7。3.2 m7 的完整递推表如果你第一次接触这个递推式可能会觉得它太抽象。我把 m7 时每一轮的J(i)列出来你可以对着算一遍i12345678910111213141516J(i)0121344318411512411计算过程就是反复执行J(i) (J(i-1) 7) % i例如J(12) (J(11) 7) % 12 (4 7) % 12 11J(13) (11 7) % 13 18 % 13 5J(16) (4 7) % 16 11最后J(16)11映射回原区域就是 13。整个过程一点魔法都没有就是每一轮更新一下幸存者的相对位置。4. 能直接提交的 C 和 Python 代码4.1 C 版本这里用最直接的写法每找到一个 n就从 m1 开始往上试。#include bits/stdc.h using namespace std; int survivorIndex(int n, int m) { // n 是原始区域数 // 1 号已经先停掉所以只对 n-1 个节点做约瑟夫递推 int s 0; // 0 基下标剩下 1 个节点时幸存者下标是 0 for (int i 1; i n - 1; i) { s (s m) % i; } return s; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; while (cin n n) { int m 1; // 目标是新编号里的 11也就是原区域 13 while (survivorIndex(n, m) ! 11) { m; } cout m \n; } return 0; }需要注意for (int i 1; i n - 1; i)这个n - 1是整个解法的关键。如果你写成i n就把 1 号也放进递推里了样例直接挂。4.2 Python 版本Python 在 UVA 老平台上不算快但 n 的数据范围很小这个写法完全够用。import sys def survivor_index(n, m): s 0 # i 从 1 到 n-1对应剩余节点数从 1 增长到 n-1 for i in range(1, n): s (s m) % i return s def main(): out [] for line in sys.stdin: n int(line.strip()) if n 0: break m 1 while survivor_index(n, m) ! 11: m 1 out.append(str(m)) sys.stdout.write(\n.join(out)) if __name__ __main__: main()Python 的range(1, n)会生成 1 到 n-1正好对应 C 里的循环范围。4.3 提交前一定要确认的四个边界n13 时答案应该是 1。因为 1 号先停然后 2、3、4……12 依次被停最后剩下 13 号。n14 时答案不是 1而是 18。这说明 m 完全可能大于 n不能枚举到 n 就停。n17 时答案必须是 7这是样例。输入遇到 0 要直接终止不要再输出一行结果。5. 枚举细节m 的上限、预计算和更大数据5.1 千万不要加“m n”的剪枝很多第一次做的人会顺手写成for (m 1; m n; m)这是错的。n14 时答案就是 18远远超过 n。原因很简单约瑟夫环里每轮数 m 个本质是“从当前位置向后偏移 m”这个偏移可能绕过整个环好几圈。m 本身可以很大取模之后的效果才会最终体现在位置上。你搜索的是原始 m而不是每轮取模后的余数所以不能按 n 限制搜索范围。5.2 多组输入时可以考虑打表UVA 的输入可能有很多个 n。最朴素写法是每个 n 独立搜索但如果同一样例里同一个 n 出现多次重复计算会显得浪费。更稳的做法是先读入所有 n记录最大值然后一次性算出来。vectorint query; int x; while (cin x x) query.push_back(x); vectorint ans(101, 0); for (int n 13; n 100; n) { int m 1; while (survivorIndex(n, m) ! 11) m; ans[n] m; } for (int n : query) cout ans[n] \n;这样预处理一次后续每组数据都是 O(1) 查表本地测试也会舒服很多。5.3 如果进一步追问怎么处理更大的 n如果 n 变成 1e7枚举 m 加 O(n) 递推显然不行。标准约瑟夫有一种分段跳跃优化核心思想是当s m i时下一轮不会触发取模s会直接加上m。于是一次可以跳过很多轮而不是每一轮都执行一次取模。不过对 UVa 151 来说n 很小老老实实枚举就是最不容易出错的方案。除非你想拿这个题目练手写约瑟夫加速否则不要为了炫技把代码写复杂。6. 我实际踩过的三个坑6.1 目标值写成 13而不是 11这是最典型的 off-by-one。递推式返回的是 0 基下标而 13 号在“拿走 1 号后”的新序列里排第 12 个下标是 11。如果你非要用 1 基写法也可以这样s 1; for (int i 2; i n - 1; i) { s (s m - 1) % i 1; } if (s 12) ...1 基序列里 13 号对应第 12 个元素所以判断等于 12。两种写法本质一样但千万不要混递推用 0 基判断却写成 13。6.2 第一刀理解错导致递推对象多了一个节点某次我图省事直接写了标准约瑟夫递推然后把判断结果加 2。// 错误示范 for (int i 2; i n; i) s (s m) % i; if (s 2 13) ...这样 n17 会输出什么m7 的时候幸存下标是 1加 2 后是 3根本不是 13。问题就出在标准约瑟夫会把 1 号当成正常参与者而本题里 1 号是提前出局的。正确做法是在 n-1 个节点上做递推并且从 i1 开始。6.3 用模拟链表写逻辑没问题但容易 TLE我也见过有人用 vector 模拟删除vectorint v; // 把 2..n 放进去然后循环 v.erase(...)n 小的时候能过但代码又长又容易下标越界。递推写法只有一行核心代码推导过程清楚了之后写起来快得多。算法竞赛里能推导就不该模拟否则遇到多组数据会很被动。最后分享一个扩展思路如果题目改成“让 k 号区域最后幸存”在“1 号先停掉”的规则下只需要把判断条件改成TARGET k - 2其他代码完全不用动。因为这个题的本质就是先移除 1 号然后在一个长度为 n-1 的约瑟夫环里找幸存位置。理解了这一点下次看到任何“先固定杀掉一个再跑约瑟夫”的变形你都能立刻知道从哪里下手。