CSP-J 2019 第一轮 第 26 题：程序（二）：m个x两两不同且m个y两两不同的输出

题目

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

若 $m$ 个 $x$ 两两不同，且 $m$ 个 $y$ 两两不同，则输出的值为（）

选项

• A. $2n-2m$
• B. $2n+2$
• C. $2n-2$
• D. $2n$

答案

A

题解

答案是 A．\(2n-2m\)。

数组 a 和 b 最初都为 \(0\)。因为输入的 \(m\) 个 \(x\) 两两不同，\(m\) 个 \(y\) 也两两不同，所以每次读入 (x, y) 时，a[x] 和 b[y] 都仍为 \(0\)。

又因为 \(x,y\ge 1\)，所以：

``cpp if (a[x] < y && b[y] < x) ``

一定成立。内部两个判断 a[x] > 0 和 b[y] > 0 则都不成立，不会清除之前的记录，随后执行：

``cpp a[x] = y; b[y] = x; ``

因此，每组输入都会使两个原本为 \(0\) 的元素变成非零。处理完 \(m\) 组后，两个数组各有 \(n-m\) 个零。

最后统计零的总数，输出就是： \[ \boxed{(n-m)+(n-m)=2n-2m} \]