企业官网建设流程全解析

东华OJ基础题第41题，题面简单到只有一个字：环。我第一次从题目列表点进去，看到标题就愣住了，没有背景故事，没有输入样例说明，根本不知道它想让我干什么。把完整题面翻出来之后才明白，这题就是经典的约瑟夫环：n个人围成一个圈，从第1个人开始报数，报到m的人出列，问最后留在圈里的人是谁。作为一个靠C++入门数据结构不久的人，这道题几乎把循环结构、删除操作和边界处理考了个遍，非常适合用来练手。如果你也在刷东华OJ基础题卡在这里，这篇就是我给你复盘的全过程。

1. 先把题面翻译成人话：这题到底在问什么

1.1 为什么标题只写了一个“环”字

东华OJ的基础题命名一直很“极简”，第41题就叫“环”。我猜最早挂题的人觉得这个名词是常识，不需要解释。但OJ多了之后你会发现，叫“环”的题有好几种可能，最常见的是约瑟夫环，也有的平台会用“环”来指“素数环”——就是让你把1到n排成一个首尾相接的排列，要求任意相邻两个数之和为素数。这两个完全不是一个考法。

我开始也犹豫了一下，后来根据题面和基础题的定位判断，东华OJ这一题应该就是约瑟夫环。理由有三：一是约瑟夫环是数据结构教材里的标配内容，和“基础题”这个定位匹配；二是约瑟夫环的题面通常很短，很适合用“环”一个字概括；三是从提交情况来看，用数组模拟和链表模拟的人都有，典型的约瑟夫环解法生态。所以下面主要按约瑟夫环讲，最后我也会单独说一句“如果题面其实是素数环该怎么办”，避免你走错方向。

1.2 用一个手算例子理解规则

怎么判断自己理解的规则对不对？拿n=5、m=3这种小数据手算一遍就行。

5个人，编号分别是1、2、3、4、5，从1开始报数，报到3的人出列：

• 第1轮：1报1，2报2，3报3，所以3出列；
• 第2轮：从4接着报1，5报2，1报3，所以1出列；
• 第3轮：从2接着报1，4报2，5报3，所以5出列；
• 第4轮：从2接着报1，4报2，2报3，所以2出列；
• 最后剩下4。

所以n=5、m=3的答案应该是4。这个手算结果非常重要，你后面不管用数组、链表还是递推公式，都先拿它验证一遍代码，能少走很多弯路。如果题目要求你输出完整出列顺序，那就是3 1 5 2，最后补一个4。

这里还有一个容易理解错的点：报完m的人出列后，是“下一个人”继续报1，不是出列者本人。很多人第一次写错，就是因为把出列后的下一次报到起点搞错了。

2. 三种解法的思维链路和选型理由

2.1 数组模拟：最直观但要注意“跳过死人”

数组模拟的思路是：开一个数组标记每个人还在不在圈里，然后从1号开始数，数到第m个还活着的人就标记成出列。整个过程不真的删除数组元素，只是用标记绕过已出列的人。

这种写法的时间复杂度是O(n*m)，因为每出列一个人，就要从当前位置往后扫m个活人。n=1000、m=100这种数据完全没压力；但如果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章我会把推导过程完整写一遍，这里你只需要记住一句话：递推只适合求最后一个人，不适合求完整出列顺序。题目只要问“最后是谁”，递推就是首选。

三种解法放一起对比，选型逻辑很清楚：

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::vector<char> 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'; }

数组模拟的边界情况很好处理：n=1时，while循环不执行，直接输出1；m=1时，每轮连续删除下一个人，逻辑也正确。我建议你提交前专门测一下n=1、m=1、n=5、m=3这三组数据，基本能覆盖所有边界。

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; }

这段代码我在本地跑过n=5、m=3，输出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 边界条件和输出格式的坑

我整理一下自己踩过的坑，全是血泪：

• n=1时，很多人忘了考虑。数组模拟时while循环不进来，链表时head和tail指向同一个节点，递推时for循环不执行，直接输出f+1=1。三个解法其实都能正确处理，前提是你别在循环里写死访问第二个节点这类逻辑。
• m=1时，出列顺序就是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::vector<int> ans; std::vector<char> used; std::vector<char> 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++新手，我建议把数组模拟、循环链表、递推公式这三个解法都各写一遍，不为别的，就是为了把循环下标、指针删除、取模递推这几个基本功扎扎实实练到位。后面不管遇到什么样的“环”，你都能一眼看出它是哪个套路。