2021 CCF CSP-S 第一轮（提高级 C++）

先明确任务：查看当前目录中有哪些文件，而不是改变所在位置。ls 不带路径时列出当前目录内容，因此选 A。

cd 用于切换目录，cp 用于复制文件；all 不是本题所需的列目录命令。若要显示点号开头的隐藏文件，通常另加 -a 选项，但不影响本题判断。

先按位权转换：$00101010_2=32+8+2=42$，$00010110_2=16+4+2=22$。相加得到 $64=2^6$，写成八位二进制是 $01000000_2$，选 B。

也可从右向左竖式相加：最低位为 0，第二位的 $1+1$ 产生进位，此后连续向高位传递。不能把二进制中的“满二进一”当作十进制加法。

普通递归调用需要保存当前函数的返回位置、局部变量等信息，形成一层调用栈帧。递归没有返回时，这些栈帧会同时保留；深度不断增加，所需栈空间也不断增加。

系统为线程提供的栈空间有限，深度过大可能造成栈溢出，所以选 A。此处讨论通常的递归实现；编译器是否能优化某些特殊递归，不改变“可能栈溢出”的判断。

稳定性要求：两个关键字相等的元素，排序后仍保持原来的先后次序。可给相等元素附上标签，再观察标签顺序。

堆排序会把堆顶与末尾元素交换，交换可能跨过另一个相等元素。例如两个相等元素组成的堆，取出堆顶时的一次交换就可能颠倒二者。因此堆排序不稳定，选 C。通常教材实现中，插入排序、冒泡排序及合并时优先取左侧相等元素的归并排序均可保持稳定。

先把 $2n$ 个数分成 $n$ 对，每对比较一次，共 $n$ 次。每对较大者进入最大值候选组，较小者进入最小值候选组。

从 $n$ 个较大者中找最大值需 $n-1$ 次，从 $n$ 个较小者中找最小值也需 $n-1$ 次，合计 $n+(n-1)+(n-1)=3n-2$，选 C。

为什么这种配对能达到最优？每个非最大元素都必须有一次“输”的证据，每个非最小元素都必须有一次“赢”的证据。比较对抗分析中，只有尚未比较过的两个元素首次配对，才能一次同时有效减少两类候选；最多有 $n$ 次这样的双重收益，其余候选仍需逐个排除，得到同样的下界。

依次算初始地址并处理已有冲突：0、1、2、3、4、5 的初始地址分别是 0、1、4、9、5、3，均为空，可以直接存放。

插入 6 时，$36\bmod11=3$。地址 3、4、5 已占用，继续探测到空地址 6，因此 6 存在地址 6。

插入 7 时，$49\bmod11=5$。地址 5、6 都已占用，第一个空位是 7，因此选 C。线性探测应检查已经存入的所有元素，而不只是上一个数。

要在固定点数下容纳尽量多的边，应把尽量多的点集中到一个完全图中，同时留下至少一个独立点以保证非连通。因此 $v$ 个点最多有 $\binom{v-1}{2}$ 条边。

若只有 9 个点，至多是 $K_8$ 加一个独立点，边数为 28，不够 36。若有 10 个点，$K_9$ 加一个独立点恰有 $9\times8/2=36$ 条边。下界可达到，所以至少需要 10 个点，选 C。

根结点处于第 1 层，第 $i$ 层最多有 $2^{i-1}$ 个结点。高度为 $h$ 的二叉树最多容纳 $1+2+\cdots+2^{h-1}=2^h-1$ 个结点。

高度 10 时上限为 1023，小于 2021；高度 11 时上限为 2047，可以容纳 2021 个结点。因此最小高度是 11，选 B。这个问题求的是“至少”，应考虑树尽量宽，而不是退化为链的情况。

前序次序是“根、左、右”，中序次序是“左、根、右”。若某结点存在非空左子树，前序中该结点先于左子树，中序中却晚于左子树，两种次序就不同。

所以不仅根没有左子树，右子树里的每个结点也都不能有左子树。反过来，若整棵树是一条向右延伸的链，两种遍历都从根沿右儿子访问，次序相同。因此选 D。这里沿用遍历题通常假定的结点可区分条件。

按目标字母顺序将 DACFEB 写为 $4,1,3,6,5,2$。逐个统计右侧更小的数：4 后面有 1、3、2，共 3 个；1 后面没有；3 后面有 2；6 后面有 5、2；5 后面有 2。

逆序对总数为 $3+0+1+2+1=7$。一次相邻交换最多消去一个逆序对，所以至少要 7 次；不断交换相邻逆序元素又能恰好做到每次减少一个，故最少就是 7 次，选 A。

递归边界 solve(1,n)=1，每增加一层就多乘一个 5 并取模，因此 solve(t,n) 等于 $5^{t-1}\bmod n$。代入本题得到 $5^{22}\bmod23$。

23 是质数，且 5 与 23 互质，费马小定理给出 $5^{22}\equiv1\pmod{23}$，所以选 A。指数是 22，因为边界层直接返回 1，并不再乘 5。

令调用工作量为 $T(n)$。当 $n>2$ 时，要分别计算 $F(n-1)$ 和 $F(n-2)$，所以 $T(n)=T(n-1)+T(n-2)+O(1)$。相同子问题会在不同分支反复计算。

递归树高度为 $O(n)$，每个结点至多分出两个孩子，可以用 $O(2^n)$ 作为上界，给定选项中选 C。更紧的增长量是 $\Theta(\varphi^n)$，其中 $\varphi=(1+\sqrt5)/2$；这不影响 $O(2^n)$ 这个正确上界。若改成记忆化或顺序递推，才可降到线性时间。

先允许一个也不选，设前 $i$ 个苹果的合法方案数为 $f_i$。若不选第 $i$ 个，有 $f_{i-1}$ 种；若选第 $i$ 个，第 $i-1$ 个必须不选，剩下有 $f_{i-2}$ 种。

因此 $f_i=f_{i-1}+f_{i-2}$，从 $f_0=1,f_1=2$ 依次得到 $f_2$ 至 $f_8$ 为 3、5、8、13、21、34、55。

最后排除“一个也不选”的唯一方案，得到 $55-1=54$，选 C。

分成等边和恰有两边相等两类。等边对应 111、222、……、999，共 9 个三位数。

恰有两边相等时，设边长为 $x,x,y$，其中 $1\le x,y\le9$ 且 $y

e x$。正边长下只需额外保证$y<2x$。当$x=1,2,\ldots,9$时，可选的$y$ 个数依次为 0、2、4、6、8、8、8、8、8，总计 52。

每组不同的 $x,y$，不相等的数字 $y$ 可放在百、十、个位三个位置，因此共 $9+52\times3=165$，选 C。把等边先单列，能避免把它重复乘 3。

按图的层次从左向右计算，记 $d(X)$ 为 A 到 X 的最短距离。第一层有 $d(B)=2,d(C)=5,d(D)=1$。

第二层：$d(E)=\min(2+12,5+6,1+13)=11$；$d(F)=\min(2+14,5+10,1+12)=13$；$d(G)=\min(2+10,5+4,1+11)=9$。

第三层：$d(H)=\min(11+3,13+6,9+8)=14$；$d(I)=\min(11+9,13+5,9+10)=18$。最后 $d(J)=\min(14+5,18+2)=19$，选 B。对应路径为 A→C→E→H→J。这样既给出一条路径，也证明其他进入各层的路径不会更短。

先检查取值范围。每个坐标绝对值不超过 1000，坐标差绝对值不超过 2000，三个平方和至多 $3\times2000^2=12000000$，在通常的 32 位 int 范围内，也可由 double 精确表示。

改类型后，存入 t 的整数值没有变化；后面比较用到的整数及平方根运算也具有相同数值。因此按题目通常的数值环境，输出不变，判断正确。不能仅凭“double 更精确”下结论，关键是本题原来的整数计算没有溢出。

原式分子为整数，但先除以 sqrt(t) 后执行浮点除法；改成先 /2 时，分子与 2 都是整数，会先截去小数部分。

用题中两单位球、球心距为 1 的输入举例：分子为 1，原式 $1/1/2=0.5$，得到 $x=y=0.5$；改后整数 $1/2=0$，得到 $x=y=1$。最终输出会从 1.3090 变成 4.1888，所以判断错误。

函数声明 sq(const int x) 决定了实参先转成整数，然后才平方。inline 只是实现层面的提示，不会改变参数类型。

仍取半径都为 1、球心距为 1 的情况，原程序中 $x=y=0.5$，直接平方为 0.25；调用 sq(x) 时却先把 0.5 转为 0，平方为 0。相交体积将被算成 0，输出改变，因此判断错误。

输入表示两个半径为 1 的球，球心分别为 $(0,0,0)$ 和 $(1,0,0)$。距离平方 $t=1$，大于半径差平方 0、小于半径和平方 4，进入部分相交分支。

$r=\arccos(0.5)=\pi/3$，$x=y=1-(1-1+1)/1/2=0.5$。代入输出式得到 $[0.25\times2.5+0.25\times2.5]\pi/3=5\pi/12\approx1.30899694$。保留四位小数为 1.3090，判断正确。

两个球的球心都是 $(1,1,1)$，所以 $t=0$；半径分别为 1 和 2，半径差平方为 1。满足 $t\le(d_2-d_1)^2$，进入第一个分支。

程序取较小半径 1，输出 $1^3\times(\pi/3)\times4=4\pi/3\approx4.18879020$。固定四位小数得到 4.1888，选 D。这里直接使用包含分支，不会执行除以球心距的公式。

把前三个输入量看作球心坐标，第四个量看作半径，则 t 是球心距平方。若距离不大于半径差，交集是较小的整个球，程序输出其体积；若距离不小于半径和，交集体积为 0。

剩下情况是部分相交。x、y 是公共截面两侧球冠的高度，球冠体积公式为 $V=\pi h^2(3R-h)/3$。程序把两个球冠体积相加，恰好得到两球公共部分的体积，因此选 C。几何解释以半径非负为前提。

先读懂 Node：h 为最大前缀和，j 为最大子段和，m 为最大后缀和，w 为区间总和，前三项允许空段，因此至少为 0。合并时最大子段只可能完全在左边、完全在右边，或由左边最大后缀与右边最大前缀拼成。

solve1 把这四项一起返回；solve2 用循环现算左后缀和右前缀，再与两侧递归答案比较。两者枚举的三类情况完全相同，因此在题目预期的有效数组范围和无整数溢出条件下，输出相等，原题判断为正确。全负数组也相等，均为 0。

当初始 $n\ge1$ 时，递归参数是非空闭区间。单个元素直接返回；长度至少为 2 时，中点 j 满足 $h\le j<m$，所以 [h,j]、[j+1,m] 都非空。由归纳可知不会进入 h>m。

即使考虑初始 $n=0$ 的空区间，每个函数也只会在第一次调用时返回一次，不可能各执行两次及以上。因此判断错误。

首个数 5 是数组长度，实际序列为 $-10,11,-9,5,-7$。逐项维护“以当前位置结尾、允许为空的最大和”，递推为 $s_i=\max(0,s_{i-1}+a_i)$。

依次得到 0、11、2、7、0，全局最大值为 11，对应只选第二项。7 只是处理到第四项时的局部结果，不能覆盖此前已出现的 11。两行均输出 11，题述第二行为 7，故判断错误。

solve1 的每个叶子处理一个元素，内部结点通过重载加法做固定次数的加法和比较，合并耗时为 $\Theta(1)$。

一棵有 n 个叶子的二叉递归树共有 $2n-1$ 个结点，每个结点工作量为常数，所以总时间为 $\Theta(n)$，选 B。也可写递推式 $T(n)=2T(n/2)+\Theta(1)$；不能把递归层数直接当作总时间。

solve2 在每个非叶区间中，从中点向两侧分别扫描。这两个循环合计访问区间内的所有元素，所以长度为 k 的一次调用，合并部分需 $\Theta(k)$。

同一递归层的区间互不重叠，总长度为 n，因此每层总工作量为 $\Theta(n)$。递归有 $\Theta(\log n)$ 层，总时间为 $\Theta(n\log n)$，选 C。与上一题的差别正是合并需要重新扫描。

使用与分治答案等价的线性手推：以当前位置结尾的最大非负子段和，依次为 0、2、12、12、4、13、9、4、13、17。过程中出现的最大值为 17。

达到它的连续子段是第 2 至第 10 项：$2+10+0-8+9-4-5+9+4=17$，因此第一行输出 17，选 B。中间虽有负数，但连接两端正数仍可能比舍弃整段更优。

输入格式合法仅表示读到了整数和不含空白的字符串，并没有保证非零 opt 对应的字符串是有效 Base64。decode 每次无条件按 4 个字符处理。

例如输入 1 A，循环仍会访问 str[i+2]、str[i+3]，超过该字符串允许访问的位置，产生未定义行为，不能保证正常输出两行。因此判断错误。正常解码需要另外校验字符集合、长度和填充位置。

按本题预期的普通 ASCII 字符模型，编码把 3 个字节的 24 位拆成 4 个 6 位索引，解码再将这些位拼回原来的 3 个字节。最后不足 3 字节时，编码加 =，解码通过 = 判断只还原 1 或 2 个字节。因此对编码结果再解码可还原原串，原题答案为正确。

需区分命题意图与代码适用范围：题面“任意不含空白字符”若包含最高位为 1 的任意字节，在有符号 char 环境中，str[i] >> 2 可能为负并造成负下标。本实现没有先转为 unsigned char，不能据此证明对任意字节串都安全；这里保留原答案，并明确其字符范围前提。

先确定 opt 为 1，程序执行解码。每四个编码字符还原一组：SGVs→Hel，bG93→low，b3Js→orl，ZA==→d。

拼接得到 Helloworld，其中第六个字符是小写 w，而题述 HelloWorld 使用大写 W。字符大小写不同，字符串就不相等，所以判断错误。

主循环每次让 i 增加 3，每轮处理 3 个输入字符并追加 4 个输出字符，因此循环次数为 $\lfloor n/3\rfloor$。末尾分支最多处理剩余两个字符。

在字符串追加按摊还常数时间计算的通常模型下，总耗时为 $\Theta(n)$，选 B；输出长度 $4\lceil n/3\rceil$ 也与输入长度同阶。位运算次数固定，并不会引入对数因子。

初始化先把 table 的所有位置设为 0xff，随后只覆盖 Base64 字符以及等号对应的位置。下标 0 对应空字符，不在这些字符中，所以仍保留全 1 的字节位型。

本题答案采用 8 位有符号 char 环境，全 1 位型表示 -1，转换成 int 后输出十进制 -1，选 D。C++ 的普通 char 是否有符号取决于实现，若使用无符号 char 则可能得到 255；因此这道题具有环境前提，不是跨平台固定输出。

把 10 个字符按三个一组分为 CSP、202、1cs、p。前三组分别编码为 Q1NQ、MjAy、MWNz；最后仅剩一个字节 p，其编码为 cA==。

例如首组 ASCII 值为 67、83、80，拆出的四个索引是 16、53、13、16，对应 Q、1、N、Q。将四组拼接，得到 Q1NQMjAyMWNzcA==，选 D。末尾两个等号来自只剩一个字节，而不是编码的普通字符。

先定义代价：F[x] 是表示正整数 x 所用的数字 4 的最少个数。无需任何运算就能写出一个 4，因此初始已知状态是 F[4]=1，选 D，其余状态暂为无穷大。

若设为 0，就把数字 4 本身的使用次数漏掉了。F[1]=2 虽对应表达式 $4/4$，却不应代替基础状态；算法应从最基本的一个 4 自动推导这些组合。

Vis[x] 表示 x 的最小代价已经确定。每轮从未确定状态中选择 F 最小的一个，再与已确定状态组合产生候选表达式。两个子表达式各至少用一个 4，所以组合的代价严格大于每个子表达式的代价，这支持按代价递增确定状态。

当目标 n 被确定后即可结束，故循环条件是 !Vis[n]，选 A。仅仅发现 F[n] 为有限值，不表示该方案已经最优；轮数 r 也不等于目标值或最优代价。