CSP-J 入门级 · CSP 2019 入门级第一轮 第 17 题

2.

#include<cstdio>
using namespace std;
int n, m;
int a[100], b[100];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        a[i] = b[i] = 0;
    for (int i = 1; i <= m; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (a[x] < y && b[y] < x) {
            if (a[x] > 0)
                b[a[x]] = 0;
            if (b[y] > 0)
                a[b[y]] = 0;
            a[x] = y;
            b[y] = x;
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i] == 0)
            ++ans;
        if (b[i] == 0)
            ++ans;
    }
    printf("%d", ans);
    return 0;
}

假设输入的 $n$ 和 $m$ 都是正整数，$x$ 和 $y$ 都是在 $[1,n]$ 的范围内的整数，完成下面的判断题和单选题：

• 判断题

1. 当 $m>0$ 时，输出的值一定小于 $2n$。（） 2. 执行完第 $27$ 行的 ++ans 时，$\mathrm{ans}$ —定是偶数。（） 3. a[i] 和 b[i] 不可能同时大于 $0$。（） 4. 右程序执行到第 13 行时，$x$ 总是小于 $y$，那么第 $15$ 行不会被执行。（）

•选择题

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题核心是维护双向映射：a[x]=y 且 b[y]=x。每次读入 (x,y) 时，若新映射更优（a[x]<y 且 b[y]<x），就清除旧映射再写入。最后统计数组里 0 的个数就是答案。

最容易踩的坑是误以为 a[i] 和 b[i] 不能同时非零，其实只要 i 既是某个旧映射的 x 又是新映射的 y，两者都会大于 0。还有很多人以为 ans 一定是偶数，忽略了++ans 是在循环里逐次执行的，中间状态可能为奇数。另外，判断 x<y 时只看了 13 行，却忘了 15 行是清除旧映射的，跟 x 和 y 的大小毫无关系。

本题考查模拟与双向映射维护

概念定义 程序中维护两个数组 a 和 b：

• a[x] = y 表示从 x 指向 y 的映射；
• b[y] = x 表示从 y 回到 x 的反向映射。

两者互为镜像，保证数据一致。

核心算法流程 每次读入一对 (x, y) 时，程序先检查两个条件： 1. a[x] < y：说明 x 当前若有映射，其目标值比新的 y 小； 2. b[y] < x：说明 y 当前若有反向映射，其来源值比新的 x 小。 只有当这两个条件同时成立时，才认为新映射更优，需要更新。

若更新，则执行三步清理与写入：

• 若 a[x] 已有值，把旧目标对应的反向映射清零：b[a[x]] = 0；
• 若 b[y] 已有值，把旧来源对应的正向映射清零：a[b[y]] = 0；
• 最后写入新映射：a[x] = y，b[y] = x。

逐题推演

1. 判断题 1：当 m>0 时，输出一定小于 2n。 - 每次成功更新至少使一个 a 和一个 b 从 0 变非 0，即减少两个 0。总共最多有 2n 个位置，至少减少 2m 个（因为 m 次输入，哪怕全部失败也不会增加 0 的个数，但题目说 m>0 且输入合法，至少有一次成功更新，否则 a[x]<y 或 b[y]<x 必有一假，但无论如何，m 次输入最多减少 2m 个 0，最少减少 2 个）。因此剩余 0 的个数 ans ≤ 2n - 2，严格小于 2n。✅正确。

2. 判断题 2：执行完第 27 行的 ++ans 时，ans 一定是偶数。 - 第 27 行是在遍历 a 数组时，若 a[i]==0 则 ++ans；第 28 行同理遍历 b。这两次 ++ans 是分开执行的，中间可能穿插其他逻辑，但题目问的是“执行完第 27 行时”，即只统计了 a 中的 0 个数，这个数可以是奇数（例如 a 中有 3 个 0，ans=3）。只有把 a 和 b 都扫完，总数才是偶数。❌错误。

3. 判断题 3：a[i] 和 b[i] 不可能同时大于 0。 - 设某时刻已有 a[3]=5，即 3→5。现在读入 x=5, y=3，检查条件：a[5] 若为空或小于 3，且 b[3] 若为空或小于 5，则可能更新。更新后 a[5]=3，b[3]=5。此时 a[3]=5 和 b[3]=5 都大于 0，说明 i=3 时两者同时非零。❌错误。

4. 判断题 4：若执行到第 13 行时 x 总是小于 y，则第 15 行不会被执行。 - 第 15 行是 if (b[y] > 0) a[b[y]] = 0;，它的触发条件只与 b[y] 是否已有值有关，与 x 和 y 的大小无关。即使 x<y 恒成立，只要之前有映射让 b[y] 非零，第 15 行仍会执行。❌错误。

5. 选择题 5：m 个 x 两两不同，m 个 y 两两不同。 - 每次输入 (x,y) 时，a[x] 原本为空（因为 x 未出现过），b[y] 原本也为空（因为 y 未出现过）。条件 a[x]<y 和 b[y]<x 自动成立（空值视为 0，小于任何正整数）。于是每次都会成功更新，且不会覆盖旧映射（因为没有旧映射）。最终形成 m 个独立映射，a 和 b 各减少 m 个 0，剩余 2n - 2m 个 0。✅选 A。

6. 选择题 6：m 个 x 两两不同，m 个 y 都相等（设为 Y）。 - 第一次输入 (x1, Y)：a[x1] 空，b[Y] 空，条件成立，写入 a[x1]=Y, b[Y]=x1。 - 第二次输入 (x2, Y)：a[x2] 空，但 b[Y] 已有值 x1，且 x1 < x2（因为 x 递增），所以 b[Y] < x2 成立；同时 a[x2] < Y 也成立。于是会清除旧映射：b[Y] 被清零，a[b[Y]]（即 a[0]）不存在，然后写入 a[x2]=Y, b[Y]=x2。 - 以此类推，每次新输入都会覆盖旧的，最终只保留最后一个映射。a 和 b 各减少 1 个 0，剩余 2n - 2 个 0。✅选 A。

命题视角 命题人喜欢用“双向映射 + 择优更新”的组合来考察学生对数组下标含义的理解，以及条件判断的细致程度。这里的关键是：a[x] 和 b[y] 的下标意义不同，一个存目标，一个存来源，更新时必须同步清除旧的反向映射，否则数据会乱。同时，a[x]<y 和 b[y]<x 这两个条件看似对称，实则分别控制正向和反向的覆盖，缺一不可。

考频与趋势 从题库数据看，一维数组在 CSP 入门级共考过 6 题，模拟在入门级共考过 134 题，说明此类题目是入门级的常客，但近年（2023-2026）考频大幅上升，尤其是 2026 年一维数组考了 59 题，模拟考了 38 题，反映出题目难度在提升，更侧重对数组操作的细节把控。

预测 基于上述趋势，未来 CSP 入门级仍会高频出现“维护双向映射 + 择优更新”的模拟题，但可能会增加一层嵌套（例如同时维护多个映射规则）或引入动态数组/结构体来考察更复杂的下标管理。暂无足够依据预测具体年份的考题形式，但可预期这类题目将保持高热度。