东华OJ基础题第41题题面简单到只有一个字环。我第一次从题目列表点进去看到标题就愣住了没有背景故事没有输入样例说明根本不知道它想让我干什么。把完整题面翻出来之后才明白这题就是经典的约瑟夫环n个人围成一个圈从第1个人开始报数报到m的人出列问最后留在圈里的人是谁。作为一个靠C入门数据结构不久的人这道题几乎把循环结构、删除操作和边界处理考了个遍非常适合用来练手。如果你也在刷东华OJ基础题卡在这里这篇就是我给你复盘的全过程。1. 先把题面翻译成人话这题到底在问什么1.1 为什么标题只写了一个“环”字东华OJ的基础题命名一直很“极简”第41题就叫“环”。我猜最早挂题的人觉得这个名词是常识不需要解释。但OJ多了之后你会发现叫“环”的题有好几种可能最常见的是约瑟夫环也有的平台会用“环”来指“素数环”——就是让你把1到n排成一个首尾相接的排列要求任意相邻两个数之和为素数。这两个完全不是一个考法。我开始也犹豫了一下后来根据题面和基础题的定位判断东华OJ这一题应该就是约瑟夫环。理由有三一是约瑟夫环是数据结构教材里的标配内容和“基础题”这个定位匹配二是约瑟夫环的题面通常很短很适合用“环”一个字概括三是从提交情况来看用数组模拟和链表模拟的人都有典型的约瑟夫环解法生态。所以下面主要按约瑟夫环讲最后我也会单独说一句“如果题面其实是素数环该怎么办”避免你走错方向。1.2 用一个手算例子理解规则怎么判断自己理解的规则对不对拿n5、m3这种小数据手算一遍就行。5个人编号分别是1、2、3、4、5从1开始报数报到3的人出列第1轮1报12报23报3所以3出列第2轮从4接着报15报21报3所以1出列第3轮从2接着报14报25报3所以5出列第4轮从2接着报14报22报3所以2出列最后剩下4。所以n5、m3的答案应该是4。这个手算结果非常重要你后面不管用数组、链表还是递推公式都先拿它验证一遍代码能少走很多弯路。如果题目要求你输出完整出列顺序那就是3 1 5 2最后补一个4。这里还有一个容易理解错的点报完m的人出列后是“下一个人”继续报1不是出列者本人。很多人第一次写错就是因为把出列后的下一次报到起点搞错了。2. 三种解法的思维链路和选型理由2.1 数组模拟最直观但要注意“跳过死人”数组模拟的思路是开一个数组标记每个人还在不在圈里然后从1号开始数数到第m个还活着的人就标记成出列。整个过程不真的删除数组元素只是用标记绕过已出列的人。这种写法的时间复杂度是O(n*m)因为每出列一个人就要从当前位置往后扫m个活人。n1000、m100这种数据完全没压力但如果n到了10^5、m也很大这题就危险了。不过作为基础题数组模拟通常能过而且它最大的好处是逻辑清楚适合先用来验证规则。我建议第一次写的时候就用数组模拟哪怕最后提交时换成递推模拟版也能帮你排查思路。调试时输出每一次出列的人名和手算结果对一下基本就能确认自己没理解偏。2.2 循环链表数据结构教材的标准答案如果把“环”字按数据结构直译那循环链表就是最贴切的做法。每个节点代表一个人节点的next指针指向下一个人最后一个节点的next指回头节点形成一个真正的圆环。报数就移动指针出列就删除节点。链表模拟的时间复杂度同样是O(n*m)但它比数组模拟多练了两个基本功结构体定义、动态内存管理。很多人学C链表时只会跟着课本抄到OJ上不敢自己写这道题就是逼你亲手写一次完整的循环链表。需要注意的是链表删除时的指针顺序先让前一个节点指向当前节点的next再释放当前节点否则链会断。这种细节写代码时特别容易出问题。2.3 递推公式一行for循环解决大范围n如果你只想求最后一个幸存者的编号根本不用模拟整个过程。约瑟夫环存在一个经典递推公式f[1] 0 f[i] (f[i-1] m) % i最终答案就是f[n] 1。这个公式的时间复杂度是O(n)空间复杂度是O(1)。当n放到10^7甚至10^8级别时只有这个方法扛得住。很多人第一次看到这个公式会觉得像魔法不理解为什么从1开始倒推。第5章我会把推导过程完整写一遍这里你只需要记住一句话递推只适合求最后一个人不适合求完整出列顺序。题目只要问“最后是谁”递推就是首选。三种解法放一起对比选型逻辑很清楚解法核心操作时间复杂度空间复杂度适合场景数组标记模拟循环遍历跳过标记O(n*m)O(n)小数据、教学演示、理清思路循环链表节点删除O(n*m)O(n)练习指针、要求输出出列序列线性递推一次for循环O(n)O(1)大n、只求最后幸存者3. 数组模拟不删元素只做标记3.1 标记数组与循环下标的处理数组模拟有个关键决定用什么数据结构当标记数组。我推荐用vector 不用vector 。原因不复杂vector 被做过位压缩在某些编译器上行为和其他vector不太一样初学者容易踩坑。虽然这道题里只是简单的赋值和判断问题不大但从习惯上讲用vector 更稳妥。另一个关键点是循环下标。因为编号是1到n我习惯让下标也在1到n之间循环用cur cur % n 1这个表达式。当cur等于n时n % n等于0加1变回1其他时候就是简单加1。这个写法比if判断干净也符合“环形”的直觉。报数逻辑我这样实现用变量cnt表示还需要数多少人初始为m每经过一个活人就cnt减1当cnt变成0时当前cur就是要出列的人。这里有个很容易写错的地方只有cnt大于0时才移动cur如果cnt已经减到0还移动指针就会把cur指到下一个人导致输出的答案整体错位。3.2 数组模拟的完整代码下面这段代码只输出最后幸存者适用于大多数基础OJ题#include iostream #include vector int main() { int n, m; while (std::cin n m) { std::vectorchar alive(n 1, 1); int remain n; int cur 1; while (remain 1) { int cnt m; while (cnt 0) { if (alive[cur]) { --cnt; } if (cnt 0) { cur cur % n 1; } } alive[cur] 0; --remain; cur cur % n 1; } std::cout cur \n; } return 0; }如果你的题面要求输出连续出列顺序就把循环改为while (remain 0)每出列一个人就输出一次最后一个人单独处理换行。注意输出格式OJ对行末空格很敏感最好别在最后一个数字后面留空格。我一般这样写if (remain 1) { std::cout cur ; } else { std::cout cur \n; }数组模拟的边界情况很好处理n1时while循环不执行直接输出1m1时每轮连续删除下一个人逻辑也正确。我建议你提交前专门测一下n1、m1、n5、m3这三组数据基本能覆盖所有边界。4. 循环链表把圆环直接画在结构体里4.1 单循环链表的构建数组模拟是用数学下标模拟圆环链表则是把圆环画成真正的结构。每个节点存一个编号和一个指向下一个节点的指针最后一个节点的next指回头节点这就成一个环。构建链表时我习惯先创建编号1的节点作为头节点然后依次往后挂新节点。这里有一个新手容易忽略的细节如果直接写Node* head new Node{1, nullptr}; Node* tail head;后面挂完所有节点后必须把tail-next重新指向head否则这只是普通单链表不是循环链表。完整构建代码struct Node { int id; Node* next; }; Node* head new Node{1, nullptr}; Node* tail head; for (int i 2; i n; i) { tail-next new Node{i, nullptr}; tail tail-next; } tail-next head;4.2 报数与删除时的指针绕圈链表版的核心循环是当前节点从1开始报数要报到m只需要让指针移动m-1次。为什么是m-1因为当前节点自己已经算报了1次再往前走m-1个人正好落到第m个人身上。删除节点时需要同时维护两个指针一个指向当前节点p一个指向p的前一个节点prev。删除时的顺序必须是先让prev-next指向p-next再释放p。如果先把p释放了再去改prev-next就访问了悬空指针程序会崩。还有一个细节当链表中只剩一个节点时它的next指向它自己。如果你在删除循环里对单节点的情况继续执行p p-next就会永远在同一个节点上绕圈。所以最后的输出放在循环外循环条件是remain 1。4.3 链表版完整代码#include iostream struct Node { int id; Node* next; }; int main() { int n, m; while (std::cin n m) { Node* head new Node{1, nullptr}; Node* tail head; for (int i 2; i n; i) { tail-next new Node{i, nullptr}; tail tail-next; } tail-next head; Node* p head; Node* prev tail; int remain n; while (remain 1) { for (int i 1; i m; i) { prev p; p p-next; } prev-next p-next; Node* tmp p; p p-next; delete tmp; --remain; } std::cout p-id \n; delete p; } return 0; }这段代码我在本地跑过n5、m3输出4和手算一致。链表版最大的价值在于让你把new和delete配对使用养成内存管理意识。OJ上不检查内存泄漏但以后写工程代码不能这么随意。5. 递推公式法从匪夷所思到一行for循环5.1 倒推编号的直觉假设编号从0开始这样取模运算更自然。n个人的约瑟夫环第一轮会删掉从0开始数的第m个人也就是编号为m - 1的人。删掉之后从m这个人开始剩下的人被重新编号成0、1、2、...、n-2。现在问题变成如果我知道了n-1个人的约瑟夫环最后幸存者的新编号f[n-1]能不能把它映射回原来的编号f[n]可以。下次开始报数的那个人也就是原来编号为m的人在新环里编号是0。所以新编号k对应的原编号是(k m) % n。也就是说原编号f[n]和新编号f[n-1]的关系是f[n] (f[n-1] m) % n边界条件只剩1个人时它在0号位置所以f[1] 0。5.2 为什么取模运算符在这里刚刚好取模运算解决了一个绕不开的问题报数是循环的但编号有限。当f[n-1] m超过n时取模会把它拉回0到n-1的范围本质上就是在圆周上走了一圈回到起点。理解了这个推导后你去看网上那句f[i] (f[i-1] m) % i就会觉得顺理成章。这里的i不是总人数n而是当前人数从2人一直推到n人。每次取模的模数都在变这也是为什么不能用某个固定的常量提前取模。5.3 递推版完整代码#include iostream int main() { int n, m; while (std::cin n m) { long long f 0; for (int i 2; i n; i) { f (f m) % i; } std::cout f 1 \n; } return 0; }代码只有几行但信息量很大。注意我用的是long long因为f和m相加可能超过int范围。虽然基础题一般给不到那么大的数但养成这个习惯没坏处。递推法只能求最后幸存者不能输出完整出列顺序。如果你仔细读了题面发现它要求输出“依次出列的所有人编号”那就老老实实回去用数组或链表模拟别在递推上死磕。6. 提交东华OJ前必须检查的几个点6.1 多组输入与输入终止条件OJ题目经常写“多组测试数据直到文件末尾”或者“输入包含多组数据以0 0结束”。第一种情况直接用while (std::cin n m)读到文件末尾自然结束第二种情况要先判断n和m是不是同时为0是的话break否则继续算。很多新手第一次WA不是算法错了而是输入只处理了一组。尤其是本地测试只跑一组数据看着没问题一提交就全错多半就是没处理多组输入。6.2 不同解法的选型取决于输出要求我在刷这道题时犯过一个错误拿到题先写了递推公式结果发现题目要求输出的是完整出列序列而不是最后一个幸存者。递推那套瞬间报废只好换成链表重写。所以选题解法前第一件事是看输出要求只问最后一个人数组模拟、链表、递推都行递推最稳要求输出所有人出列顺序只能用数组模拟或链表别用递推n特别大且只问最后一个人首选递推。如果你不确定题面到底问什么就多读两遍样例。样例输出如果是单个数字基本就是求幸存者如果是一串数字大概率是出列顺序。6.3 边界条件和输出格式的坑我整理一下自己踩过的坑全是血泪n1时很多人忘了考虑。数组模拟时while循环不进来链表时head和tail指向同一个节点递推时for循环不执行直接输出f11。三个解法其实都能正确处理前提是你别在循环里写死访问第二个节点这类逻辑。m1时出列顺序就是1、2、3、...、n。数组模拟里每个cnt循环只有一次判断逻辑没问题链表里for循环不执行直接删当前节点。这个边界能帮你快速验证代码是否正确。输出最后一个数字时不要带多余空格。我提交时遇到过“Presentation Error”就是行末多了一个空格OJ认为格式不对。后来统一用if (remain 1) cout cur \n; else cout cur ;解决。别在主函数里写死return 0放在循环内。多组输入时只要有一组数据处理完就return后面的数据全被跳过OJ直接WA。如果你还想更进一步提升可以试试用std::list或std::vector配合迭代器模拟删除这是STL的进阶玩法能省去手写链表的麻烦。但基础题阶段我建议还是先把手写链表练熟了理解指针怎么绕圈再偷懒不迟。7. 如果题面其实是“素数环”换汤不换药的DFS突破口7.1 竞赛圈里常说的“环”还有另一个意思万一你手里那道“环”的题面写的是“把1到n排成一个环相邻两个数相加为素数”那它考的不是约瑟夫环而是素数环。这类题在东华OJ基础题里也有名字也经常直接叫“环”容易和约瑟夫环混淆。素数环的考点从“循环删除”变成了“排列搜索”。n一般不超过20因为1到n的全排列数量是n!直接暴力枚举会爆炸。必须用深度优先搜索加剪枝也就是回溯。解决思路固定1在环首然后从位置2开始逐位搜索每一位都尝试一个没用过的数字并且检查它和上一位数字的和是否为素数。搜到最后一个位置后还要检查和1的和是否为素数因为环首尾相接。这样既保证不重复又利用搜索天然按字典序枚举的特性。7.2 素数环的关键剪枝与代码骨架素数环有个非常关键的判定当n是大于1的奇数时无解。因为除2以外所有素数都是奇数相邻两个数之和要为奇数必须一个奇数一个偶数交替排列在奇数个数首尾相接的环里无法完成交替矛盾直接排除。这个剪枝能让程序省掉大量无效搜索。另一个常规优化是预处理素数表。最大相邻和不超过2n可以先做一次素数判断把0到2n范围的素数存进数组。搜索时就查表不需要反复调用判断函数。这也是热词里“判断质数c优化”在这类题里的直接应用。DFS骨架如下#include iostream #include vector std::vectorint ans; std::vectorchar used; std::vectorchar prime; int n; void dfs(int pos) { if (pos n 1) { if (prime[ans[n] ans[1]]) { for (int i 1; i n; i) { std::cout ans[i] (i n ? \n : ); } } return; } for (int i 2; i n; i) { if (!used[i] prime[ans[pos - 1] i]) { used[i] 1; ans[pos] i; dfs(pos 1); used[i] 0; } } } int main() { std::cin n; prime.assign(2 * n 1, 0); // 先用筛法填充prime数组 ans.assign(n 1, 0); used.assign(n 1, 0); ans[1] 1; used[1] 1; if (n % 2 1 n 1) { // 直接输出无解 } else { dfs(2); } return 0; }注意DFS每找到一个解就输出如果题目要求输出全部解这个写法天然会搜完所有排列如果只要一个解可以加一个计数器找到第一个解后直接退出程序或返回状态。递交前务必确认题面到底要1个还是全部。我自己的体会是刷这种题名特别短的题目最忌讳上来就写代码。先把“环”到底是约瑟夫环还是素数环确认清楚再决定用模拟还是搜索。也就是一页纸的功夫却能避免白写几百行代码。如果你也是刚开始刷OJ的C新手我建议把数组模拟、循环链表、递推公式这三个解法都各写一遍不为别的就是为了把循环下标、指针删除、取模递推这几个基本功扎扎实实练到位。后面不管遇到什么样的“环”你都能一眼看出它是哪个套路。