CSP-S 2026 初赛模拟题 第3套 题解

一、单项选择题解析

第1题

答案：A

解析： grep 常用于在文件或输入流中查找包含指定字符串的行。mkdir 创建目录，chmod 修改权限，pwd 显示当前工作目录。

---

第2题

答案：D

解析： 小端序会把低位字节存放在低地址。$0\text{x12345678}$ 的最低字节是 $0\text{x78}$，所以最低地址处存放 $0\text{x78}$。

---

第3题

答案：B

解析： 对固定的 $i$，内层循环中 $j$ 依次为：$1, 2, 4, 8, \ldots$ 直到不超过 $i$，执行次数为 $O(\log i)$。总复杂度为：$O(\log 1 + \log 2 + \cdots + \log n) = O(n \log n)$。

---

第4题

答案：B

解析： 小根堆中元素从小到大依次为：1, 3, 4, 6, 7, 9。连续删除两次堆顶后，删除的是1和3，新的堆顶为4。

---

第5题

答案：C

解析： 树中不存在环，因此一定可以二染色，树一定是二分图。奇环和含三角形的图不是二分图，完全图在顶点数大于2时也不是二分图。

---

第6题

答案：A

解析： 前序第一个结点是根，所以根为A。中序中A左边是D B E，右边是F C。左子树前序为B D E，中序为D B E，后序为D E B。右子树前序为C F，中序为F C，后序为F C。整棵树后序为：D E B F C A。

---

第7题

答案：D

解析： 每个球都有3个盒子可以选择。5个互不相同的球独立选择盒子，共有：$3^5 = 243$。

---

第8题

答案：B

解析： 计算：$3^2 = 9$；$3^3 = 27 \equiv 1 \pmod{13}$。所以：$3^{10} = 3^9 \cdot 3 = (3^3)^3 \cdot 3 \equiv 1^3 \cdot 3 = 3 \pmod{13}$。

---

第9题

答案：B

解析： 图中存在负权边时，Dijkstra不再适用。若不存在负权环，Bellman-Ford可以求单源最短路。Prim和Kruskal用于最小生成树。

---

第10题

答案：B

解析： 构造Trie：根结点1个。cat, car, cart共享前缀ca：根到c，到a，再分出t与r，r后还有t，共新增5个结点。dog, do共享前缀do，再有g，共新增3个结点。总数为：$1 + 5 + 3 = 9$。

---

第11题

答案：B

解析： 这是最小生成树的割性质。如果某条边是一个割中权值唯一最小的边，那么它一定属于所有最小生成树。

---

第12题

答案：C

解析： 每个任务处理时间都是1，且每一时刻只能执行一个任务。要完成任务6，必须完成1, 2, 3, 4, 5, 6这6个任务。所以最早完成时间为6。

---

第13题

答案：A

解析： 逻辑非优先级高于逻辑与，逻辑与高于逻辑或。表达式等价于：(x && y) || ((!y) && z)。代入 $x = \text{true}, y = \text{false}, z = \text{true}$：$x \land y$ 为 false；$\lnot y \land z$ 为 $\text{true} \land \text{true}$，即 true。所以整体为 true。

---

第14题

答案：A

解析： 总共有36种等可能结果。满足 $x < y$ 的有：$5 + 4 + 3 + 2 + 1 = 15$ 种。所以期望得分为：$\dfrac{15}{36} = \dfrac{5}{12}$。

---

第15题

答案：B

解析： 递归式为：$T(n) = T(n/2) + O(n)$。每一层代价依次为：$n, \dfrac{n}{2}, \dfrac{n}{4}, \ldots$ 总和为等比级数，复杂度为 $O(n)$。

---

二、程序阅读题解析

阅读程序（一）解析

程序计算的是字符串的Z数组。$z_i$ 表示从位置 $i$ 开始的后缀与整个字符串的最长公共前缀长度。

16. 答案：A（正确）

数组z初始全为0，循环从 $i = 1$ 开始，不会修改 $z_0$。所以 $z_0$ 始终为0。

---

17. 答案：A（正确）

若所有字符两两不同，则任意非零位置开头的后缀都无法与原串前缀匹配第一个字符。所以所有 $z_i$ 都为0，输出 0 0。

---

18. 答案：A（正确）

输入为 aaaa。Z数组为：0 3 2 1。最大值为3，总和为6。输出为：3 6。

---

19. 答案：C

输入为 ababa。各位置的Z值为：0 0 3 0 1。最大值为3，总和为4。输出：3 4。

---

20. 答案：D

输入为 abcabca。从下标3开始的后缀是 abca，与原串前缀 abca 匹配长度为4。所以 $z_3 = 4$。

---

21. 答案：A

Z算法通过维护右端点 $r$，保证每个字符被扩展比较的总次数为线性级别。因此时间复杂度为 $\Theta(n)$。

---

阅读程序（二）解析

该程序用矩阵快速幂计算斐波那契数列。矩阵 $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ 是斐波那契转移矩阵。

22. 答案：A（正确）

当 $n = 0$ 时，函数直接返回0。

---

23. 答案：A（正确）

当 $n = 1$ 时，先令 $n--$，变为0，循环不执行。此时 $r$ 是单位矩阵，返回 $r.a[0][0] = 1$。

---

24. 答案：B（错误）

快速幂只有在当前二进制位为1时才应该把当前幂乘入答案。如果每轮都执行 r = mul(r, b);，相当于把不该乘的矩阵也乘入答案，结果会错误。

---

25. 答案：B

斐波那契数列为：$F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5, F_6 = 8$。输入6时输出8。

---

26. 答案：B

每次循环 $n$ 右移一位，循环次数为 $\Theta(\log n)$。矩阵大小固定为 $2 \times 2$，每次乘法是常数复杂度。所以总复杂度为 $\Theta(\log n)$。

---

27. 答案：A

对 $n \geq 1$，程序输出第 $n$ 个斐波那契数，其中 $F_1 = 1, F_2 = 1$。

---

阅读程序（三）解析

程序维护一个初始全为0的序列。操作1对区间 $[l, r]$ 整体加 $v$。操作2查询某个位置 $p$ 的当前值。同时，线段树中的 tr[o] 维护该区间最大值，lz[o] 维护整段懒标记。

28. 答案：A（正确）

add 是区间加法，qry 是单点查询。所以该程序支持区间加法和单点查询。

---

29. 答案：A（正确）

每次更新后：tr[o] = max(tr[o<<1], tr[o<<1|1]) + lz[o];。所以 tr[o] 表示该结点对应区间的最大值。根结点对应整个区间，因此 tr[1] 表示整个序列最大值。

---

30. 答案：B（错误）

如果某个祖先区间整体加过值，这个值存在 lz[o] 中。查询子结点时必须累加沿途懒标记。删除 lz[o] + 后，会漏掉祖先区间加法贡献。

---

31. 答案：B

初始序列为：0 0 0 0 0

执行 1 1 3 2 后：2 2 2 0 0

执行 1 2 5 1 后：2 3 3 1 1

查询位置2，输出3。

执行 1 4 4 5 后：2 3 3 6 1

查询位置4，输出6。

所以输出为：

3
6

---

32. 答案：C

先执行区间 $[1, 5]$ 加2，序列为：2 2 2 2 2

再执行区间 $[3, 4]$ 加7，序列为：2 2 9 9 2

最大值为9，所以 tr[1] = 9。

---

33. 答案：B

线段树一次区间修改或单点查询都只访问 $O(\log n)$ 层结点。因此每次操作时间复杂度为 $\Theta(\log n)$。

---

三、完善程序题解析

完善程序（一）：长度受限最大子段和

设前缀和为：$s_i = a_1 + a_2 + \cdots + a_i$。子段 $[j+1, i]$ 的和为：$s_i - s_j$。

若子段长度在 $[L, R]$ 内，则：$L \leq i - j \leq R$，也就是：$i - R \leq j \leq i - L$。

对于每个右端点 $i$，要让 $s_i - s_j$ 最大，就要在合法范围内找最小的 $s_j$。因此用单调队列维护候选下标 $j$，并让队列中的前缀和单调递增。

34. 答案：B

读入 $a_i = x$ 后，前缀和为：s[i] = s[i - 1] + x

---

35. 答案：A

队列维护前缀和递增。如果队尾前缀和大于等于新加入的前缀和，新下标更靠后且值不大，旧队尾无用，应弹出：s[q[t]] >= s[x]

---

36. 答案：A

将候选左端点下标加入队尾：q[++t] = x

---

37. 答案：A

合法左端点 $j$ 需要满足 $j \geq i - R$。若队首下标过小，需要弹出：q[h] < i - R

---

38. 答案：C

当前最优子段和为：s[i] - s[q[h]]

---

完善程序（二）：删边后的连通块

这类删边问题可以倒过来做。正向是不断删边，比较难维护连通性。倒序看，就是从最终图开始，不断把删除过的边加回来。用并查集维护连通块数量 cc：若加入一条边连接了两个不同连通块，则连通块数量减少1。

39. 答案：A

并查集路径压缩写法为：fa[x] = fd(fa[x])，同时这个表达式返回压缩后的根。

---

40. 答案：B

只有当两个点属于不同集合时，合并才会减少连通块数量：x != y

---

41. 答案：A

输入要删除的边编号 de[i] 后，需要标记这条边已经被删除：vis[de[i]] = 1

---

42. 答案：B

构造最终图时，只加入没有被删除的边：!vis[i]

---

43. 答案：A

ans[i] 表示第 $i$ 次删除之后的连通块数量。所以输出：ans[i]