[数据结构与算法]CSP-S1 2021 非官方解答

如有错误欢迎批评指正。

选择题

1. cd = change directory 切换目录，cp 复制文件或目录，all 不知道。选 A。
2. 略。选 B。
3. 爆栈。选 A。
4. 考查算法基础。选 C。
5. $2n$ 个数，两两比较大小，找出 $n$ 个较大值，$n$ 个较小值，然后分别 $n?1$ 次比较找出最大最小值。总计 $3n?2$ 次。选 C。
6. 手动模拟即可。选 C。
7. 36 条边，最少要 9 个点，再加一个点使其不连通，故最少要 10 个点，选 C。
8. $2^{11}?1=2047>2021$，选 B。
9. 考查算法基础。前序根左右，中序左根右，显然符合题意时每一次都没有左。选 D。
10. 手动模拟即可。一次顶多减少 1 个逆序对，而这里总共有 7 个逆序对，故答案下界为 7。选 A。
11. 简单分析可知 $\text{solve}(t,n)=5^{t?1}\mathrm{m}\mathrm{o}\mathrm{d}n$。即求 $5^{22}\mathrm{m}\mathrm{o}\mathrm{d}23$，由费马小定理，易知答案为 1。选 A。
12. $T(n)=T(n?1)+T(n?2),T(1)=1,T(2)=1$，故 $T(n)=\Theta (Fi{b}_n)$。由特征方程等方法，易知 $Fi{b}_n=\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2}{)}^n?(\frac{1?\sqrt{5}}{2}{)}^n)$，在渐进意义下与 $2^n$ 同阶。选 C。
13. 设 $f(n,0/1)$ 表示已经选到第 $n$ 个苹果，第 $n$ 个苹果取或没取时的方案数。为了方便计数，将一个苹果都不选的方案计算在内，易知：
    $$?\begin{array}{l}f(1,1/0)=1\\ f(n,1)=f(n?1,0)n\ge 2\\ f(n,0)=f(n?1,1)+f(n?1,0)n\ge 2\end{array}$$
    所求即为 $f(8,0)+f(8,1)?1$。注意到 $f(n?1,1)=f(n?2,0)$，这实际上是 Fibonacci 数列。背诵易得答案为 $55?1=54$。选 C。
14. 等边有 9 个。等腰不等边时腰长为 1, 2, 3, 4 时分别有 0, 2, 4, 6 种可能底边，其余有 8 种，此时每种选择的边长在三位数中有 3 种排列方式。故答案为 $9+(8\times 5+6+4+2+0)\times 3=165$。
15. 手动 Dijkstra 即可。选 B。

阅读程序

题目 1

程序简述：求两个球交的体积，保留 4 位小数输出。

判断 1. 正确。只要该整数在 $[?2^{53},2^{53}]$ 内，就可以用 double 精确表示。

判断 2. 错误。int / sqrt(t) / 2 相当于 double / int，而 int / 2 / sqrt(t) 时，int / 2 是整除，产生误差。

判断 3. 错误。要求传 int，却传进去 double，那肯定不行。

判断 4. 正确。手算即可。答案为 $\frac{5\pi }{12}$，约为 1.3089969…。

选择 1. 此时一个球完全在另一个球内，答案就是较小的球的体积 $\frac{4\pi }{3}$。选 D。

选择 2. 显然选 C。

题目 2

程序简述：两种求最大连续子段和的程序。

程序一中某一个段的 $h,j,m,w$ 四个属性分别表示：从序列左端点开始的子段的答案，这个段的答案，从序列右端点结束的子段的答案，这一段所有数的和。

分治进行处理。更新答案时，一个段的最大连续子段和对应的子段要么全落在左侧、要么全落在右侧、要么一部分落在左侧，一部分落在右侧。故有转移 $j=\max (\max (j,\text{o.}j),m+\text{o.}h)$ 。同理可得剩下三个转移。

判断 1. 正确。均会输出这个序列的最大子段和。

判断 2. 错误。只有在 $n$ 为负数时会执行 1 次。

判断 3. 错误。答案显然为 11，选择 $[2,2]$ 子段即可。

选择 1. $T(n)=2T(\frac{n}{2})+\Theta (1)$，由主定理 $T(n)=\Theta (n)$。选 B。

选择 2. $T(n)=2T(\frac{n}{2})+\Theta (n)$，由主定理 $T(n)=\Theta (n\log n)$。选 C。

选择 3. 除了 -3 全选。答案为 17，选 B。注意第一个 10 是 $n$。

题目 3

程序简述：base64 编码 / 解码器。

判断 1. 错误。decode 时对原串字符并没有限制，所以反例为一个原串中有 \n 的字符串 base64 加密后 decode。标准反例：1 ZnVjawpjY2Y=

判断 2. 正确。先编码后解码，肯定得到原串。

判断 3. 错误。解码出来为 Helloworld。

选择 1. 显然 $\Theta (n)$。选 B。

选择 2. 目前本题有争议。char 范围是 -128~127，故赋值为 0xff 应为 -1，选 D。但是据 cppreference 以及 OIer 测试，不同平台上测出的结果不同。¹

选择 3. 手动解码即可。可以先靠判断位数与等号个数排除 AC，接下来只算 G/W 不同即可。选 D。

完善程序

题目 1

处理方法类似于 Dijkstra。

34. 初始化：4 只需要 1 个 4 就能表示，选 D。
35. 选 A，其正确性可以通过反证法说明。B 不对，令 $n=2$ 即可。C 错的离谱。D 不对，一次更新后并不能保证其为最优答案。
36. 从还没有确定答案的点中，选一个当前答案最小的点。选 D。
37. 用已经知道答案的点去更新目前这个点的答案。选 C。本题有些争议。AD 错的都蛮离谱的。但是 B 似乎没问题？

题目 2

考 Four Russians 就离谱

笛卡尔树这里不做介绍，有兴趣的可以去 OI-wiki 上学习。链接：笛卡尔树 - OI wiki。

笛卡尔树的构建方法为「单调栈维护右链」，请记住这一点。

38. 后文中，query 求的是节点深度的最小值，所以不难分析出这里要建立的是一个键值满足大根堆性质的笛卡尔树。若 p->val 大于栈顶的值时，就不断弹出元素，将其放置于 p 左边。选 A。
39. 维护右链。选 D。
40. 建出笛卡尔树后，问题转化为一个区间的 LCA 问题。这等价于在两个对应点中查找 dep 最小值。选 A。
41. 上文说了，比较 dep 大小。选 D。
42. 由于转化后的问题为 +/-1 RMQ，所以可以枚举所有的差分序列，计算其最大值的位置。这里的 v 是当前数字与第一个数字的差值。由 41 问的选择知，一个 mask 的某一位为 1 时，表示前面的数大于后面的数，故应将 v 减 1。只有 D 项符合。选 D。
43. 截取差分数组中 $[L,R]$ 的对应段，注意边界判断即可。选 C。