文章

【CSP】CSP-J 2019 第一轮真题解析（二）：阅读程序题

发表于
作者 OneCoder
次浏览 35 分钟阅读

继上一篇单项选择题的全面解析后，本文我们将进入 CSP 初赛试卷中拉开分差的核心板块——阅读程序题。

阅读程序题考察的是考生在脑海里（或草纸上）“人工执行”代码的能力。除了基础的语法规则，它常融合数学数论规律。我们先来看本试卷“阅读程序”模块的第一大题。

📌 二、阅读程序（第一大题）

题目说明：
阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

📜 原题代码提取

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include <cstdio>
#include <cstring>
using namespace std;
char st[100];
int main() {
    scanf("%s", st);
    int n = strlen(st);
    for (int i = 1; i <= n; ++i) {
        if (n % i == 0) {
            char c = st[i - 1];
            if (c >= 'a')
                st[i - 1] = c - 'a' + 'A';
        }
    }
    printf("%s", st);
    return 0;
}

🧠 程序宏观意图分析

在做答之前，第一眼先看懂代码在做什么：

  1. 用 scanf 读入一个字符串进入 st 数组。
  2. 以 $i$ 从 1 到 $n$ 进行遍历。
  3. 条件分支：如果 $n$ 可以被 $i$ 整除（即 $i$ 是字符串长度 $n$ 的约数），则读取数组中对应的字符 st[i - 1]。
  4. ASCII 操作：如果取出字符 c >= 'a'，则通过 c - 'a' + 'A' 计算公式将其转换成大写字母。

    总结： 这个程序的作用就是算出输入字符串总长度 $n$，然后对下标为 $n$ 的所有约数位置对应的字符进行筛选，尝试把它变大写。

第 1 题（判断题）

  1. 输入的字符串只能由小写字母或大写字母组成。（ ）

正确答案： $\times$（错）

深度解析： C++ 库函数中的 scanf("%s", st) 能够吸入所有不在遇到空格、换行之前的非空白可见字符，比如标点符号、数字甚至一些怪异符号。程序段也没有任何异常抛出或拦截输入的操作。输入非英文字母完全合法，只是在 c >= 'a' 时不进行大写化操作而已。

第 2 题（判断题）

  1. 若将第 8 行的 “i = 1” 改为 “i = 0”，程序运行时会发生错误。（ ）

正确答案： $\surd$（对）

深度解析： 这道题抓住了核心命门：第 9 行有一句 n % i == 0。 取模运算 % 本质是除法求余。如果把 i 的初始值强行改成 0，优先执行到第 9 行就会出现数学上的 n % 0（即除数为 0），这会直接引发系统底层的除零错误（Runtime Error / 运行时抛出浮点异常），程序立刻崩溃。

进阶拓展（数组越界的后果）： 很多同学可能会想，既然 i=0，那第 10 行的 st[i - 1] 不就变成 st[-1] 发生数组越界了吗？ 确实如此！如果没有除零错误（假设跳过了第 9 行）而直接触发 st[-1]，在 C++ 中属于未定义行为（Undefined Behavior, UB）。

  1. 它必定是程序的逻辑错误，但不一定保证每次都会像“除零”那样立刻触发系统报错截图。
  2. 读取越界时：程序会读到紧挨着 st 数组内存前方的“脏数据（乱码字符）”。
  3. 写入越界时（如第 12 行 st[-1] = ...）：程序会强行把前面原本不属于它的内存区域覆盖掉，这会破坏其他变量的值，甚至可能破坏函数调用栈。一旦破坏了关键内存保护区，系统就会抛出大名鼎鼎的段错误（Segmentation Fault，简称 Segfault） 并强制杀死程序。

第 3 题（判断题）

  1. 若将第 8 行的 “i <= n” 改为 “i * i <= n”，程序运行结果不会改变。（ ）

正确答案： $\times$（错）

深度解析： 这道题属于经典易错题。
i * i <= n 的本质实际上是只遍历到了 $\le \sqrt{n}$ 的范围。
比如，假设输入长为 $n = 4$。

  • 原版代码会循环 $i = 1, 2, 3, 4$；因为 $4 \% 1==0$、$4\%2==0$、$4\%4==0$，位置 0、1、3 (按索引i-1算) 会被大写处理。
  • 改写之后，只进行到了 $i = 2$ 就退出了！这完美错过了 $i = 4$ 的处理！ 这就导致原本位于比较后半段的约数位置都不会被大写处理，最终字符串和原来截然不同。

第 4 题（判断题）

  1. 若输入的字符串全部由大写字母组成，那么输出的字符串就跟输入的字符串一样。（ ）

正确答案： $\surd$（对）

深度解析： 考寻边界控制与 ASCII 值。
在 ASCII 表中，所有大写字母都在小写字母之前。比如 'A' 是 65，'a' 是 97。
如果输入的全是大写，代码中第 11 行 if (c >= 'a') 这个判断就会变成假（65 不可能 >= 97），于是第 12 行的转换动作压根一次都不会执行，于是原样输出。

第 5 题（选择题）

  1. 若输入的字符串长度为 18，那么输入的字符串跟输出的字符串相比，至多有（ ）个字符不同。 A. 18     B. 10     C. 6     D. 1

正确答案： C

深度解析： 如我们在宏观分析中所述，能决定一个字符是否被改变的原因有两点：

  1. 位置 $i$ 必须是 $n$ 的约数。
  2. 该字符必须被触发进 if (c >= 'a')。 题目问“至多有几个不同”，就是假设每个命中的位置原先全都是小写的情况下发生替换。 问题转化为了：求 18 的约数个数。 18 的约数有：$1, 2, 3, 6, 9, 18$。 总计 6 个约数！所以最多也就 6 个字母会被篡改。选 C。

第 6 题（选择题）

  1. 若输入的字符串长度为（ ），那么输入的字符串跟输出的字符串相比，至多有 36 个字符不同。 A. 36     B. 1     C. 128     D. 100000

正确答案： D

深度解析： 这道题是第 5 题的反向延展。题目问：选项中哪个数字的“约数个数刚好是 36 个”？ 在数论中，如果一个数分解成质因数的乘积为 $p_1^{a_1} \times p_2^{a_2}$，那它的约数个数公式为：$(a_1+1) \times (a_2+1)$。

直接根据选项穷举判断：

  • A 项 36：约数有 ${1,2,3,4,6,9,12,18,36}$，共 9 个。
  • B 项 1：约数有 ${1}$，只有 1 个。
  • C 项 128：$128 = 2^7$。根据公式它的约数个数是 $(7+1) = 8$ 个。
  • D 项 100000：$100000 = 10^5 = (2 \times 5)^5 = 2^5 \times 5^5$。
    套用约数个数公式：$(5 + 1) \times (5 + 1) = 6 \times 6 = 36$。 恰好吻合，选 D。

勘误避坑指南： 很多细心的同学觉得代码开头明明写了 char st[100];，这说明限制死了最大长度只能是不到 100 呀怎么能输入十万长度呢？其实这类题叫做剥离代码框架题，出题人单纯把它当成考查你“根据程序推数学”的一道题，完全忽略了数组边界设定。在 CCF 的考场不要死扣牛角尖，跟着逻辑数学走。

📌 三、阅读程序（第二大题）

📜 原题代码提取

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

#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\n", ans);
    return 0;
}

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

🧠 程序宏观意图分析

在做答之前，我们依然要抽丝剥茧理解程序的实质。这段代码模拟的是一个带有竞争和覆盖机制的双向匹配系统（类似于双向选择的资源分配/抢占）：

  1. 初始状态：程序初始化了两个数组 a 和 b，初始全为 0，代表两类实体（如供给方与需求方）尚未建立任何映射。
  2. 读入关系：循环读入 $m$ 组潜在的匹配对 $(x, y)$。
  3. 竞争与替换逻辑：if (a[x] < y && b[y] < x) 是核心判定规则。这里采用了一种“值越大优先级越高”的贪心策略：只有当新的目标 $y$ 优于 $x$ 当前的匹配对象，且新的 $x$ 也优于 $y$ 当前的匹配对象时，双方才会达成新的匹配关系。
  4. 关系更新操作：在建立新匹配前，必须先释放彼此的旧关系：
    • 清除旧连接：如果 $x$ 之前已有匹配（a[x] > 0），则释放该旧匹配对象（b[a[x]] = 0）。同样，如果 $y$ 之前已有匹配（b[y] > 0），也将原对象释放（a[b[y]] = 0）。
    • 建立新连接：正式写入双向绑定映射 a[x] = y; b[y] = x;。
  5. 绝对对称性：整个更新过程建立了一个严格的对称双向映射网络。只要 a[i] 非零（存着某个数值），位于该数值 b 数组处的记录必然非零并指回 i。这就意味着，无论中途发生多少次互相夺取与覆盖重置，最终 a 数组与 b 数组中成功匹配的数目（非零元素的个数）绝对相等。
  6. 最终统计目标：最后的循环扫描旨在统计未被分配的 0 元素总和。如果最终全场达成了 $K$ 对有效非零匹配，那么未匹配的总数就是两边之和：$(n - K) + (n - K) = 2n - 2K$。

第 1 题（判断题）

  1. 当 m>0 时，输出的值一定小于 2n。 ( )

正确答案： $\surd$（对）

深度解析： 根据题干条件“ $x, y \in [1, n]$ 且均为正整数”，当执行第一组 $(x, y)$ 时，此时全场都是 0，必然满足状态判定 a[x] == 0 < y 和 b[y] == 0 < x。 只要 $m>0$，意味着系统肯定无条件至少执行完成一次成功的第一次大配对操作！虽然在这个过程中后期可能发生不断互相踹掉旧匹配的现象，但由于旧的被踹掉的先决条件是被一个“数值更大”的数取代，所以无论场上局势多么激烈更换，总体一定会诞生至少有一对保持相互牵手成功且大于 0 的链接！即全场总非零配对组数 $K \ge 1$。 带入公式计算，零的数量为 ans $= 2n - 2K \le 2n - 2 < 2n$。绝对正确。

第 2 题（判断题）

  1. 执行完第 27 行的 “++ans” 时，ans 一定是偶数。( )

正确答案： $\times$（错）

深度解析： 这道题出得非常“阴冷刁钻”。 正如我们在宏观分析里得出的结论：最终所有的 ans 加起来（也就是整个大循环彻底执行完毕的最终结果）一定是个偶数 $2n - 2K$。 但是！请注意题目给出的特殊时刻：“每次单步执行完第 27 行时”。 对于任意下标范围扫描 $i$ 时，并没有规定 a[i] 与 b[i] 前后对应的镜像坑位都是并列对称排列的。（仅仅只有总数一样而已，分布位置是不对称映射的！） 举个例子：假设 $n=2, m=1$。唯一的输入为 $(x=1, y=2)$。 执行完后配对网络为：a[1]=2, b[2]=1。其余位都是 0。那么此时：

  • 考察下标扫描到 i=1 的回合里，a[1]=2 （非 0 ）故 ans 没变还是 0。但紧接着检查下面一行发现 b[1]=0 ，此刻恰好触发一次 27 行代码！执行完成并 ++ 取值后局部瞬时状态下：ans = 1！此时显然是个奇数！因此这题完全错误。

第 3 题（判断题）

  1. a[i]和b[i]不可能同时大于 0。( )

正确答案： $\times$（错）

深度解析： 这种绝对化的结论题完全可以用最直白的极简特例推翻。假设运气很好第一组输入数据即为自己指向自己：x=1，y=1。 互相接纳配对之后变成：a[1] = 1; 并且 b[1] = 1;。 这就轻而易举使得同一个下标数字 i=1 的时刻，它们俩同时满足了大于 0！

第 4 题（判断题）

  1. 若程序执行到第 13 行时，x 总是小于 y，那么第 15 行不会被执行。 ( )

正确答案： $\times$（错）

深度解析： 代码执行第 15 行 b[a[x]] = 0 的前提条件仅为 a[x] > 0，即 $x$ 之前已经存在匹配对象。这与输入条件 $x < y$ 并不冲突。

例如，当 $m=2$ 时：

  1. 第一次输入 $(1, 2)$ 满足 $x < y$。配对成功后 a[1] = 2。
  2. 第二次输入 $(1, 3)$ 同样满足 $x < y$。此时新的目标 $y=3$，满足外层更新条件 a[x] < y（即 $2 < 3$）。 进入内层判断后，由于 a[1] = 2 > 0，程序会正常执行第 15 行 b[a[x]] = 0。

因此，即使 $x$ 总是小于 $y$，第 15 行依然可以被执行。

第 5 题（选择题）

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

正确答案： C

深度解析： 因为 $m$ 个 $x$ 两两不同，且 $m$ 个 $y$ 也两两不同，每次判断时对应的数组元素 a[x] 和 b[y] 必然均为初始值 0。 此时，条件 0 < y 和 0 < x 必定成立，且因为元素唯一，永远不会发生替换或覆盖。 因此，程序会成功建立 $m$ 个相互独立的双向映射对。 由于非零的映射关系恰好有 $m$ 对，代入前面的结论公式，最终输出为 0 的元素个数为 $2n - 2m$。故选 C。

第 6 题（选择题）

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

正确答案： A

深度解析： 题设中所有的 $y$ 都相等（例如均为同一个目标对象），意味着 $m$ 个两两不同的 $x$ 在反复竞争唯一的 $y$。 根据代码中的更新规则 b[y] < x，只有当新输入的 $x$ 大于当前已配对的 $x$ 时，才会发生替换。 由于只有一个 $y$ 参与配对，无论中间经历多少次比较覆盖，最终只会有唯一的、值最大的那个 $x$ 成功与该 $y$ 绑定。 其余落选或被替换的 $x$，其对应的数组值都会回归为 0 状态。 因此，整个流程结束时，建立的有效配对恰好仅有 1 对。 将配对数 $K=1$ 代入公式计算，最终输出的 0 的个数必然为 $2n - 2 \times 1 = 2n - 2$。故选 A。

📌 四、阅读程序（第三大题）

📜 原题代码提取

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

#include <iostream>
using namespace std;
const int maxn = 10000;
int n;
int a[maxn];
int b[maxn];

int f(int l, int r, int depth) {
    if (l > r)
        return 0;
    int min = maxn, mink;
    for (int i = l; i <= r; ++i) {
        if (min > a[i]) {
            min = a[i];
            mink = i;
        }
    }
    int lres = f(l, mink - 1, depth + 1);
    int rres = f(mink + 1, r, depth + 1);
    return lres + rres + depth * b[mink];
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 0; i < n; ++i)
        cin >> b[i];
    cout << f(0, n - 1, 1) << endl;
    return 0;
}

题目说明： 根据上述代码逻辑，完成对应的判断与选择作答。

🧠 程序宏观意图分析

从数据结构层面分析，该程序旨在体现一种建树与分治的过程：

  1. 寻找最小值（建树起点）：函数 f(l, r, depth) 遍历区间 [l, r]，找出数组 $a$ 在该区间内的最小值及其下标 mink。
  2. 区间划分（递归分治）：以 mink 为中心点，将区间分为左右两部分：左区间 [l, mink-1] 和右区间 [mink+1, r]，分别进行递归调用，并且让递归深度 depth 加一。
  3. 结果累加：返回值 lres + rres + depth * b[mink] 表示累加所有节点的（深度 $\times$ b数组对应值）。

本质总结：这是一段利用数组 $a$ 构建 笛卡尔树（Cartesian Tree） 的代码，并在此过程中计算了数组 $b$ 元素的加权深度和。

拓展：什么是笛卡尔树？ 笛卡尔树是一种基于序列构建的特殊二叉树，它同时满足两个基础数据结构的性质：

  1. 二叉堆属性：父节点的权值总是小于（或大于）其左右子节点。本题中通过抽取每一层的最小值作为子树的根节点，体现了小根堆的特性。
  2. 二叉搜索树属性（BST）：对笛卡尔树进行中序遍历，得到的元素序列必定与序列原来的顺序一致。代码中以位置下标 mink 严格划分 [l, mink-1] 为左子树，[mink+1, r] 为右子树，从而维护了原数组基于下标维度的二叉搜索树属性不变。

第 1 题（判断题）

  1. 如果 a 数组有重复的数字，则程序运行时会发生错误。 ( )

正确答案： $\times$（错）

深度解析： 循环判断条件为 if (min > a[i])，即严格大于。当存在多个相等的最小值时，程序只会取最先遍历到的下标作为 mink。随后的区间划分能够正常进行，不影响递归逻辑，不会引发死循环或越界错误。

第 2 题（判断题）

  1. 如果 b 数组全为 0，则输出为 0。 ( )

正确答案： $\surd$（对）

深度解析： 函数 f(l, r, depth) 的返回值规则分为两部分：

  1. 边界条件：当 $l > r$ 时，递归触底，直接返回 0。
  2. 中间节点：返回值为子树结果与当前节点之和：lres + rres + depth * b[mink]。 由假设可知所有的 $b_i = 0$，意味着当前层的乘项 depth * b[mink] 必定为 0，这使得式子退化为单纯的合并律：lres + rres。 由于递归最底层的边界状态返回的必然是 0，导致从底部升上来的所有 lres 与 rres 变量统统接收到了 0。自底向上进行层层回溯，每一层的计算实际上都在执行 $0 + 0 + 0 = 0$。因此最终函数输出结果必然为 0。

第 3 题（选择题）

  1. 当 n=100 时，最坏情况下，与第 12 行的比较运算执行的次数最接近的是： ( )。 A. 6     B. 100     C. 5000     D. 600

正确答案： C

深度解析： 最坏情况：每次划分得到的最小值都恰好在区间的最边缘（例如输入数组 $a$ 呈现单调递增或递减）。这会导致分割时一边区间为空，另一边区间包含全部剩余元素，递归树退化为一条链。 此时比较次数构成等差数列：$100 + 99 + 98 + \dots + 1 = \frac{100 \times 101}{2} = 5050$ 次。 最接近 5050 的选项是 C。

第 4 题（选择题）

  1. 当 n=100 时，最好情况下，与第 12 行的比较运算执行的次数最接近的是： ( )。 A. 5000     B. 6     C. 100     D. 600

正确答案： D

深度解析： 要理解最终比较次数的计算方式，须重点剖析区间遍历次数与笛卡尔树节点深度之间的等价转换机制：

  1. 代码中第 12 行的比较运算位于 for (int i = l; i <= r; ++i) 内部。这意味着每执行一次 f(l, r, depth)，比较次数等于当前区间 [l, r] 的长度。因此，总执行次数 = 整个递归过程中产生的所有子区间长度之和。
  2. 为什么“区间长度之和”刚好等于“所有节点的深度之和”？我们可以转换视角，追踪数组中任意一个个体元素 $a[k]$ 的扫描轨迹：
    • 初始主干层（深度 1）：区间包含全量元素，$a[k]$ 参与循环被比较 1 次。
    • 随后区间被割裂：只要 $a[k]$ 尚未被确立为它所在区间的最小值，就会被分配到新产生的更小的左区间或右区间（深度 2），再次参与 for 循环比较 1 次。
    • 以此类推，$a[k]$ 会伴随着不断深入的递归分治，一层层地累加比较次数。直到在某一层深度中它成为了那个子区间的最小值（落定为树节点），此时它被剥离出子区间，不再参与后续的扫描。
    • 核心定理：一个元素在 for 循环中被扫描的总次数，严格等同于它在笛卡尔树中最终落定的节点层数（即深度）。 综上所述，将每一个元素的独立扫描次数进行加总，得到的结果在数学上绝对等于“整棵树中所有节点的深度总和”。

最好情况：为了使这个计算求和结果尽量小，也就是整体树的深度尽可能浅，最好的情况便是每次的最小值正好位于正中央将区间对半平分。这会让生成的笛卡尔树成为标准的平衡二叉树。 对于 $100$ 个节点构造出的满二叉图层分布：

  • 深度 1 至 6 层能排满的节点数依次为：$1, 2, 4, 8, 16, 32$，共排满 63 个节点。
  • 深度 7 层的节点数为：$100 - 63 = 37$。

深度总和累加式 $= 1 \times 1 + 2 \times 2 + 4 \times 3 + 8 \times 4 + 16 \times 5 + 32 \times 6 + 37 \times 7 = \mathbf{580}$。 最接近 580 的选项是 D。

第 5 题（选择题）

  1. 当 n=10 时，若 b 数组满足，对任意 0<=i<n，都有 b[i] = i + 1，那么输出最大为 ( )。 A. 385     B. 383     C. 384     D. 386

正确答案： A

深度解析： 已知数组 $b$ 取值为：${1, 2, 3, \dots, 10}$。 要使目标加权函数 $\sum (b_i \times \text{depth})$ 最大，需要让较大的 $b_i$ 匹配更大的节点深度。 通过调整数组 $a$ 的内容，可以构造出极端的链状退化树（所有节点独享一条链），使其最大深度达到 10。 将权值从小到大对应从浅到深的节点，即：深度 1 配置权值 1，深度 2 配置权值 2……深度 10 配置权值 10。 所求和转化为数字平方和的公式计算： $1^2 + 2^2 + 3^2 + \dots + 10^2 = \frac{10 \times 11 \times 21}{6} = \mathbf{385}$。

第 6 题（选择题）

  1. (4分) 当 n=100时，若 b 数组满足，对任意 0<=i<n，都有 b[i] = 1，那么输出最小为 ( )。 A. 582     B. 579     C. 581     D. 580

正确答案： D

深度解析： 由于所有的 $b_i=1$，目标求和式简化为单纯求解：所有节点的深度总和。 题目要求结果最小，等同于要求构造的递归树达到最大复用效率的平衡二叉树状态。 这与第 4 题的计算逻辑完全等价：100 个节点构造的平衡二叉树的所有节点深度之和恰为 $580$。

[!TIP] 本篇结语 以上是 2019 年 CSP-J 真题“阅读程序题”的逻辑详解。这三大题重点考查了程序的运行机制分析能力、匹配模拟、以及蕴含的数据结构（如笛卡尔树建树过程）理解。 下一级段，我们将迈入第一轮真题中考查完整算法搭建思维的“完善程序题”篇，请大家继续保持关注。

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

"luogu-"系列题目可在洛谷题库进行在线评测。

"bcqm-"系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号
GESP/CSP 认证学习微信公众号
CSP, J
CSP C++ 第一轮 初赛 阅读程序
本文由作者按照 CC BY-NC-SA 4.0 进行授权