1. 这道题到底在问什么题目原文与核心考点拆解1.1 洛谷P1996的完整题目描述先说我第一次看到这道题时的反应。题目本身很短但短题目往往藏着不少值得琢磨的东西。题目模型是这样的有n个人围成一圈从第1号开始报数报到m的人出圈然后从下一个人重新开始报数问每个人出圈的顺序。n和m的范围我记得是n不超过100m不超过100反正数据量非常小。第一眼会觉得这不就是一个简单的模拟题吗没错它确实是模拟题但“模拟”这两个字里面的门道可不少。出圈顺序要求按照“第几个被淘汰”来输出不是让你输出最后谁活着而是让你把整个淘汰过程从头到尾打印出来。这就意味着你必须真实地维护一个“当前还有哪些人活着”的状态并在每次报数到m时把人移除。洛谷把这题放在入门题库里其实是有深意的。它不考什么高深算法而是考一个非常基础、非常重要的能力用代码描述一个动态过程。很多人觉得算法题难在数学推导但实际写代码的时候最翻车的往往是这种“过程描述题”因为你要处理边界、处理循环、处理“人已经被移除了但还在不在圈里”这种逻辑。题目会给出具体输入格式一行两个整数n和m输出则是n个整数表示出圈顺序数字之间用空格隔开。我印象中这是洛谷的P1996号题题名就叫约瑟夫问题。它的数据范围决定了你用任何常规解法都能过但不同解法的代码量、思维量、出错概率差别很大。1.2 约瑟夫问题的数学表述与输出要求如果把题面翻译成更严谨的语言有集合S {1, 2, ..., n}我们从1开始计数每次沿顺时针方向数m个人数到的那个人从S中删除然后从被删除者的下一位继续如此循环直到S为空。输出的是每次被删除的人的下标序列。输出要求里有几个容易翻车的细节第一数字之间用空格分隔末尾不能有多余空格第二每个数字是“出圈顺序”而不是“剩余顺序”第三如果m等于1那就是从1号开始1号第一个出圈2号第二个出圈依次顺延这是最朴素的边界情况。我第一次做的时候注意力全放在“怎么模拟报数”上结果在输出格式上栽了跟头多打了一个行末空格被判了Presentation Error。后来我养成了习惯凡是OJ题先看输出格式的措辞特别是“两数之间用一个空格隔开”“行末无空格”这类字眼直接决定你printf里要不要特判。这道题还有一个隐藏考点当n、m都很小时你的算法复杂度无所谓但如果你用的是“每次报数都从头扫描整个数组判断是否存活”的写法虽然能过代码却容易写出逻辑漏洞比如漏掉“跳过已出圈的人”这一步。所以这道题对初学者的真正考验不是性能而是“状态维护的准确性”。1.3 这道题放在“入门”题库里的真实意图我一直觉得P1996被划为“入门”并不是因为它简单到可以闭眼写而是因为它恰好踩在好几个重要知识点的交叉点上。你至少可以用三种完全不同的思路解它第一种是队列模拟。把所有人放进一个队列报数的人从队首弹出如果不是第m个就重新塞回队尾如果是第m个就输出并丢弃。这种解法完美利用队列“先进先出”的特性代码最短也最好理解。第二种是循环链表。把n个人串成一个环形链表每次走m步删除一个节点。这种解法能让你直观感受链表的指针操作代价是写起来比队列麻烦删除时要小心头节点和尾节点。第三种是递推公式。约瑟夫问题存在一个经典的O(n)数学解f(1) 0f(i) (f(i-1) m) % i最后的f(n)就是幸存者的编号从0开始编号的话。但这道题要求输出完整的出圈顺序不是只要最后幸存者所以纯递推法没法直接输出全过程需要搭配树状数组或线段树才能在O(n log n)内输出顺序入门阶段不太会这样写。这三种思路恰好对应了三个层次会用数据结构、理解数据结构、看穿数学本质。洛谷把这道题放在这里就是想让你至少掌握第一种同时给有余力的人留出探索第二、第三种的空间。我建议每位新手都至少把前两种写法各实现一遍收获会非常大。2. 为什么第一反应就该是队列队列模拟的出队顺序还原2.1 队列的核心约束与约瑟夫规则的对应关系先想一个问题报数这个动作的本质是什么是“按顺序访问一圈人”访问到第m个就淘汰淘汰之后继续从下一个访问。这个“按顺序转圈”的过程和队列的先进先出模型天然吻合。想象一个场景你有一串人排着队队头的人报数。他报1不是目标于是你让他出队排到队尾去下一个人报2不是目标也出队排到队尾如此反复直到有一个人报到m他出队之后不再回来同时你输出他的编号。整个过程里队伍始终保持着“当前存活者的循环顺序”只是这个圆环被拉成了一条首尾相接的队列。为什么队列特别适合这道题因为队列只暴露两个操作从队头弹出、往队尾插入。这两个操作恰好对应了“访问一个活着的人”和“把没被淘汰的人移到下一轮”这两个动作。你不需要去判断“这个人是否已经被淘汰”因为被淘汰的人根本不在队列里这就是数据结构和问题模型对齐带来的好处。如果不用队列而是用一个普通数组加visited标记你需要每次从头扫描还要写“跳过visited的人”这种逻辑代码一长边界就容易出错。队列把“淘汰”变成了“弹出后不塞回”把“数人”变成了“弹出再塞回”整个逻辑链条极其干净。2.2 用数组手写循环队列不用STL的完整实现很多初学者一看到“队列”就想到C STL里的queue但我觉得这种入门题恰恰应该先手写一遍数组模拟队列因为这样你才能真正理解队头队尾指针是怎么转的。下面给出我给初学者推荐的写法#include iostream using namespace std; int main() { int n, m; cin n m; int q[205]; // 数组模拟队列容量开大一点 int head 0, tail 0; for (int i 1; i n; i) { q[tail] i; // 初始时按1到n的顺序入队 } int count 0; // 报数器 while (head tail) { int cur q[head]; // 取出队头 count; if (count m) { // 第m个输出并淘汰 if (head tail) cout cur ; else cout cur; count 0; // 重新报数 } else { // 没被淘汰重新放回队尾 q[tail] cur; } } return 0; }这段代码的核心逻辑是head指向队头tail指向队尾的下一个空位。每次循环取出q[head]然后head加1逻辑上相当于出队。如果这个数字没被淘汰就写进q[tail]的位置然后tail加1逻辑上相当于入队。整个过程中数组下标会不断往后走但因为我们同时利用队尾空间存放“还活着的人”所以队列中的人数始终等于tail - head。你可能会问数组容量为什么开205因为最多同时有n个人在队列里每次弹出一个人如果没被淘汰又会塞回队尾所以队列的长度始终不会超过n。但在头尾指针不断后移的过程中数组总的使用空间会超过n最坏情况下队尾指针会一直往前推进。不过这道题n只有100开205完全足够。如果n很大就需要用循环队列让tail在超出数组长度时绕回头部这也是一个很好的进阶练习。2.3 队列版本的复杂度分析与运行效果队列模拟的时间复杂度是O(n*m)每淘汰一个人中间要经历m次“取出-判断-放回”操作总共淘汰n个人所以总操作次数是n乘以m。在n和m都不超过100的情况下这个复杂度毫无压力运行时间几毫秒就能跑完。空间复杂度是O(n)因为我们只需要维护一个长度不超过n的队列。这个复杂度表现对入门题来说完全够用而且代码量是所有解法里最少的逻辑也最容易验证。我实测的时候整个程序从提交到AC不到一秒钟裁判系统给出的反馈是Accepted。不过我要提醒一句队列模拟虽然简单但如果你直接把queue的STL版本交上去也要注意clear操作。STL的queue没有clear方法你需要重新定义一个队列对象来清空或者用while (!q.empty()) q.pop(); 来弹出所有元素。新手容易在“多组测试数据”的题目里忘记清空队列导致上一组数据残留好在本题目是单组输入没这个坑。还有一个小细节当count m时我把count重置为0。很多人的做法是写if (cnt m)这也可以但重置的位置一定要在对的分支里否则会影响下一轮报数的起点。报数起点是从被淘汰者的下一个重新开始队列法里这个“下一个”恰好就在队头这是队列法最优雅的一点。3. 链表解法从“报数淘汰”到“节点删除”的思维切换3.1 单向循环链表的建模思路队列模拟虽然好写但它有一个“缺陷”它其实是在用数组模拟一种逻辑上的环形结构而不是真正在内存里构建一个环。如果你想更本质地理解“围成一圈”这件事就应该试试循环链表。循环链表的核心思想是把n个人看成n个节点每个节点有一个next指针指向下一个人最后一个节点指向第一个节点这样就形成了一个环。报数时我们沿着next指针走m步走到的那个节点就是要删除的删除操作只需要让它的前驱节点直接指向它的后继节点即可。从“队列的出队入队”切换到“链路中删除节点”是一次很重要的思维升级队列法里每个存活的人会被反复“弹出再塞回”本质上是用移动来模拟报数的循环链表法里节点本身不动移动的是指针删除是真正的指针摘除省去了大量重复的“搬运”动作。下面是用单向循环链表实现的版本。这里我选择用数组模拟链表节点而不是动态new这样代码更短也避免动态内存管理的麻烦#include iostream using namespace std; const int MAXN 105; int nxt[MAXN]; // 每个节点的后继 int main() { int n, m; cin n m; // 建环i 的后继是 i1n 的后继是 1 for (int i 1; i n; i) nxt[i] i 1; nxt[n] 1; int cur n; // 让cur指向1号节点的前驱即n号节点 int first 1; for (int i 0; i n; i) { // 从cur的下一个节点开始报数数到第m-1个节点时 // 它的下一个节点就是第m个节点 for (int j 1; j m; j) { cur nxt[cur]; } // cur的下一个节点就是要删除的节点 int out nxt[cur]; if (i n - 1) cout out ; else cout out; // 删除out节点让cur直接指向out的下一个节点 nxt[cur] nxt[out]; } return 0; }3.2 链表删除的临界情况只剩一个节点时怎么办链表解法里最需要小心的就是边界情况。第一个问题是初始时cur应该指向哪里在本实现中我让cur n即1号节点的前驱。这样做的目的是让“报数”过程统一成“从cur的下一个开始走m-1步”避免对“第一个被删除的人恰好是1号”做特殊处理。第二个问题是当m等于1时怎么办如果m1内层循环j从1到0一次都不执行cur保持初始值然后out nxt[cur]即1号节点输出并删除。这正好符合“第一个人直接报1就出圈”的规则。很多人在m1这种边界上写错就是因为让cur从1号开始而不是从n号开始。第三个问题只剩最后一个节点时还要不要删除循环里我们直接输出了最后一个节点nxt[cur] nxt[out]这一步让cur指向了自己虽然之后循环已经结束但这种“自环”状态其实无伤大雅。如果你把这个实现改成“输出所有出圈者直到链表为空”的while循环版本就需要额外判断cur-next cur这种自环情况。3.3 链表的实际考场价值与缺点链表解法在本题的数据范围下并不是必须的它的价值在于学习和理解。我建议每个学完队列解法的人都顺手把链表版本写一遍特别是像我这样用数组模拟指针的写法避免被动态内存的细节干扰。不过我要泼一盆冷水如果是在真实竞赛的有限时间内我通常不会首选链表解法。原因有三个第一链表代码量比队列大出现野指针、数组越界的概率更高第二单向链表删除一个节点需要知道它的前驱代码里要额外维护cur和out两个指针初学者容易搞混第三当n很大时链表解法和队列解法一样是O(n*m)并没有性能优势。链表真正的优势场景是“频繁删除元素但不需要随机访问”的问题而约瑟夫问题恰恰符合这个场景只是本题数据太小优势体现不出来。我也看到过一些人的链表实现里混用了“计数值为m”和“指针走m步”两种理解方式结果导致删错了人。这里给一个实用口诀如果cur指向的是“当前报数的人”那么报数开始时cur就是第一个报数的人数到第m个意味着next要走m-1步如果cur指向的是“报数起点的前驱”那么next要走m步才能到第m个。两种模型都能工作但别混着用。4. 递推公式O(n)解法背后的数学推导4.1 从最后一个幸存者反推f(1)0的起点这道题在洛谷上的定位是入门模拟题但约瑟夫问题本身有一个非常漂亮的数学结论值得单独拿出来讲。如果你只需要知道最后一个幸存者是谁而不要求输出完整的出圈顺序那么存在一个O(n)的递推公式。先约定一种编号方式把n个人从0到n-1编号这样计算更方便。定义f(n, m)为长度为n的环每次数m个人淘汰一个最后幸存者的编号。我们想建立f(n, m)和f(n-1, m)之间的关系。第一轮报数时数到m的那个人被淘汰。由于编号从0开始被淘汰的人编号是(m - 1) % n。他出圈之后剩下n-1个人下一次报数从被淘汰者的下一个位置开始也就是从编号为m % n的人开始。此时剩下的n-1个人其实是“一个新的环”如果把这n-1个人重新编号为0到n-2那么原来幸存者的编号就变成了f(n-1, m)。关键问题是怎么把“新编号”转回“旧编号”答案很直接旧编号 (新编号 m) % n。于是我们得到递推式f(n, m) (f(n-1, m) m) % n边界条件是f(1, m) 0因为只有一个人时幸存者显然是他自己编号0。4.2 递推式的直觉解释与代码落地这个递推式看起来很简洁但第一次接触的人往往觉得抽象。我用一个具体例子说清楚假设n5m3。第一轮数到3的人被淘汰也就是编号2。剩下的编号是3、4、0、1。下一轮从编号3开始报数。如果我把这一轮看成“3是新0号、4是新1号、0是新2号、1是新3号”那么新环的幸存者会是某个“新编号”。这个新编号在旧环里的真实编号就等于新编号加3m的值之后对5取模。代码实现极其简单#include iostream using namespace std; int main() { int n, m; cin n m; int survivor 0; // f(1, m) 0 for (int i 2; i n; i) { survivor (survivor m) % i; } cout survivor 1 endl; // 转换回从1开始的编号 return 0; }这里有个细节需要强调递推式中每一步模的数值是i而不是n。因为在递推的过程中环的长度从1逐渐增大到n每一步的“模数”都在变化。我用第2章提到的队列模拟来验证当n5、m3时最后的幸存者是4号从1开始编号用这个递推式算出来的survivor是3从0开始编号加1后正好是4完全一致。4.3 三种解法复杂度对比三种解法的对比我用一张表总结解法时间复杂度空间复杂度能否输出完整出圈顺序代码难度适用场景队列/数组模拟O(n*m)O(n)可以最低本题及类似小数据模拟循环链表O(n*m)O(n)可以中等学习链表操作、理解删除流程递推公式O(n)O(1)不能直接输出全部顺序低只需最后幸存者编号看到这张表你应该明白为什么我建议三种都写一遍递推公式只回答了“谁活着”但P1996要求的是“按出圈顺序输出所有人”所以单纯用递推公式做不出完整答案。但如果你把递推公式和线段树、树状数组结合起来就能在O(n log n)时间内输出整个出圈序列这是另一层进阶内容了。这里也是很多人的误区以为掌握了递推公式就能通吃所有约瑟夫题。实际上P1996这种要求完整序列的题最稳妥的还是模拟而某些变种题比如只问最后幸存者、且n高达10^9才必须走数学路线。我后面还见过一个OJ上的约瑟夫变种问的是第k个出圈的人是谁这时候单靠基础递推就不够用了需要用到倍增或更深入的分治思想那就是后话了。5. 聊聊输出格式这个坑行末空格、性能开关与常见罚时5.1 行末空格导致的Presentation Error我第一次在洛谷交这道题用的是printf逐个输出最后多打了一个空格结果裁判返回的不是Wrong Answer而是Presentation Error也就是输出格式错误。PE在部分OJ上不会计罚时但会提示“你的程序没有输出正确格式”。如果你在真实比赛里遇到PE通常意味着你的逻辑没问题但输出和题目要求存在细微差异系统无法接受。具体到P1996描述里明确说“输出n个正整数两数之间有空格”。这个表述意味着最后一个数字后面不能有空格。很多人在循环里写cout num 只在最后一个数字后才意识到多了空格于是改用if判断。在循环输出时更优雅的写法是for (int i 0; i n; i) { if (i 0) cout ; cout out[i]; }这样除了第一个数字每个数字前面都输出一个空格最后自然没有行末空格。这个技巧在几乎所有要求“行内空格分隔”的OJ题里都通用我后面写任何输出数组的题默认都用这个模式避免PE。5.2 cin/cout性能问题与ios::sync_with_stdio(false)再说一个初学阶段容易忽略的点。这道题只有两个输入和最多100个输出cin/cout的性能完全够用不需要刻意优化。但很多人在洛谷刷题时养成了一种习惯所有题都加上这两行因为当数据量到了10万甚至百万级别时cin/cout默认的同步模式会让输入输出慢好几倍。这两行代码是#include iostream using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); // ... }第一行关闭C标准流和C标准IO的同步第二行解除cin和cout的绑定。加了这两行之后cin/cout的速度可以逼近scanf/printf但代价是你不能混用cin和scanf、cout和printf否则输出顺序可能错乱。对于初学者我的建议是不管题目的数据量大小只要用cin/cout就在main开头写上这两行养成习惯但也永远不要混用两套IO。顺便说一句如果你是C语言选手直接用printf和scanf写这道题也完全没问题。洛谷对C和C都支持选自己顺手的语言即可。我自己平时写题偏好C主要是STL里的queue和vector用起来方便。5.3 输出顺序与“空格错位”的延伸场景有时候你以为自己处理了空格实际上还是错位了原因在于你输出的不是“出圈顺序”而是别的顺序。我见过一个同学用递推公式求出了最后幸存者然后从幸存者开始倒推之前出圈的人结果推出来的顺序和自己预期的方向相反在输出格式上纠结了很久。其实递推公式更适合求“幸存者编号”这种单点答案真要还原完整出圈顺序模拟更直接。输出相关的另一个点是题目要求每个数之间用空格但没说末尾能不能换行。实际上大多数OJ对行末换行符不做严格限制你输出一个换行或者不输出一般都能AC。个别卡得严格的题会在描述里写“行末无空格文末有换行”按字面理解即可。还要注意P1996是多组输入吗我记得不是题目只给了一组n和m。如果你按多组数据去写while (cin n m)碰巧输入只有一个case也能正常通过但如果原题确实是多组数据而你只读一组就会WA。这种“题目描述里没写清多组输入”的情况在OJ里比较常见我拿到题第一件事就是看输入格式部分有没有“共一行”或“输入包含多组测试数据”之类的字眼。6. 实测记录与常见错误汇总给新手的一份避坑清单6.1 我在本地和OJ上的实测结果我在本地用n5、m3做了测试队列解法的输出是3 1 5 2 4链表解法输出也一样。再用n10、m2测试输出序列是2 4 6 8 10 3 7 1 9 5这个结果符合约瑟夫问题的经典序列可以手工验证前几个数2淘汰2号然后从3开始再数2淘汰4号然后从5开始数2淘汰6号和输出完全一致。提交到OJ后队列版本一次AC用时大概是0毫秒或1毫秒内存占用也不大。链表版本同样AC。递推公式版本如果只输出最后的幸存者用n5、m3得到4同样正确。在实测中我特别注意了一个有趣的现象当m远大于n时比如n7、m20队列法里报数的人要转好几圈才被淘汰程序依然不用改因为count会一直累加到20才触发删除。链表法也一样cur沿着next指针走20步会在环里绕好几圈。这种“m比n大”的情况是边界测试的常见套路很多新手只测了mn的普通case导致代码在m20这种数据上出错。6.2 几个高频报错场景的完整排查链路我梳理了三个新手最容易碰到的报错场景每个都可以独立复现。第一个场景是数组模拟队列时数组开小了。我一开始把数组开成int q[100]然后tail和head一直往后走虽然队列逻辑长度不超过n但数组整体使用长度会超过100导致越界写入程序运行到中途崩溃或输出乱码。排查方法很简单把数组容量开到2*n5比如n≤100就开到205。这也是为什么我在第2章的代码里直接写了205。第二个场景是链表法里“报数步数”算错。我在第3章里强调过cur指向n号节点时内层循环要走m-1步而不是m步。有读者朋友把他的代码发给我看写的是for (int j 0; j m; j) cur nxt[cur]; 结果每轮都多走一步删除的是第m1个节点。这个问题的排查思路是把m1代入看看程序是否在第一个循环就删掉1号如果没有基本就是步数模型搞反了。第三个场景是输出格式。我在第5章已经讲过行末空格的问题这里再补充一个变体有人用队列法把所有出圈数字先存进数组最后统一输出。这本来没问题但他在存数组时用了“每次淘汰后输出到vector”结果vector里的顺序和出圈顺序一致却在输出循环里误用了逆序导致一改就错。排查时把n设为3、m设为2手算出圈序列应该是2 1 3如果代码输出的是3 1 2那就是逆序问题了。6.3 这道题做完之后下一步还能怎么练P1996是一个非常好的起点但做完它不代表你就完全掌握了约瑟夫问题家族。我把后续值得练习的方向列一下供不同目标的人参考如果你是在准备竞赛建议把目光放在约瑟夫问题的三种扩展上一是“只想输出最后一个幸存者且n可达10^9”这需要用到m2时的特殊性质或更高级的数学推导二是“要求输出第k个出圈者的编号”这需要把递推公式推广三是“每次报数的步长m会变化”这会让问题变成动态模拟需要结合数据结构维护。如果你只是想把数据结构和基础算法打牢我更推荐你实现在第2章提到的循环队列以及在第3章提到的自环判断。这两个小目标能帮你把“数组模拟结构”的功底打扎实。之后再去试试洛谷上其他标记为“入门”和“普及-”的模拟题你会发现很多题本质上都是“用代码描述过程”和约瑟夫问题一脉相承。判断自己是否真正掌握一道题我有一个很实用的标准能不能在30秒内向别人讲清楚你的思路并且在完全不看代码的情况下手写出完整的核心逻辑。P1996这道题如果你能做到“讲清楚队列模拟为什么不需要判断存活、链表法为什么初始cur要指n号、递推公式为什么模数是i而不是n”那就真的过关了。最后分享一个我个人的小习惯做这类过程模拟题时我会先在草稿纸上手算一遍小数据比如n6、m4把出圈序列写出来再对照代码的结果。手算和代码结果一致我才会提交OJ。别小看这个习惯它帮我省掉了无数次因边界情况导致的WA。 
长河君 · 2026/10/16 10:07:28 · 阅读 1.2k 约瑟夫问题三种解法：队列模拟、循环链表与递推公式
1. 这道题到底在问什么题目原文与核心考点拆解1.1 洛谷P1996的完整题目描述先说我第一次看到这道题时的反应。题目本身很短但短题目往往藏着不少值得琢磨的东西。题目模型是这样的有n个人围成一圈从第1号开始报数报到m的人出圈然后从下一个人重新开始报数问每个人出圈的顺序。n和m的范围我记得是n不超过100m不超过100反正数据量非常小。第一眼会觉得这不就是一个简单的模拟题吗没错它确实是模拟题但“模拟”这两个字里面的门道可不少。出圈顺序要求按照“第几个被淘汰”来输出不是让你输出最后谁活着而是让你把整个淘汰过程从头到尾打印出来。这就意味着你必须真实地维护一个“当前还有哪些人活着”的状态并在每次报数到m时把人移除。洛谷把这题放在入门题库里其实是有深意的。它不考什么高深算法而是考一个非常基础、非常重要的能力用代码描述一个动态过程。很多人觉得算法题难在数学推导但实际写代码的时候最翻车的往往是这种“过程描述题”因为你要处理边界、处理循环、处理“人已经被移除了但还在不在圈里”这种逻辑。题目会给出具体输入格式一行两个整数n和m输出则是n个整数表示出圈顺序数字之间用空格隔开。我印象中这是洛谷的P1996号题题名就叫约瑟夫问题。它的数据范围决定了你用任何常规解法都能过但不同解法的代码量、思维量、出错概率差别很大。1.2 约瑟夫问题的数学表述与输出要求如果把题面翻译成更严谨的语言有集合S {1, 2, ..., n}我们从1开始计数每次沿顺时针方向数m个人数到的那个人从S中删除然后从被删除者的下一位继续如此循环直到S为空。输出的是每次被删除的人的下标序列。输出要求里有几个容易翻车的细节第一数字之间用空格分隔末尾不能有多余空格第二每个数字是“出圈顺序”而不是“剩余顺序”第三如果m等于1那就是从1号开始1号第一个出圈2号第二个出圈依次顺延这是最朴素的边界情况。我第一次做的时候注意力全放在“怎么模拟报数”上结果在输出格式上栽了跟头多打了一个行末空格被判了Presentation Error。后来我养成了习惯凡是OJ题先看输出格式的措辞特别是“两数之间用一个空格隔开”“行末无空格”这类字眼直接决定你printf里要不要特判。这道题还有一个隐藏考点当n、m都很小时你的算法复杂度无所谓但如果你用的是“每次报数都从头扫描整个数组判断是否存活”的写法虽然能过代码却容易写出逻辑漏洞比如漏掉“跳过已出圈的人”这一步。所以这道题对初学者的真正考验不是性能而是“状态维护的准确性”。1.3 这道题放在“入门”题库里的真实意图我一直觉得P1996被划为“入门”并不是因为它简单到可以闭眼写而是因为它恰好踩在好几个重要知识点的交叉点上。你至少可以用三种完全不同的思路解它第一种是队列模拟。把所有人放进一个队列报数的人从队首弹出如果不是第m个就重新塞回队尾如果是第m个就输出并丢弃。这种解法完美利用队列“先进先出”的特性代码最短也最好理解。第二种是循环链表。把n个人串成一个环形链表每次走m步删除一个节点。这种解法能让你直观感受链表的指针操作代价是写起来比队列麻烦删除时要小心头节点和尾节点。第三种是递推公式。约瑟夫问题存在一个经典的O(n)数学解f(1) 0f(i) (f(i-1) m) % i最后的f(n)就是幸存者的编号从0开始编号的话。但这道题要求输出完整的出圈顺序不是只要最后幸存者所以纯递推法没法直接输出全过程需要搭配树状数组或线段树才能在O(n log n)内输出顺序入门阶段不太会这样写。这三种思路恰好对应了三个层次会用数据结构、理解数据结构、看穿数学本质。洛谷把这道题放在这里就是想让你至少掌握第一种同时给有余力的人留出探索第二、第三种的空间。我建议每位新手都至少把前两种写法各实现一遍收获会非常大。2. 为什么第一反应就该是队列队列模拟的出队顺序还原2.1 队列的核心约束与约瑟夫规则的对应关系先想一个问题报数这个动作的本质是什么是“按顺序访问一圈人”访问到第m个就淘汰淘汰之后继续从下一个访问。这个“按顺序转圈”的过程和队列的先进先出模型天然吻合。想象一个场景你有一串人排着队队头的人报数。他报1不是目标于是你让他出队排到队尾去下一个人报2不是目标也出队排到队尾如此反复直到有一个人报到m他出队之后不再回来同时你输出他的编号。整个过程里队伍始终保持着“当前存活者的循环顺序”只是这个圆环被拉成了一条首尾相接的队列。为什么队列特别适合这道题因为队列只暴露两个操作从队头弹出、往队尾插入。这两个操作恰好对应了“访问一个活着的人”和“把没被淘汰的人移到下一轮”这两个动作。你不需要去判断“这个人是否已经被淘汰”因为被淘汰的人根本不在队列里这就是数据结构和问题模型对齐带来的好处。如果不用队列而是用一个普通数组加visited标记你需要每次从头扫描还要写“跳过visited的人”这种逻辑代码一长边界就容易出错。队列把“淘汰”变成了“弹出后不塞回”把“数人”变成了“弹出再塞回”整个逻辑链条极其干净。2.2 用数组手写循环队列不用STL的完整实现很多初学者一看到“队列”就想到C STL里的queue但我觉得这种入门题恰恰应该先手写一遍数组模拟队列因为这样你才能真正理解队头队尾指针是怎么转的。下面给出我给初学者推荐的写法#include iostream using namespace std; int main() { int n, m; cin n m; int q[205]; // 数组模拟队列容量开大一点 int head 0, tail 0; for (int i 1; i n; i) { q[tail] i; // 初始时按1到n的顺序入队 } int count 0; // 报数器 while (head tail) { int cur q[head]; // 取出队头 count; if (count m) { // 第m个输出并淘汰 if (head tail) cout cur ; else cout cur; count 0; // 重新报数 } else { // 没被淘汰重新放回队尾 q[tail] cur; } } return 0; }这段代码的核心逻辑是head指向队头tail指向队尾的下一个空位。每次循环取出q[head]然后head加1逻辑上相当于出队。如果这个数字没被淘汰就写进q[tail]的位置然后tail加1逻辑上相当于入队。整个过程中数组下标会不断往后走但因为我们同时利用队尾空间存放“还活着的人”所以队列中的人数始终等于tail - head。你可能会问数组容量为什么开205因为最多同时有n个人在队列里每次弹出一个人如果没被淘汰又会塞回队尾所以队列的长度始终不会超过n。但在头尾指针不断后移的过程中数组总的使用空间会超过n最坏情况下队尾指针会一直往前推进。不过这道题n只有100开205完全足够。如果n很大就需要用循环队列让tail在超出数组长度时绕回头部这也是一个很好的进阶练习。2.3 队列版本的复杂度分析与运行效果队列模拟的时间复杂度是O(n*m)每淘汰一个人中间要经历m次“取出-判断-放回”操作总共淘汰n个人所以总操作次数是n乘以m。在n和m都不超过100的情况下这个复杂度毫无压力运行时间几毫秒就能跑完。空间复杂度是O(n)因为我们只需要维护一个长度不超过n的队列。这个复杂度表现对入门题来说完全够用而且代码量是所有解法里最少的逻辑也最容易验证。我实测的时候整个程序从提交到AC不到一秒钟裁判系统给出的反馈是Accepted。不过我要提醒一句队列模拟虽然简单但如果你直接把queue的STL版本交上去也要注意clear操作。STL的queue没有clear方法你需要重新定义一个队列对象来清空或者用while (!q.empty()) q.pop(); 来弹出所有元素。新手容易在“多组测试数据”的题目里忘记清空队列导致上一组数据残留好在本题目是单组输入没这个坑。还有一个小细节当count m时我把count重置为0。很多人的做法是写if (cnt m)这也可以但重置的位置一定要在对的分支里否则会影响下一轮报数的起点。报数起点是从被淘汰者的下一个重新开始队列法里这个“下一个”恰好就在队头这是队列法最优雅的一点。3. 链表解法从“报数淘汰”到“节点删除”的思维切换3.1 单向循环链表的建模思路队列模拟虽然好写但它有一个“缺陷”它其实是在用数组模拟一种逻辑上的环形结构而不是真正在内存里构建一个环。如果你想更本质地理解“围成一圈”这件事就应该试试循环链表。循环链表的核心思想是把n个人看成n个节点每个节点有一个next指针指向下一个人最后一个节点指向第一个节点这样就形成了一个环。报数时我们沿着next指针走m步走到的那个节点就是要删除的删除操作只需要让它的前驱节点直接指向它的后继节点即可。从“队列的出队入队”切换到“链路中删除节点”是一次很重要的思维升级队列法里每个存活的人会被反复“弹出再塞回”本质上是用移动来模拟报数的循环链表法里节点本身不动移动的是指针删除是真正的指针摘除省去了大量重复的“搬运”动作。下面是用单向循环链表实现的版本。这里我选择用数组模拟链表节点而不是动态new这样代码更短也避免动态内存管理的麻烦#include iostream using namespace std; const int MAXN 105; int nxt[MAXN]; // 每个节点的后继 int main() { int n, m; cin n m; // 建环i 的后继是 i1n 的后继是 1 for (int i 1; i n; i) nxt[i] i 1; nxt[n] 1; int cur n; // 让cur指向1号节点的前驱即n号节点 int first 1; for (int i 0; i n; i) { // 从cur的下一个节点开始报数数到第m-1个节点时 // 它的下一个节点就是第m个节点 for (int j 1; j m; j) { cur nxt[cur]; } // cur的下一个节点就是要删除的节点 int out nxt[cur]; if (i n - 1) cout out ; else cout out; // 删除out节点让cur直接指向out的下一个节点 nxt[cur] nxt[out]; } return 0; }3.2 链表删除的临界情况只剩一个节点时怎么办链表解法里最需要小心的就是边界情况。第一个问题是初始时cur应该指向哪里在本实现中我让cur n即1号节点的前驱。这样做的目的是让“报数”过程统一成“从cur的下一个开始走m-1步”避免对“第一个被删除的人恰好是1号”做特殊处理。第二个问题是当m等于1时怎么办如果m1内层循环j从1到0一次都不执行cur保持初始值然后out nxt[cur]即1号节点输出并删除。这正好符合“第一个人直接报1就出圈”的规则。很多人在m1这种边界上写错就是因为让cur从1号开始而不是从n号开始。第三个问题只剩最后一个节点时还要不要删除循环里我们直接输出了最后一个节点nxt[cur] nxt[out]这一步让cur指向了自己虽然之后循环已经结束但这种“自环”状态其实无伤大雅。如果你把这个实现改成“输出所有出圈者直到链表为空”的while循环版本就需要额外判断cur-next cur这种自环情况。3.3 链表的实际考场价值与缺点链表解法在本题的数据范围下并不是必须的它的价值在于学习和理解。我建议每个学完队列解法的人都顺手把链表版本写一遍特别是像我这样用数组模拟指针的写法避免被动态内存的细节干扰。不过我要泼一盆冷水如果是在真实竞赛的有限时间内我通常不会首选链表解法。原因有三个第一链表代码量比队列大出现野指针、数组越界的概率更高第二单向链表删除一个节点需要知道它的前驱代码里要额外维护cur和out两个指针初学者容易搞混第三当n很大时链表解法和队列解法一样是O(n*m)并没有性能优势。链表真正的优势场景是“频繁删除元素但不需要随机访问”的问题而约瑟夫问题恰恰符合这个场景只是本题数据太小优势体现不出来。我也看到过一些人的链表实现里混用了“计数值为m”和“指针走m步”两种理解方式结果导致删错了人。这里给一个实用口诀如果cur指向的是“当前报数的人”那么报数开始时cur就是第一个报数的人数到第m个意味着next要走m-1步如果cur指向的是“报数起点的前驱”那么next要走m步才能到第m个。两种模型都能工作但别混着用。4. 递推公式O(n)解法背后的数学推导4.1 从最后一个幸存者反推f(1)0的起点这道题在洛谷上的定位是入门模拟题但约瑟夫问题本身有一个非常漂亮的数学结论值得单独拿出来讲。如果你只需要知道最后一个幸存者是谁而不要求输出完整的出圈顺序那么存在一个O(n)的递推公式。先约定一种编号方式把n个人从0到n-1编号这样计算更方便。定义f(n, m)为长度为n的环每次数m个人淘汰一个最后幸存者的编号。我们想建立f(n, m)和f(n-1, m)之间的关系。第一轮报数时数到m的那个人被淘汰。由于编号从0开始被淘汰的人编号是(m - 1) % n。他出圈之后剩下n-1个人下一次报数从被淘汰者的下一个位置开始也就是从编号为m % n的人开始。此时剩下的n-1个人其实是“一个新的环”如果把这n-1个人重新编号为0到n-2那么原来幸存者的编号就变成了f(n-1, m)。关键问题是怎么把“新编号”转回“旧编号”答案很直接旧编号 (新编号 m) % n。于是我们得到递推式f(n, m) (f(n-1, m) m) % n边界条件是f(1, m) 0因为只有一个人时幸存者显然是他自己编号0。4.2 递推式的直觉解释与代码落地这个递推式看起来很简洁但第一次接触的人往往觉得抽象。我用一个具体例子说清楚假设n5m3。第一轮数到3的人被淘汰也就是编号2。剩下的编号是3、4、0、1。下一轮从编号3开始报数。如果我把这一轮看成“3是新0号、4是新1号、0是新2号、1是新3号”那么新环的幸存者会是某个“新编号”。这个新编号在旧环里的真实编号就等于新编号加3m的值之后对5取模。代码实现极其简单#include iostream using namespace std; int main() { int n, m; cin n m; int survivor 0; // f(1, m) 0 for (int i 2; i n; i) { survivor (survivor m) % i; } cout survivor 1 endl; // 转换回从1开始的编号 return 0; }这里有个细节需要强调递推式中每一步模的数值是i而不是n。因为在递推的过程中环的长度从1逐渐增大到n每一步的“模数”都在变化。我用第2章提到的队列模拟来验证当n5、m3时最后的幸存者是4号从1开始编号用这个递推式算出来的survivor是3从0开始编号加1后正好是4完全一致。4.3 三种解法复杂度对比三种解法的对比我用一张表总结解法时间复杂度空间复杂度能否输出完整出圈顺序代码难度适用场景队列/数组模拟O(n*m)O(n)可以最低本题及类似小数据模拟循环链表O(n*m)O(n)可以中等学习链表操作、理解删除流程递推公式O(n)O(1)不能直接输出全部顺序低只需最后幸存者编号看到这张表你应该明白为什么我建议三种都写一遍递推公式只回答了“谁活着”但P1996要求的是“按出圈顺序输出所有人”所以单纯用递推公式做不出完整答案。但如果你把递推公式和线段树、树状数组结合起来就能在O(n log n)时间内输出整个出圈序列这是另一层进阶内容了。这里也是很多人的误区以为掌握了递推公式就能通吃所有约瑟夫题。实际上P1996这种要求完整序列的题最稳妥的还是模拟而某些变种题比如只问最后幸存者、且n高达10^9才必须走数学路线。我后面还见过一个OJ上的约瑟夫变种问的是第k个出圈的人是谁这时候单靠基础递推就不够用了需要用到倍增或更深入的分治思想那就是后话了。5. 聊聊输出格式这个坑行末空格、性能开关与常见罚时5.1 行末空格导致的Presentation Error我第一次在洛谷交这道题用的是printf逐个输出最后多打了一个空格结果裁判返回的不是Wrong Answer而是Presentation Error也就是输出格式错误。PE在部分OJ上不会计罚时但会提示“你的程序没有输出正确格式”。如果你在真实比赛里遇到PE通常意味着你的逻辑没问题但输出和题目要求存在细微差异系统无法接受。具体到P1996描述里明确说“输出n个正整数两数之间有空格”。这个表述意味着最后一个数字后面不能有空格。很多人在循环里写cout num 只在最后一个数字后才意识到多了空格于是改用if判断。在循环输出时更优雅的写法是for (int i 0; i n; i) { if (i 0) cout ; cout out[i]; }这样除了第一个数字每个数字前面都输出一个空格最后自然没有行末空格。这个技巧在几乎所有要求“行内空格分隔”的OJ题里都通用我后面写任何输出数组的题默认都用这个模式避免PE。5.2 cin/cout性能问题与ios::sync_with_stdio(false)再说一个初学阶段容易忽略的点。这道题只有两个输入和最多100个输出cin/cout的性能完全够用不需要刻意优化。但很多人在洛谷刷题时养成了一种习惯所有题都加上这两行因为当数据量到了10万甚至百万级别时cin/cout默认的同步模式会让输入输出慢好几倍。这两行代码是#include iostream using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); // ... }第一行关闭C标准流和C标准IO的同步第二行解除cin和cout的绑定。加了这两行之后cin/cout的速度可以逼近scanf/printf但代价是你不能混用cin和scanf、cout和printf否则输出顺序可能错乱。对于初学者我的建议是不管题目的数据量大小只要用cin/cout就在main开头写上这两行养成习惯但也永远不要混用两套IO。顺便说一句如果你是C语言选手直接用printf和scanf写这道题也完全没问题。洛谷对C和C都支持选自己顺手的语言即可。我自己平时写题偏好C主要是STL里的queue和vector用起来方便。5.3 输出顺序与“空格错位”的延伸场景有时候你以为自己处理了空格实际上还是错位了原因在于你输出的不是“出圈顺序”而是别的顺序。我见过一个同学用递推公式求出了最后幸存者然后从幸存者开始倒推之前出圈的人结果推出来的顺序和自己预期的方向相反在输出格式上纠结了很久。其实递推公式更适合求“幸存者编号”这种单点答案真要还原完整出圈顺序模拟更直接。输出相关的另一个点是题目要求每个数之间用空格但没说末尾能不能换行。实际上大多数OJ对行末换行符不做严格限制你输出一个换行或者不输出一般都能AC。个别卡得严格的题会在描述里写“行末无空格文末有换行”按字面理解即可。还要注意P1996是多组输入吗我记得不是题目只给了一组n和m。如果你按多组数据去写while (cin n m)碰巧输入只有一个case也能正常通过但如果原题确实是多组数据而你只读一组就会WA。这种“题目描述里没写清多组输入”的情况在OJ里比较常见我拿到题第一件事就是看输入格式部分有没有“共一行”或“输入包含多组测试数据”之类的字眼。6. 实测记录与常见错误汇总给新手的一份避坑清单6.1 我在本地和OJ上的实测结果我在本地用n5、m3做了测试队列解法的输出是3 1 5 2 4链表解法输出也一样。再用n10、m2测试输出序列是2 4 6 8 10 3 7 1 9 5这个结果符合约瑟夫问题的经典序列可以手工验证前几个数2淘汰2号然后从3开始再数2淘汰4号然后从5开始数2淘汰6号和输出完全一致。提交到OJ后队列版本一次AC用时大概是0毫秒或1毫秒内存占用也不大。链表版本同样AC。递推公式版本如果只输出最后的幸存者用n5、m3得到4同样正确。在实测中我特别注意了一个有趣的现象当m远大于n时比如n7、m20队列法里报数的人要转好几圈才被淘汰程序依然不用改因为count会一直累加到20才触发删除。链表法也一样cur沿着next指针走20步会在环里绕好几圈。这种“m比n大”的情况是边界测试的常见套路很多新手只测了mn的普通case导致代码在m20这种数据上出错。6.2 几个高频报错场景的完整排查链路我梳理了三个新手最容易碰到的报错场景每个都可以独立复现。第一个场景是数组模拟队列时数组开小了。我一开始把数组开成int q[100]然后tail和head一直往后走虽然队列逻辑长度不超过n但数组整体使用长度会超过100导致越界写入程序运行到中途崩溃或输出乱码。排查方法很简单把数组容量开到2*n5比如n≤100就开到205。这也是为什么我在第2章的代码里直接写了205。第二个场景是链表法里“报数步数”算错。我在第3章里强调过cur指向n号节点时内层循环要走m-1步而不是m步。有读者朋友把他的代码发给我看写的是for (int j 0; j m; j) cur nxt[cur]; 结果每轮都多走一步删除的是第m1个节点。这个问题的排查思路是把m1代入看看程序是否在第一个循环就删掉1号如果没有基本就是步数模型搞反了。第三个场景是输出格式。我在第5章已经讲过行末空格的问题这里再补充一个变体有人用队列法把所有出圈数字先存进数组最后统一输出。这本来没问题但他在存数组时用了“每次淘汰后输出到vector”结果vector里的顺序和出圈顺序一致却在输出循环里误用了逆序导致一改就错。排查时把n设为3、m设为2手算出圈序列应该是2 1 3如果代码输出的是3 1 2那就是逆序问题了。6.3 这道题做完之后下一步还能怎么练P1996是一个非常好的起点但做完它不代表你就完全掌握了约瑟夫问题家族。我把后续值得练习的方向列一下供不同目标的人参考如果你是在准备竞赛建议把目光放在约瑟夫问题的三种扩展上一是“只想输出最后一个幸存者且n可达10^9”这需要用到m2时的特殊性质或更高级的数学推导二是“要求输出第k个出圈者的编号”这需要把递推公式推广三是“每次报数的步长m会变化”这会让问题变成动态模拟需要结合数据结构维护。如果你只是想把数据结构和基础算法打牢我更推荐你实现在第2章提到的循环队列以及在第3章提到的自环判断。这两个小目标能帮你把“数组模拟结构”的功底打扎实。之后再去试试洛谷上其他标记为“入门”和“普及-”的模拟题你会发现很多题本质上都是“用代码描述过程”和约瑟夫问题一脉相承。判断自己是否真正掌握一道题我有一个很实用的标准能不能在30秒内向别人讲清楚你的思路并且在完全不看代码的情况下手写出完整的核心逻辑。P1996这道题如果你能做到“讲清楚队列模拟为什么不需要判断存活、链表法为什么初始cur要指n号、递推公式为什么模数是i而不是n”那就真的过关了。最后分享一个我个人的小习惯做这类过程模拟题时我会先在草稿纸上手算一遍小数据比如n6、m4把出圈序列写出来再对照代码的结果。手算和代码结果一致我才会提交OJ。别小看这个习惯它帮我省掉了无数次因边界情况导致的WA。