CSP-J 入门级 · CSP 2021 入门级第一轮 第 19 题

三、完善程序（单选题，每小题 3 分，共计 30 分）

（1）（Josephus 问题） 有 $n$ 个人围成一个圈，依次标号 $0$ 至 $n - 1$。从 $0$ 号开始，依次 $0 , 1 , 0 , 1 , \dots$ 交替报数，报到 $1$ 的人会离开，直至圈中只剩下一个人。求最后剩下人的编号。

试补全模拟程序。

#include <iostream>
using namespace std;

const int MAXN = 1000000;
int F[MAXN];

int main() {
    int n;
    cin >> n;
    int i = 0, p = 0, c = 0;
    while (【①】) {
        if (F[i] == 0) {
            if (【②】) {
                F[i] = 1;
                【③】;
            }
            【④】;
        }
        【⑤】;
    }
    int ans = -1;
    for (i = 0; i < n; i++)
        if (F[i] == 0)
            ans = i;
    cout << ans << endl;
    return 0;
}

34. ①处应填（ ）

35. ②处应填（ ）

36. ③处应填（ ）

37. ④处应填（ ）

38. ⑤处应填（ ）

这题考模拟+约瑟夫问题变种。核心是维护‘当前报数p’和‘已出局数c’，循环直到只剩一人。填①时别盯着i，要盯c；填②③④时注意p=1才出局、出局后c++、p要翻转；填⑤别漏取模。

最容易栽跟头是①填成 i<n 或 i<n-1，把循环条件搞错，导致多跑一圈或少跑一圈；其次是②把 p 当成下标用，写成 i++ 或 i=(i+1)%n，结果报数逻辑全乱；还有③在 p=0 时误填 c++，或者④没写 p^=1 导致报数不交替；⑤漏写取模直接 i++ 会让数组越界。

这道题考查的是模拟能力，具体是约瑟夫问题（Josephus）的一个变种。原题约瑟夫是报数到 k 出局，这里简化为报数 0、1、0、1……交替，报到 1 的人出局。题目给了一个框架，让我们补全 5 个空，把模拟过程写对。命题人挖坑的点很典型：一是循环终止条件容易看错，二是报数状态 p 的维护，三是出局计数 c 的更新时机，四是下标 i 的循环移动（必须取模）。下面我带着大家把 5 个空一个个推过去，顺便把背后的逻辑讲透。先给个总览：变量 i 是当前下标，p 是当前报的数（0 或 1），c 是已经离开的人数，F[i]=0 表示还在圈里，F[i]=1 表示已离开。程序要一直跑，直到圈里只剩一个人，也就是 c = n-1 时停止。所以第一个空①就是循环条件。很多同学会下意识写 i < n，因为 i 从 0 到 n-1 遍历一圈，但这里 i 会在循环里不断移动，而且我们真正关心的是‘还有几个人在圈里’，而不是‘i 有没有越界’。圈里人数 = n - c，当 c = n-1 时只剩 1 人，条件应该是 c < n-1。选 A（i<n）或 C（i<n-1）都会导致循环多执行一次或少执行一次，最后 ans 会错。所以①填 D：c < n - 1。接下来看②：当 F[i]==0 说明这个人还在圈里，此时要判断他报的是 0 还是 1。p 就是当前报的数，p=1 时这个人出局。题目给的选项有 p、!p、i++ 等。如果填 p，条件就是 if (p)，等价于 if (p==1)，正好对应‘报到 1 的人离开’。填 !p 就反了，填 i++ 或 i=(i+1)%n 更是把下标当成报数，逻辑全乱。所以②填 C：p。然后③：一旦这个人出局，我们要把 F[i] 置为 1，并且把已出局人数 c 加 1。选项里有 c++、p^=1、i 的更新等。显然这里要的是 c++。填 p^=1 会改变报数，但还没到下一次循环，报数应该等下一个人时再变；填 i 的更新更不对，i 是下标，不能在这里动。所以③填 C：c++。再看④：不管这个人出局没，报数都要交替。如果刚才 p=1 出局了，下一次报数应该是 0；如果刚才 p=0 没出局，下一次报数应该是 1。所以要在每次循环结束时把 p 翻转。C 语言里异或赋值 p ^= 1 就是 0↔1 切换。选项 D 正好是 p ^=1。填 C（c++）就错了，因为 c 已经在③里加了；填 A/B 的 i 更新也不对，i 的更新应该在循环末尾统一做。所以④填 D：p ^=1。最后⑤：i 要指向下一个人，因为是围成一圈，所以要用取模：i = (i + 1) % n。选项 B 就是这个式子。填 A（i++）会越界，填 C/D 的 c++ 或 p^=1 更离谱。所以⑤填 B：i = (i + 1) % n。把五个空串起来，程序逻辑就是：只要 c < n-1，就检查当前人是否还在圈里；在圈里就判断报数 p 是否为 1，若是就标记出局并 c++；然后不管出不出局，p 都要翻转；最后 i 移到下一个位置（取模）。这样跑完循环，F 数组里只剩一个 0，后面的 for 循环就能正确找到 ans。避坑方面，我再强调三点：1）循环条件一定要看 c，别被 i 迷惑；2）p 的翻转必须在每次循环末尾，不能在 if 内部；3）i 的移动必须取模，否则数组越界。关于考频，‘模拟’这个大类在题库里已经考了 178 题，覆盖 12 个级别，从 2010 年一直延续到 2026 年，其中 2026 年猛增到 38 题，说明模拟类题目热度持续上升。细分到‘约瑟夫问题’，虽然官方标签里没单独统计，但这类围圈报数、交替出局、标记出局的题在 CSP 入门级和 GESP 里反复出现，2021 年这道题就是典型代表。趋势上看，命题人喜欢把经典约瑟夫做变种：报数规则从固定 k 改成交替 0/1，或者增加标记数组 F 来模拟‘已离开’状态，这样既考察循环控制，又考察状态维护。未来如果继续考，很可能还会出‘报数 0/1/2 循环’或‘每隔 m 个报数’的变种，核心还是模拟 + 取模 + 状态翻转。基于现有数据，我没法给出精确到个数的预测，但可以说：模拟类题目在 CSP 入门级和 GESP 六级/七级里占比很高，约瑟夫变种大概率还会以‘完善程序’或‘填空’形式出现，尤其是带标记数组和交替报数的组合。所以，拿到这类题，先别急着写代码，花 30 秒把变量含义和循环终止条件想清楚，再按顺序填空，基本就能避开所有坑。