2021 年 CSP-S 初赛试题详解

· · 个人记录

1. 试题总结

总体来讲，此次 CSP-S 初赛的难度相比去年有所增加。主要的难点在于，试题中涉及了很多新的知识、算法，例如 球体积交、BASE64、四毛子 RMQ 算法。从这个角度来说，对于曾经没有接触过这些东西的人，在考场上现场理解是极为困难的。

但正因如此，今年的试题才更值得我们去学习总结。

原题链接，在附件中下载

2. 单项选择题解答

  1. Linux 系统下的命令为 ls，而 Windows 系统下则为 dir。

  2. 二进制加法，从第二位开始一直进位。

  3. 此题需要记忆。不单单是数组，函数调用也会占用空间。例如 dfs 程序，如果现在正在调用 10^7 次函数，存储它的栈就会有这么多的元素，有可能就会爆掉空间。

  4. 排序方法的详细信息如下表：

平均情况不用记忆。需要重点关注每个排序的最好/坏情况和稳定性。

还需要记住的是，堆排序是选择排序的优化版本。在具体程序实现中，归并排序或基数排序的效果通常最佳。

  1. 此题有 3n-2 次的方法：将 2n 个数两两配对先比较 n 次，得到比较大的 n 个数和比较小的 n 个数。再用 2(n-1) 次各自比较即可。但为什么它是最佳的，需要用数学方法进行论证。个人没有很好的方法。

  2. 注意到题目对哈希存储的规则就很容易。6,7 在存储时不存在原先的位置上。

  3. 去年考过类似的题。注意 G 是不连通的，对于 10 个点，可以把其中九个点两两连边，从 \dfrac{9\times 8}{2}=36 条边。容易证明是最佳的。

  4. 发现：高度为 x 的二叉树节点数最多为 2^x-1。

  5. 二叉树的前序遍历为：先祖先，再左子树，再右子树；中序遍历为：先左子树，再祖先，再右子树。两者相等说明左子树为空。故 D 是正确的。

  6. 每次交换最多减少一个逆序对。注意到原串有 7 个逆序对，故最少操作 7 次。这里可以采用这样的方式构造：找到最小的，一直交换直到变到第一位；然后找后面最小的，再一直换到第二位；等等。构造虽简单，但保证了每次操作恰好减少一个逆序对。

  7. 发现：Solve(x,n)\equiv 5^{x-1}\pmod n。

费马小定理：p 为质数，x 不是 p 的倍数，则 x^{p-1}\equiv 1\pmod p。

所以 Solve(23,23) 即 5^{22}\mod 23，得 1。

  1. 如果按照 F(1),F(2) 计算一次来算，那么 F(n) 的计算次数应大于等于 F(n)。

    Fibonacci 数列通项公式：F(n) 是 Fibonacci 数列第 n 项，则

    F(n)=\dfrac{1}{\sqrt5}\left[\left(\dfrac{1+\sqrt5}{2}\right)^n-\left(\dfrac{1-\sqrt5}{2}\right)^n\right]

所以说，F(n) 是指数级别的。选 C。

  1. 可以按照选的苹果个数枚举。

  1. 可以按照等腰三角形的腰长枚举，然后讨论底边。注意到如果腰长不等于底边长，对答案的贡献是 3；若相等（即等边三角形），则贡献为 1。

  2. 可以用 Dijkstra 的方法模拟。但注意到图是分层图，就可以一层一层地算出每个点的最短路了。最短路径：A\to C\to E\to H\to J，长度为 19。

3. 阅读程序解答

3.1 第一题

  1. 发现 sq() 函数是关于 int 类型变量，返回值为 int 的函数。故 t 的结果也应该是整数。将 int 改为 double，它的值不变。故正确。

  2. 注意到：sq(d1)-sq(d2)+t 是整数 ( int ) 类型。程序中先将其除掉了 \sqrt{t}，这时自动变为了浮点类型的数，再除以 2 也不是“整除”了。但如果先除 2，因为是整数除整数，所以程序会自动认为除法的意思是整除，进而可能导致答案错误。故错误。

  3. 同样的知识点，x,y 可能是小数，sq(X) 需要 X 是整数，故 sq(x) 相当于先把 x 取整后再运算，进而可能导致答案错误。故错误。

总结一下这三道题的共同点：都是对变量类型和运算与其的关系进行考察，这需要我们对整数和浮点数有非常清晰的认识。

那么，19、20 题就可以直接计算了。

对于第 21 题，我们需要更深入地分析这个程序。t=(a_1-a_2)^2+(b_1-b_2)^2+(c_1-c_2)^2，很自然地想到它是空间上的两点距离的平方。如果 t\ge (d_1+d_2)^2，相当于两点间的距离大于等于 d_1+d_2，此时答案是 0。发现：21 题的四个选项只有一个是求交，其余都是求并，而求并是不会出现 0 这个答案的。故可以直接猜出答案是 C。

若两球相包含或相离，则可很简单地计算出答案。若不然，则可以转化为两个球冠的体积之和。球冠的体积公式如下：

那么只需要算出两个球冠的 h 即可。这可以用余弦定理推导。

左边的球冠，有

h=r_1-OH =r_1-r_1\times \cos \angle AO_1H =r_1-r_1\times \dfrac{r_1^2+d^2-r_2^2}{2d}

最后一步利用了在 \triangle AO_1O_2 里的余弦定理。右边的球冠同理，再用公式计算即可。

3.2 第二题

我们先看 23、25、26 题。

  1. 若 n\ge 1，则调用的 solve 函数中永远满足：h\le m。故 28,38 行调用次数一定为 0；若 n\le 0，调用一次就返回了，次数一定为 1。故不可能分别调用两次以上。

25 . 对于开始的 Solve1(1,n)，如果把 1,n 看作区间 [1,n]，则递归调用相当于砍成两半处理，之后再分别砍成两半变为四半，以此类推。注意到 1+2+4+\cdots+2^k=2^{k+1}-1=2\times 2^k -1，故一共调用的次数是 O(n) 的。Node 的加法是 O(1) 的，每次调用 O(1)，故总复杂度 O(n)。

26 . 和上面分析类似。但此次有所不同：对于 Solve2(l,r) 来讲，额外的运算时间是 O(r-l)。故分成两半后，每半的额外运算时间加起来是 \dfrac{n}{2}\times 2=n；之后再分成四半，额外运算时间加起来是 \dfrac{n}{4}\times 4=n；等等。那么一共会分几次呢？答案是 O(\log n)。每次都会额外贡献 O(n)，故总时间复杂度为 O(n\log n)。

对于剩下的题目，则需要更细致地理解程序。注意到 22 题给我们提示：Solve1 和 Solve2 可能是等价的！我们先看 Solve2。它在干什么呢？wht 求的是 [l,j] 后缀最大值，wmt 求的是 [j+1,r] 的前缀最大值。最后把 wht+wmt 算进 max 中，自然想到：它求的是序列的最大子段和。

Solve1 求最大子段和的方式是线段树的常用维护方式。这里是拓展例题。具体做法是这样的：对于区间 [l,r] 维护前缀最大值 h，后缀最大值 m，总和 w，区间最大子段和 j。转移可以分成左右两个区间递归处理。

22 题，两个函数求解问题相同，自然等价。正确。

24 题，最大子段和为 11 而非 7。错误。

27 题，最大子段和为从 a_2 至 a_{10}，加起来是 17。

3.3 第三题

实际上没什么可以说的。这个代码就是BASE64 加密方法。

  1. 乍一看是正确的，但细致一想会出现问题：如果解密时，输入的加密串是不合法的（例如 1 a），自然就不会正常输出。还有一种方式，就是让解密后的字符串存在换行，这样就不满足“一行”的条件了！

  2. BASE64 的加密是可逆的。

BASE64 的加密过程是将三个字符 a,b,c 加密为四个字符 x_1,x_2,x_3,x_4。其中，加密后的字符仅有 64 种，用六位二进制数表示。

$x_2$ 的前两位是 $a$ 的后两位，后四位是 $b$ 的前四位； $x_3$ 的前四位是 $b$ 的后四位，后两位是 $c$ 的前两位； $x_4$ 的六位是 $c$ 的后六位。

31 . 注意到 for 循环中的操作全部为 O(1)，故总复杂度为 O(n)。

30、33 题需要暴力计算验证。

0 的 ascii 码是 48，1 至 9 依次类推；
A 的 ascii 码是 65，B 至 Z 依次类推；
a 的 ascii 码是 97，b 至 z 依次类推。

4. 完善程序解答

4.1 第一题（魔法数字）

首先，考虑这道题给到我们手里，该怎么做。

这种题不能用很好的数学方法去分析，所以只能类搜索的方式解决。这里用动态规划解决这个问题。设 f_n 表示 n 的表示法所用 4 的个数最小值。那么，如果 i 和 j 能通过一次运算得到 n，则 f_n 对 f_i+f_j 取 \min。

这里注意：f_n 的递推不一定是从 1 至 n！所以我们需要一轮一轮地处理，每一轮根据当前已经处理完的 f 进行递推。

回到原题。第一空填的是 dp 的初状态，显然是 f_4=1，因为表示 4 最少用一个 4。

再次发现，原题采用的是类似 Dijkstra 的方式，每次选择一个 x 进行转移，还运用了 vis 数组。不难想到此时的 x 即为 f 最小的那一个。那么，第二空填 !Vis[n]，因为如果 Vis[n] 是 true 那么它就不可能再被更新了。第三空也显然，把还未确定的选一个最小的确定下来。对于第四空来说，我们看一个“极端情况”：r=1 时的转移。这时只有 i=x=4 可以转移，这自然就排除了选项 A,D。

4.2 第二题（RMQ 区间最值问题）

题干中给出的四毛子算法（The Method of Four Russians）的解释较为详细。这里我给一些补充说明。

这里的笛卡尔树能做到什么呢？首先，它是二叉树，树上的每个结点一一对应原序列上的每个数。并且，对于任意两个结点，它们的最近公共祖先（LCA）即为对应序列区间的最大值。

自然想到，最大的那个数将作为笛卡尔树的根。它的两个儿子呢？如果按根的位置将序列分成两部分的话，那么它们的最大值就分别对应根的左右儿子，依此类推。

这里是 OI-wiki 上的一个例子。（它把 max 改为了 min）

正确性不难得出。

这里的 Euler 序，为从根节点开始，进行如下操作：

将当前节点加入 Euler 序中；
递归所有子树；
将当前节点再次加入 Euler 序中。

利用 Euler 序，我们将 LCA 问题转化为了 +1-1RMQ 问题。如果我们按照序列中每个点的深度作为标准进行比较，那么两点 u,v 的 LCA 为 u 第一次出现的地方 t_1 与 v 第二次出现的地方 t_2 之间的深度最大的点。（若 t_1>t_2 需要交换 u,v）并且，相邻两数深度差距恰好为 1。

回到原题。

剩下的代码对解题无帮助，这里跳过。

5. 总结

写完之后的感觉是，确实难。

在这里给大家一些小建议：