CSP-J 2019 第一轮 第 23 题：程序（二）：ans是否一定是偶数

题目

#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]$ 的范围内的整数，完成下面的判断题和单选题：

执行完第 $27$ 行的 ++ans 时，$\mathrm{ans}$ —定是偶数。（）

选项

• A. 正确
• B. 错误

答案

B

题解

选 B. 错误。

注意，题目问的是执行完第 27 行的 ++ans 时，并不是程序最终输出时。

举一个反例： ``text 2 1 1 2 ``

处理完输入后，数组为：

统计时，ans 初始为 0。当 i = 1：

• a[1] != 0，不执行第一个 ++ans。
• b[1] == 0，执行第 27 行的 ++ans，此时 ans = 1，是奇数。

所以“一定是偶数”是错误的。

补充：最终输出的 ans 一定是偶数，因为非零的 a[x] = y 和 b[y] = x 总是成对存在，两个数组中零的总数为 2n − 2 × 配对数。但循环中途只统计了一部分，不保证为偶数。