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

cd 表示 change directory，执行 cd work 后，当前工作目录切换到 work，后续相对路径也从新目录解释。

ls 只列出内容，cp 用于复制；要改变当前工作目录应选 B。

秒表从程序启动计时到程序结束，测的是经过的实际时间，对应 real=30.721 秒，最接近 30 秒，选 A。

user=24.579 秒是用户态 CPU 时间，sys=6.123 秒是内核态 CPU 时间；它们不包含所有等待时间，不能用其中一项代替秒表读数。

若要输出序列 afedcb，先把 a 入栈并立即弹出；随后要让 f 成为栈顶，必须依次压入 b、c、d、e、f。

此时待输入元素已耗尽，要依次输出 f,e,d,c,b，只能连续出栈 5 次，中间再无新元素可入栈打断，违反不能连续三次退栈。

因此 D 不可能；这并非普通栈序本身非法，而是额外操作限制排除了它。

归并排序把数据反复二分，共有约 $\log_2 n$ 层；同一层的合并区间互不重叠，处理总量为 n。

所以最坏时间为 $O(n\log n)$，比平方级低，选 C。插入、冒泡以及未加保护的快速排序，都存在 $\Theta(n^2)$ 的输入。

基数排序的每一趟按当前位进行稳定分配：若两个未受影响元素的当前位相同，仍保持上一趟的相对次序。

异常元素即使改变数值和所处桶，也不会改变其他两个正常元素的数位比较结果。忽略它之后，各趟对正常元素仍组成同样的稳定排序过程。

因此移除这一个异常元素后，其余数据仍有序，最坏也只会有它自身的位置不正确，选 A。

将 0xDEADBEEF 按字节分为 DE、AD、BE、EF。p 指向变量首地址，即最低内存地址，并且只读取一个字节。

小端的地址从低到高存 EF、BE、AD、DE，故读到 EF；大端存 DE、AD、BE、EF，故读到 DE。

%X 用十六进制输出该字节，因此分别为 EF、DE，选 B。

按完整各层的三叉树模型，高为 4 的子树含 $1+3+9+27=40$ 个结点。根编号 1，三棵子树的前序编号段分别为 2…41、42…81、82…121。

100 落在以 82 为根的第三棵子树，其中每个孩子子树有 13 个结点，编号段为 83…95、96…108、109…121。

再进入根 96 的子树，其第一个孩子编号 97，紧随其后的三个叶子为 98、99、100。故父结点为 97，选 C。

这里沿用答案把“完全3叉树”理解为各层全满的模型；若按末层可不满、从左向右填充的通常完全树定义，仅给深度无法唯一确定。例如 101 个结点的完全三叉树，前序第 100 个结点的父编号为 98。应区分原题的术语口径与一般定义。

强连通要求任意两点 u、v 都有 u 到 v 以及 v 到 u 的有向路径，不要求路径长度为 1。

例如有向环 1→2→3→4→1 是强连通图，但 1 和 3 之间没有直接边。它足以否定 B。

其余关于相邻边的描述按本题通常的非单点图口径理解，核心区别是“路径”与“直接边”。

每点度数为 2 的简单无向图由若干个环组成。若要有遍历所有边的欧拉回路，这些环不能分属不同连通分量，所以必须是经过全部 n 点的一个环。

固定顶点 1 作为书写起点，剩余顶点有 $(n-1)!$ 种排列；把顺时针与逆时针视作同一个无向环，再除以 2。

因此在通常 n≥3 的环模型下，方案数为 $(n-1)!/2$，选 D。

按选项所考查的“一支两人团队”计数，从 8 人中先选第一人有 8 种，再选另一人有 7 种。

同一对成员交换选择顺序仍是同一支队伍，故除以 2，得到 $\binom{8}{2}=28$，选 A。

若问题改成把全部 8 人同时分成 4 支无标号队伍，则会是 105 种；那是不同的计数任务。

固定的“省 A·”不产生选择。后面两位字母各可选 A 至 Z 共 26 种，三位数字各可选 0 至 9 共 10 种。

不同位置独立且允许重复，由乘法原理得到 $26^2\times10^3=676000$，选 C。数字部分是编号，不受三位整数首位不能为 0 的限制。

逐项插入：71→1，23→3；73 初始位置 3 已占，顺延到 4；99→9；44 的位置 4 已占，顺延到 5；79 从 9 回绕到空位 0。

最后插入 89 时，从余数位置 9 开始，9、0、1 都已占用，位置 2 为空，因此落在 2，选 D。

原 PDF 的内层更新语句是 j*=2，但初值仍写为 j=0。n>0 时，0 每次乘 2 仍为 0，j<n 永远成立；该原卷代码不能作为一个正常结束的排序或计数循环分析。

给定答案 B 对应的是把初值改为 1 后的命题意图：内层依次取 1,2,4,…，执行 $O(\log n)$ 次，外层 n 次，得到 $O(n\log n)$。

本题保留原卷及其答案，同时明确区分：B 是勘误后的复杂度，不是原样程序的时间复杂度；也不能用一次运行假定它会在整数溢出后正常结束。

每个不是最大值的元素，至少要在一次比较中输给别的元素，才能确定排除它。共有 n−1 个这样的元素，而一次比较最多新增一个被排除者。

所以至少要比较 n−1 次；从第一个元素作候选，依次与其他元素比较，恰能达到该下界。因此选 B。

当 m=1 时，ack(1,0)=ack(0,1)=2；每增加一次 n，调用 ack(0,…) 把结果加 1，所以 ack(1,n)=n+2。

于是 ack(2,0)=ack(1,1)=3，ack(2,1)=ack(1,3)=5，ack(2,2)=ack(1,5)=7。

因此选 B；第三个分支必须先算内层，再把结果作为外层第二个参数。

输入运算符把空格两侧分别读入 s=abcde、t=fg，模式长度 m=2。shift 中 f 为 2、g 为 1，其他字符默认 3。

候选起点 i=0 时首字符失配，窗口后字符 c 的位移为 3，于是跳到 i=3；这里 d 与 f 仍不等，再跳出合法起点范围。

没有完整匹配，返回 −1，判断正确。

主串 abbababbbab 的零基下标 3、4、5、6 依次为 a、b、a、b，组成第一次出现的 abab。

程序返回起点下标 i，而不是从 1 开始数的字符位置，因此输出 3。题目说输出 4，判断错误。

模式“22”长度为 2，字符 2 最后一次出现于下标 1，因此 shift[2]=1；其他字符的默认位移为 3。

实际候选起点依次为 0、3、6、9、12。前四次首字符就失配，不执行 j++；i=12 时末尾两个 2 都匹配，使 j 从 0 增至 2。

因此 j++ 总计 2 次，判断正确。

每次尝试匹配，while 最多成功或检查约 m 个字符。跳转表虽能跳过一些起点，但最坏仍有与 n 同阶的候选窗口。

例如主串全为 a，模式为若干个 a 后接 b，每次先比较长 a 前缀再失败，窗口后字符 a 只让起点移动 2 位。

当 n 远大于 m 时，需要 $\Theta(n)$ 个窗口，每个 $\Theta(m)$ 次工作，最坏为 $O(nm)$，选 D。

函数依次检查可能的匹配起点，首次完整匹配就 return i；若全部失败，则返回 −1。

a.find(b) 同样返回 b 在 a 中第一次出现的位置，因此功能最接近 A。严格说 find 的未找到标记是 string::npos，而此函数用 int 的 −1；题目比较的是查找功能。

模式 aaaa 的 shift[a]=1；其他字符默认跳 5。程序只尝试起点 0、5、6、7、8、13，不会逐个起点检查。

这些窗口分别成功匹配 0、3、2、1、0、4 个字符；每成功一个字符才执行一次 j++，失败的那次比较不计。

合计 $0+3+2+1+0+4=10$，选 B。

每一趟利用计数前缀和确定数位相同元素的区间，再从原数组末尾向前放置，放一个就把该桶的末位置减一。

若同位的两个元素 u 原本在 v 前面，则 v 先放到较后位置，u 后放到较前位置，相对顺序保持不变。

所以单趟计数排序稳定，各趟组成的基数排序也稳定，“不稳定”这一断言错误。此处按算法所需的非负键值与不溢出前提分析。

一趟排序至少需要 n 个位置保存 temp，此外还要有 k 个桶来统计每个数位出现次数。

按随输入规模分配空间的算法模型，额外空间为 $O(n+k)$，会受到基数 k 的影响，所以断言错误。原代码用固定 MAXN 数组实现，不应把固定容量写法当成可扩展算法的空间结论。

一趟包括清空 k 个桶、统计 n 个元素、累加 k 个桶的前缀和、回填 n 个元素及复制 n 个元素，总量为 $O(n+k)$。

这样的过程执行 m 次，对应最大数的 k 进制位数，因此排序阶段为 $O(m(n+k))$，判断正确；这里采用桶下标有效且整数计算不溢出的正常排序前提。

第一趟 base=1，数位取 val[j]%3。98、26 的余数为 2，91、37、46 的余数为 1，没有余数 0 的数。

稳定计数排序把余数 1 的组先放，组内保持 91,37,46；余数 2 的组保持 98,26。

第一次执行到第 36 行时已经复制回 val，得到 91 37 46 98 26，选 D。

给定答案 C 对应比较趟数：最大值 100 分别需要 7 位二进制、5 位三进制、3 位十进制，因此 k=10 的趟数最少。

但题干问完整“运算次数”，每趟还要处理 k 个桶，不能只数趟数。按代码各循环体执行次数粗计，每趟为 k+n+(k−1)+n+n=3n+2k−1。

例如 n=1 时，k=2、3、10 分别得到 42、40、66 次这一口径下的循环体执行量，10 并非最少。因此缺少 n 与具体成本口径时，不能严格证明 C 为唯一最优；此处保留原答案并说明其简化假设。

当所有非负键值都小于 k 时，init 中 maximum>=k 一开始为假，所以 m=1。

唯一的一趟中 base=1，val[j]/base%k 等于 val[j] 本身，计数桶直接按完整数值统计，再按前缀和回填。

这正是计数排序，选 C，无需再处理高位。

每轮选取余数 r∈[0,k−1]，并更新商 $q=(r-n)/k$，保持 $n=(-k)q+r$。

于是商的绝对值满足 $|q|\le |n|/k+1$，经过与对数同阶的次数就降至常数范围，算法生成一位后再处理余下商。

按非零 n 的通常规模写法，时间为 $O(\log_k|n|+1)$，题目意指对数量级，判断正确；负数不能直接写实数对数 $\log_k n$。

即使加上字符常量，ans[i]+'0' 和 ans[i]+'A'−10 的算术结果也是整数。char(...) 把它转回字符，使 cout 输出字形。

例如输入 1 2 时，有转换输出字符“1”；删除转换则输出字符编码的十进制值 49。因此程序行为改变，判断错误。

每轮写入一个负 k 进制数位，最终 m 就是位数，倒序循环每次输出一个字符。

商的绝对值大致每轮缩小 k 倍，所以位数为 $O(\log_k|n|+1)$，判断正确。

末尾的加 1 覆盖 n=1 等对数为 0 的小规模情形；n=0 则由单独分支输出一个 0。

当前 n=100 时，规范余数为 2，新的 n=(2−100)/7=−14。

n=−14 时余数为 0，新的 n=2；再取余数 2，新的 n=0，结束。

得到低位到高位 [2,0,2]，倒序输出 202，且 $2(-7)^2+2=100$，选 A。

逐轮规范余数与新商为：−255→余数 1、商 32；32→余数 0、商 −4；−4→余数 4、商 1；1→余数 1、商 0。

低位到高位为 [1,0,4,1]，倒序得到 1401。

验证 $1(-8)^3+4(-8)^2+1=-512+256+1=-255$，选 B。

每轮的“当前 n→数位、新商”为：1000000→11,−52631；−52631→18,2771；2771→16,−145；−145→7,8；8→8,0。

数位 11、18、16 分别编码为 B、I、G，低位到高位为 B,I,G,7,8，倒序输出 87GIB，选 B。

代回负十九进制位权，$8\times19^4-7\times19^3+16\times19^2-18\times19+11=1000000$，与输入一致。

若 a1[m1]≤a2[m2]，严格小于 a1[m1] 的元素至多来自第一数组前 m1 项和第二数组前 m2 项，总数至多为 m1+m2。若这个和小于 k，则 a1[m1] 不会大于合并后的第 k 小值，可以把第一侧这个中点及以前的元素纳入左前缀。

反之，若 m1+m2≥k，则 a2[m2] 前面已有足够多的不大于它的候选，可以缩小第二侧右边界。另一分支完全对称，因此①采用零基下标和 m1+m2，选 C。这里比较的是分割位置，不应直接替换成两个前缀长度之和。

需同时注意原卷的边界缺陷：例如 n=1、k=1、a1=[1]、a2=[2]，循环后 left1=1，收尾访问 a2[k−left1−1]=a2[−1]。本题答案体现原卷分割意图，不能据此断言代码对所有输入都安全。

②为真时，cnt<k 会向右移动 left1；否则向左移动 right2。因此这一分支应对应 a1 的中点不大于 a2 的中点。

填 a1[m1]<=a2[m2] 后，两支恰好按较小/较大中点作对称处理，选 B；只比较相等或不等不能确定该移动哪一侧。

整体代码的空前缀访问风险见第 34、37 题，局部比较方向正确并不能消除它。

循环前提是两边候选区间都非空。对包含端点的闭区间 [left1,right1]，只有 left1>right1 才表示它已经为空。

因此③选 C，用来区分哪侧搜索先结束。left1==right1 时还剩一个候选元素，不应判为空。

按分割的计数意图，第一侧前缀已有 left1 个元素，第二侧应补 k−left1 个。第二侧最后一个元素的零基下标为 k−left1−1，所以④选 C。

若两侧前缀都非空，取 a1[left1−1] 与 a2[k−left1−1] 的较大值，就是合并前缀的末项。

但是 k−left1=0 时第二侧为空，这个下标为 −1；原代码只检查 left1==0，没有检查这一对称边界。因此该表达式有边界前提，不能直接作为可复用的完整第 k 小模板。

这一分支与上一分支对称：第二侧前缀有 left2 个元素，第一侧需要 k−left2 个，对应末元素下标 k−left2−1。

因此⑤填 y=a1[k−left2−1]，选 A，再与 a2[left2−1] 取最大值。

同样必须警惕 k−left2=0 时的空前缀；原卷未提供该边界保护，解析说明的是选项的分割含义。

当前容器水量为 (x,y)，向容量 a 的容器 1 倒水，最多还能装 a−x，同时容器 2 只有 y 升可倒，因此 t=min(a−x,y)。

新状态为 (x+t,y−t)，当前倒水消耗一步，所以①填 dfs(x+t,y−t)+1，选 A。

例如 a=5、x=2、y=4 时 t=3，新状态为 (5,1)，不能把目标容器装到超过容量。

向容器 2 倒水时，可倒量同时受容器 1 的现存水量 x 和容器 2 的剩余容量 b−y 限制，故 t=min(x,b−y)。

倒完后容器 1 减少 t、容器 2 增加 t，新状态 (x−t,y+t)，再加这一步操作，②选 C。

题目只要求任意一个容器中恰好有 c 升。到达 x=c 或 y=c 时已经成功，后面不需要继续输出操作。

所以③填 x==c || y==c，选 A。&& 会错误地要求两容器同时达到 c，>= 则会把多于 c 的水也当作完成。

还原路径时，若记录的当前代价恰等于后继代价加 1，就可以输出这次操作并递归到后继。

本分支打印 POUR(2,1)，后继明确为 (x+t,y−t)，所以④必须与 dfs 中相应转移一致，填 dfs(x+t,y−t)+1，选 A。

这个等式解释的是路径还原规则；对于带环状态图，不能仅凭使用了记忆化 DFS 就一般性保证所有 f 值均为最短距离。

最后一个分支对应 POUR(1,2)，后继为 (x−t,y+t)，故需比较 f[x][y] 与 dfs(x−t,y+t)+1，⑤选 C。

选择后就按代码进入该后继，每次把剩余操作数减一；方向和加一成本都必须与搜索转移保持一致。

若用它实现独立的最少步数求解，应另外证明带环图上的距离计算正确，通常可用 BFS 作可靠对照。