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

【题目】

CSP-J 2019 入门级 第一轮 第17题
阅读程序

#include
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) {//第13行
            if (a[x] > 0)
                b[a[x]] = 0;//第15行
            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;//第27行
    }
    printf("%d", ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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

1. 当 m>0 时，输出的值一定小于 2n。（）
   A. 正确
   B. 错误
2. 执行完第 27 行的 ++ans 时，ans —定是偶数。（）
   A. 正确
   B. 错误
3. a[i] 和 b[i] 不可能同时大于 0。（）
   A. 正确
   B. 错误
4. 右程序执行到第 13 行时，x 总是小于 y，那么第 15 行不会被执行。（）
   A. 正确
   B. 错误
   选择题
5. 若 m 个 x 两两不同，且 m 个 y 两两不同，则输出的值为（）
   A. 2n-2m
   B. 2n+2
   C. 2n-2
   D. 2n
6. 若 m 个 x 两两不同，且 m 个 y 都相等，则输出的值为（）
   A. 2n-2
   B. 2n
   C. 2m
   D. 2n-2m

【题目考点】

1. 数组

2. 映射（对应关系）

【解题思路】

看第一段：

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;
1
2
3
4
5
6

易知a，b是两个整型数组，初值为0。n是数组中元素的个数。
看第二段for循环：

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;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

每次循环输入一对数字x,y，可知m是输入数对的对数
接下来可以通过模拟运行法观察规律

初始状态下a、b初值都为0

i	1	2	3	4
a[i]	0	0	0	0
b[i]	0	0	0	0

1. 如果第一次输入1 2，那么x:1， y:2
   a、b数组初值都为0，a[x] 判断a[x]>0与b[y]>0，都为假，不运行if下的语句。
   执行a[x]=y, b[y]=x，而后a[1]:2， b[2]:1。

i	1	2	3	4
a[i]	2	0	0	0
b[i]	0	1	0	0

2. 如果第二次输入2 3，那么x:2，y:3
   a[x] a[x]>0与b[y]>0都为假，不运行里面if下的语句。
   执行a[x]=y, b[y]=x，而后a[2]:3， b[3]:2

i	1	2	3	4
a[i]	2	3	0	0
b[i]	0	1	2	0

3. 如果第三次输入1 3，那么x:1，y:3
   a[x]

4. 如果输入1 4，那么x:1，y:4
   a[x] 当前a[x]>0，运行b[a[x]]=0，即b[2]=0。
   b[y]=0，不满足条件。
   而后执行a[x]=y, b[y]=x，使得：a[1]:4, b[4]:1

i	1	2	3	4
a[i]	4	3	0	0
b[i]	0	1	2	1

至此，基本可以看出该段代码的功能。
a[x]=y, b[y]=x即为确定了一个映射，或者说一组一一对应关系。
可以设想有左边一列数字，右边一列数字
输入x，y，即为让左边的数字x对应右边的数字y，二者之间连线。
a[x]表示左边的x对应右边的数字，b[y]表示右边的y对应左边的数字。
上述样例输入1 2， 2 3后情况如下

输入1 3后，情况不变。
接着输入1 4后，情况如下：

可知，改变两边数字连线的前提是：两边数字连到的新的数字都比先前连到的数字更大。

比如已有连接1–4，2–3
如果要连接1–3，不可以，因为左边1连接的数字变小了，右边3连接的数字也变小了。
如果要连接1–2，虽然右边2从不连接（连接的数是0）变为了1，但左边1连接的数字变小了，也是不允许的。
接着可以连接2–4，左边2连接的数字从3变为4，右边4连接的数字从1变为2，都变大了，是可以的。修改后，左边的1和右边的3不再连接数字（也可以说连接的数字是0）。

 int ans = 0;
 for (int i = 1; i <= n; ++i) {
     if (a[i] == 0)
         ++ans;
     if (b[i] == 0)
         ++ans;
 }
 printf("%d", ans);
1
2
3
4
5
6
7
8

最后一段为统计两列数字中没有参与连线的数字个数。

比如上图中n为4时，只有1–4,2–3连线时，没参与连线的数字个数为4

至此已了解整段代码的功能为：有两列n个数字，输入m个数对，让两列中对应数字连线，如果新的连线会使得连线两边的数字连到的数字更大，则更新连线。保持每个数字最多参与1次连线。最终统计未参与连线的数字数量。

1. 当 m>0 时，输出的值一定小于 2n。（）
A. 正确
B. 错误
m>0，即为有数对要连线。两列数字，一列有n个，总数字数量是2n个，连线后剩下未连线的数字数量一定小于2n，选A，正确。
2. 执行完第 27 行的 ++ans 时，ans —定是偶数。（）
A. 正确
B. 错误
第27行的++ans是

 if (b[i] == 0)
    ++ans;
1
2

中的++ans。
执行这句后，并不意味着会结束整个for循环。这只是统计过程中的一步。整个统计结束后，剩下未连线的数字数量一定是偶数，但不能保证统计过程中ans一定是偶数。所以该题选B，错误。

比如n为2，输入1 2。两列数字中只有1–2连线，当i为1时，a[1]为2，b[1]为0，运行++ans，ans为1。此时ans就是奇数。

3. a[i] 和 b[i] 不可能同时大于 0。（）
A. 正确
B. 错误
如果左侧第i数字与右侧第i数字同时参与了连线，a[i]与b[i]是可以同时大于0的。选B，错误。

比如n为2，输入1 2，再输入2 1。两列数字中有1–2，2–1连线，那么a[1]是2，b[1]是2，都大于0。

4. 右程序执行到第 13 行时，x 总是小于 y，那么第 15 行不会被执行。（）
A. 正确
B. 错误

if (a[x] < y && b[y] < x) {//第13行
    if (a[x] > 0)
        b[a[x]] = 0;//第15行
    if (b[y] > 0)
        a[b[y]] = 0;
    a[x] = y;
    b[y] = x;
}
1
2
3
4
5
6
7
8

第15行执行的条件为：左侧数字x要与比右侧a[x]更大的数字y相连。原来右侧a[x]自然不用连接数字了，就将其连接的数字设为0。
因此第15行执行的条件并不是xa[x]0。
选B，错误。
5. 若 m 个 x 两两不同，且 m 个 y 两两不同，则输出的值为（）
A. 2n-2m
B. 2n+2
C. 2n-2
D. 2n
如果每次输入的x y中：x都不同，y都不同。那么每次都会将两边没连线的两个数字连起来。一共会连线m对数字，未连线的数字减少2m个，总数字数量是2n个，所以剩下的未连线数字数量为2n-2m个，选A。
6. 若 m 个 x 两两不同，且 m 个 y 都相等，则输出的值为（）
A. 2n-2
B. 2n
C. 2m
D. 2n-2m
m个y都相等，最终y只能与左侧的1个数字相连，未相连的数字为2n-2，选A。

【答案】

1. A
2. B
3. B
4. B
5. A
6. A