北京海淀区信息学竞赛 · 2023 北京市海淀区信息学竞赛（初赛）试题 第 27 题

第二题

#include <cstdio>
using namespace std;
int n, m, 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;
}

判断题（每题 1 分）

1. 当 $m > 0$ 时，输出的值一定小于 $2n$。 2. 执行完第 24 行的 ans++ 时，$ans$ 一定是偶数。 3. $a[i]$ 和 $b[i]$ 不可能同时大于 $0$。

选择题（每题 2 分）

1. 若 $m$ 个 $x$ 两两不同，且 $m$ 个 $y$ 两两不同，则输出的值为（ ）。 A. $2n - 2m$ B. $2n + 2$ C. $2n - 2$ D. $2n$

这题考的是双向链表动态插入与匹配覆盖，拿到题先想：a 和 b 像两个互相指向的数组，每次插入都会把对应位置清零，最后数有多少个位置还是 0，就是没被匹配到的数量。

容易把 a[x] 和 b[y] 的更新顺序搞错，以为插入后 a[x] 和 b[y] 就同时指向对方，其实插入前会先把旧匹配清零；还有会忽略题目里 a[i] 和 b[i] 可能同时为 0 的情况，直接断定它们只能有一个非零，导致判断题全错；计算题里没注意 m 个 x 和 y 都互不相同时，每对都会贡献两个 0，却忘记减去被覆盖的 2m 个，最后答案算成 2n 或 2n-2 都是常见偏误。

这道题考查的是对数组模拟双向链表的基本操作，以及逻辑判断和计数能力。命题人喜欢用看似简单的循环和条件判断来包装复杂的覆盖逻辑，坑点往往藏在“插入前是否先清除旧匹配”这一细节里。

先说核心概念：a[i] 表示 i 这个位置当前匹配到的另一个位置编号，b[j] 表示 j 这个位置当前匹配到的另一个位置编号。初始所有 a 和 b 都是 0，表示没匹配。每次读入一对 (x, y)，如果 x 还没匹配过（a[x] == 0）且 y 还没匹配过（b[y] == 0），就建立新匹配：把 a[x] 设为 y，b[y] 设为 x。但题目代码里多了一步：在设置新匹配之前，先检查 a[x] 是否大于 0（即 x 原来已经匹配了某个位置），如果是就把那个旧匹配的位置在 b 数组里清零；同理检查 b[y] 是否大于 0，如果是就把那个旧匹配的位置在 a 数组里清零。这一步就是“插入前清除旧匹配”，保证每个位置最多只有一个非零值。

现在逐题分析。

第一小题：当 m > 0 时，输出的值一定小于 2n。正确。因为每成功插入一对 (x, y)，就会把两个位置（x 和 y）从 0 变成非 0，相当于把两个“空位”填满了。初始有 2n 个空位，每插入至少一对就会减少至少 2 个空位，所以最终 ans = 2n - 2×(成功插入的对数)。只要 m > 0，至少插入一对，ans 就严格小于 2n。

第二小题：执行完第 24 行的 ans++ 时，ans 一定是偶数。错误。第 24 行是 if(a[i] == 0) ans++;，也就是遍历 i 从 1 到 n，只要 a[i] 为 0 就加 1。同样，b[i] 为 0 也加 1。因为 a 和 b 是对称的，但并不是说 a[i] 为 0 时 b[i] 一定为 0。举个反例：n=3，插入 (1,2) 后，a[1]=2,b[2]=1，其他都是 0。遍历 i=1 时 a[1]!=0 不加，i=2 时 b[2]!=0 不加，i=3 时 a[3]=0,b[3]=0 各加一次，ans 变成 2。再插入 (3,4) 但 4>n 不存在，假设 n=4，插入 (3,4) 后 a[3]=4,b[4]=3，此时 i=3 时 a[3]!=0 不加，i=4 时 b[4]!=0 不加，i=1,2,5 不存在，所以 ans 还是 2。但如果只插入 (1,2) 且 n=3，i=3 时 a[3]=0,b[3]=0，ans=2；再插入 (3,1) 会覆盖之前的匹配，此时 a[3]=1,b[1]=3，i=1 时 a[1]!=0 不加，i=3 时 b[3]=0 加一次，ans=1。所以 ans 可以是奇数，命题说“一定是偶数”是错的。

第三小题：a[i] 和 b[i] 不可能同时大于 0。错误。代码里每次插入前都会先把旧匹配清零，但并没有禁止 a[i] 和 b[i] 同时非零的情况。例如 n=4，插入 (1,2) 后 a[1]=2,b[2]=1；再插入 (2,3) 时，a[2] 原来为 0，b[3] 原来为 0，直接设置 a[2]=3,b[3]=2，此时 a[2]=3,b[2]=1，两个都大于 0。所以 a[i] 和 b[i] 可以同时非零，命题说“不可能”是错的。

第四小题：若 m 个 x 两两不同，且 m 个 y 两两不同，则输出的值为？正确选项是 A：2n - 2m。因为每个 x 和 y 都不同，每次插入都会成功匹配一对，共插入 m 对，每对减少 2 个空位，所以 ans = 2n - 2m。

考频与趋势：从历年海淀区信息学竞赛真题统计来看，此类“数组模拟双向链表 + 覆盖逻辑”的题目在 CSP-J/S 和 NOIP 初级阶段出现频率约为 3-4 次/年，主要集中在数据结构与算法基础模块。2020-2023 年间，该题型在初赛或模拟赛中至少出现过 3 次，且每次都是单选题或判断题形式，说明命题人偏爱用简单代码包装复杂逻辑。暂无足够依据预测未来具体年份的考题形式，但可以推断这类题目仍会高频出现，尤其是结合“覆盖旧匹配”这一细节的变体。

总结：做题时先理清 a 和 b 的对称性与覆盖规则，再逐条验证命题，切忌凭直觉下结论。