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

mkdir 是 make directory 的缩写，用于创建目录。例如 mkdir work 会在当前目录下创建名为 work 的子目录。

题目给出的标准命令是 B；是否创建成功还取决于目标名称、目录权限等，但不影响这里的命令识别。

千位不能为 0，可从 1、2、3、4 中选择，共 4 种。

选定千位后，余下 4 个数字中依次选百位、十位、个位，有 $4\times3\times2=24$ 种。

总数为 $4\times24=96$，选 A。数字 0 可以出现在后三位，只是不能作最高位。

先代入稀疏条件 m 与 n 同阶。A 为 $O(n\sqrt{\log n\log\log n})$，D 为 $O(n\log n)$；B、C 的主项分别是平方级和平方除以对数，均更大。

比较 A 与 D，前者除以后者的增长项得到 $\sqrt{\log\log n/\log n}$，随 n 增大趋向 0。

因此 A 增长最慢，不能因其式子较复杂而误判更慢。

可按由底到顶放成四列：[1,3,6,10]、[2,7,9]、[4,5,11]、[8]，相邻和分别是 4、9、16 等完全平方数，所以 1 至 11 可放下。

再证明 12 不可能放下：1、2、4 都找不到更小的正整数与自己配成完全平方数，因此至少需要三根柱子作起点。3 和 8 都只有前驱 1，但同一个球上面只能直接放一个球，所以二者至少有一个必须另开一柱。

同理，5 和 12 都只有前驱 4，二者也至少有一个必须另开一柱。两组涉及不同球，因此至少需要 3+1+1=5 根柱子，超过四根的限制。

所以任何方案都无法放到 12，上限为 11，选 C。

哈夫曼树把较小权值反复合并，目的是使带权路径长度最小，常用于构造可变长前缀编码。

图的深度优先搜索则沿未访问顶点不断深入，通过递归或栈回溯，与“选择两个最小权值合并”的过程不同。因此 B 的用途描述不恰当。

把树的根染成颜色 1，深度为偶数和奇数的结点交替染两种颜色。树的每条边只连接父子，深度相差 1，所以不会冲突。

完全三叉树也属于树，必能两色染色，选 A。三角形同时是平面图、边双连通图和欧拉图，却有奇环，必须三色，能排除其余类别的必然性。

设 dp[i][j] 为前 i、j 个字符的 LCS 长度。末字符相同可用 dp[i−1][j−1]+1，否则取 dp[i−1][j] 与 dp[i][j−1] 的较大者。

对 X=ABCAAAABA 逐行计算，最终对 Y 各前缀的结果为 1,2,3,4,4,4,5,5,6，所以完整长度为 6。

例如 ABCABA 在 X 中可选位置 1,2,3,4,8,9，在 Y 中可选 1,2,5,7,8,9。它给出长度 6 的构造，而 DP 证明不能达到 7，选 C。

固定第一次点数 x。第二次只有一个点数会让收益清零，其余五个点数均保留 2x，因此条件期望为 $2x\times5/6$。

第一次的六种 x 等可能，平均点数为 $(1+2+3+4+5+6)/6=7/2$。

总体期望为 $2\times(7/2)\times(5/6)=35/6$ 元，选 B。

按优先级加括号，表达式为 (a&b) || ((c^b)&&(a|c))。

先算 5&3=1，左侧已经为真，|| 发生短路，右侧实际上无需执行，res 得到布尔值 true，选 A。

若仅作数值核对，右侧的位运算分别会得到 7 和 5，也都为真；但不能据此说实际程序一定求值了右侧。bool 的默认流输出可显示 1，本题按布尔字面值选择 true。

已排序且元素按通常不同值情形分析时，首元素是最小值或最大值。每次以它为基准，剩余非空子问题只有一个，规模为 n−1。

划分的总工作量为 $n+(n-1)+\cdots+1=\Theta(n^2)$，选 C。

只有划分近似平衡时才能得到通常的对数层数，本题没有随机选枢轴来避免退化。

g++ 后的 main.cpp 是输入源文件；-o 后紧随的 main 是输出文件名。参数 -o 可以放在源文件之前，只要它的参数对应正确即可。

因此 g++ -o main main.cpp 会生成名为 main 的可执行文件，选 A。把 main.cpp 放在 -o 后会错误地指定输出名。

树最多有两个重心；若有两个，它们相邻，删去连接边会把树分成大小相同的两半。

相同大小的两半要求总结点数为偶数，因此 7 个结点不可能有两个重心，必然唯一，选 C。

偶数结点不一定有两个，但偶数长度的链就有两个，足以否定其他选项中的“一定唯一”。

观察箭头，唯一有向环为 1→3→4→1；结点 2 只向外连接，5、6 方向形成向 6 汇入的支路，不会构成另一个回路。

删除 1→3、3→4、4→1 中任意一条，都能打破该环，使全图变成 DAG；删除环外边则仍保留这个环。

因此候选边恰有 3 条，选 C。

十六进制中 $16\equiv1\pmod{15}$，所以每次求数位和都保持模 15 的余数；反复求和最终得到 0 至 15 的一位数。

对正数而言，不动点为 9 等价于原数模 15 余 9。区间端点按题意为 $100_{16}=256$ 与 $1A0_{16}=416$。

区间内最小符合数为 264，最大为 414，相邻间隔 15，共 $(414-264)/15+1=11$ 个，选 B。

虽然每个递归参数都减半，但相同的 quick_power(x,n/2) 被调用两次，没有保存第一次的结果。

调用树每层结点数约翻倍，深度约为 $\log_2 n$，总调用数为 $1+2+4+\cdots+O(n)=O(n)$，选 A。

标准快速幂只计算一次半幂并复用，才会得到 $O(\log n)$。

按题目采用的 16 位 unsigned short 模型，设 x 最低的非零位在第 t 位。x<<6 在第 t 位仍为 0，因此第一步异或后第 t 位仍为 1，截断高位也不会消去它。

再对第一步结果取最高的非零位，第 8 位右移后的值在这个位置必为 0，所以第二步异或也不能清空最高非零位。

两步都把非零数映射为非零数，因此判断正确。

unsigned short 变量在每次复合赋值后按 16 位保存；换成 unsigned int，会保留第一步产生的更高位，这些位能在下一次右移时回到低 16 位。

取 x=1024：原程序第一步把 1024 xor 65536 截成 1024，第二步得到 1028。改为 unsigned int 参数后，第一步保留 66560，第二步为 66820，返回 unsigned short 时截成 1284。

1028 与 1284 不同，所以判断错误；截断发生在赋值/返回转换处，不是移位表达式本身自动使用 16 位运算。

65535 的低 16 位全为 1，左移 6 位后低 16 位为 1111111111000000。

两者异或再存回 unsigned short，只剩低 6 位为 1，即 63。63>>8=0，第二步异或不改变它。

因此输出 63，判断正确。

第一步为 1 xor (1<<6)=1 xor 64=65，保留了原来的最低位 1。

因为 65<256，右移 8 位为 0，第二步仍为 65。因此输出 65，不是 64，判断错误。

512 为 $2^9$，左移 6 位成为 $2^{15}=32768$，与原值没有重合的 1 位，异或结果为 33280。

再把 33280 右移 8 位得到 130；它与 33280 的 1 位也不重合，最终为 33280+130=33410，选 B。

题目只问执行第 5 行后，还没有执行右移异或。

64<<6=4096，两者分别只有第 6、12 位为 1，异或得到 4096+64=4160，选 D。

d 保存某个质数 i 的各次幂，倒序遍历让一个数先遇到它能整除的最大 i 的幂，之后 p[j] 被置 false，不再被较小幂覆盖。

取 n=4：正常顺序先处理 4，得到 g[4]=4，最后 f[4]=7；若不 reverse，先处理 2 就把 g[4] 固定为 2，随后算得 f[4]=f[2]×3=9。

于是第一行由 15 变为 17，输出改变，判断错误。

solve1 先为 i 找最小质因子 p 及其最大幂 q，再利用约数和的积性，计算 $\sigma(i)=\sigma(i/q)(1+p+\cdots+q)$。

solve2 中，每个正整数 d 是 1 至 n 中恰有 $\lfloor n/d\rfloor$ 个数的约数，因此累加 $d\lfloor n/d\rfloor$ 等于同一个约数和总和。

n=10 时贡献为 10,10,9,8,10,6,7,8,9,10，和为 87，两行相等，第一行并不更大，判断错误。

solve1 是逐个数求约数和后累加，solve2 是逐个约数求其出现次数后累加；两者只是交换了求和顺序。

具体恒等式为 $\sum_{x=1}^{1000}\sum_{d\mid x}d=\sum_{d=1}^{1000}d\lfloor1000/d\rfloor=823081$，所以两行相等，判断正确。

这里各项与总和都在相应整数类型的范围内，计算无需依赖浮点近似。

对于质数 p，筛它的各次幂所需枚举次数不超过 $n/p+n/p^2+\cdots=O(n/(p-1))$。

对所有相关质数累加，得到筛法量级 $\Theta(n\log\log n)$；另外生成幂、扫描剩余质数以及最后递推，都不超过这一主项。

因此选 D；即使某个数已被标记，循环仍会访问它，不能把总成本误判为线性。

solve2 只有一重循环，i 从 1 增至 n，恰好执行 n 次。

每轮的 n/i、乘法和累加均按常数时间整数运算处理，因此总复杂度为 $\Theta(n)$，选 B。

n=5 时，整数商 n/i 依次为 5、2、1、1、1。

每轮贡献为 1×5=5、2×2=4、3、4、5，累加 $5+4+3+4+5=21$，所以第二行输出 21，选 B。

设原答案为 v，即计数首次达到 k 的差值阈值。错误修改的是成功分支 h=m−1，不是中点计算公式。

若成功分支遇到 m>v，减 1 后仍有 h≥v；若恰遇到 m=v，才会把 v 排除，使 h=v−1。失败分支只把 g 移到不超过 v 的位置。

因此最终结果只能是 v 或 v−1。例 a=[0,2]、k=1 时仍输出 2；a=[0,1,3]、k=1 时由 1 变为 0，判断正确。

数组元素绝对值至多 $10^8$，故最大差值不超过 $2\times10^8$；二分始终有 $0\le g\le h\le2\times10^8$。

所以 h+g 至多 $4\times10^8$，在通常 32 位 int 内不会溢出。两式都计算非负区间的向下取整中点，因此输出不变，判断正确。

排序后为 [−4,−3,1,2,5]。按每个左端点列差值：从 −4 出发为 1,5,6,9；从 −3 出发为 4,5,8；从 1 出发为 1,4；从 2 出发为 3。

十个差值排序为 1,1,3,4,4,5,5,6,8,9，第 7 小为 5。f 二分的正是第 k 小差值，所以判断正确。

先排序需 $O(n\log n)$。二分的整数取值区间含 A 个值，需要 $O(\log A)$ 次判定。

f0 中 i、j 都只向右走，各最多移动 n 次，所以一次判定为 $O(n)$，不是平方级。

总开销为 $O(n\log n+n\log A)=O(n\log(nA))$，按题目最坏复杂度口径选 C；不能漏掉最开始的排序。

按题目的计数意图，原条件把窗口保持为差值≤m，改成 >= 后想保持差值<m。阈值相同而可计入的数对减少，因此若程序安全执行，新二分结果不会更小，给定答案为 B。

但原代码没有限制 j≤i。取 n=2、k=1、a=[0,1]，首次 m=0；修改后 i=0 时，a[0]−a[0]=0≥0，使 j 先增至 1，此时连数对计数 i−j 都变成了 −1；到 i=1 时，又因 a[1]−a[1]=0≥0 使 j 增至 2，下一次访问 a[2] 越界。

因此严格按完整 C++ 程序，题设不足以保证一个可比较的新输出。B 描述的是忽略这一缺陷后的单调计数结论，不能当作所有合法输入的运行保证。

开头 5、8 分别是 n、k，真正的五个元素为 2,−5,3,8,−12，排序得到 [−12,−5,2,3,8]。

按左端点列差值：7,14,15,20；7,8,13；1,6；5。排序为 1,5,6,7,7,8,13,14,15,20。

第 8 小为 14，选 B。不能把 n=5 或 k=8 再当成数组元素加入。

cand 排序后，每个候选顶点 u 对应一个连续的字典序分组，组内共有 f[u] 条后续路径。

若当前名次 k≤f[u]，目标就在这一组，返回 u；若 k>f[u]，跳过整组并减去 f[u]。因此①选 B。

这个判断是选择路径分组，并不表示路径会立即在 u 结束；是否结束还要看更新后的 k 是否等于 1。

deg[v] 是删除当前边之前的剩余入度。当前边是最后一条入边时，deg[v]=1，随后 --deg[v] 才会变成 0。

因此应在 deg[v]==1 时把 v 加入 Q，②选 A；若先判断等于 0，则错过刚好被释放的顶点。

从 u 出发的路径，要么只包含 u，要么先走到某个后继 v，再接一条从 v 出发的路径。各组按第一步分开，可以相加。

f[u]=1 已经计入单点路径，每条出边只需加 f[v]，不能再加 1。由于只查询不超过 LIM 的名次，超过 LIM 的数量统一截断即可。

因此③填 min(f[u]+f[v],LIM)，选 A。逆拓扑序保证每个 f[v] 已算好。

固定当前路径前缀后，立即结束的路径是最短前缀，排在所有继续延长的路径之前，组内名次为 1。

若 k=1，应停止；只有 k>1 时才需要再选择后继，因此④选 D。顶点有出边并不意味着目标路径必须继续走。

进入循环说明目标不是当前就结束的路径。该单条路径恰占一个名次，所以先执行 --k。

随后 next(E[u],k) 才是在各后继路径组中寻找新的第 k 小。若直接减 f[u]，会把目标所属的整个大组都跳过，因此⑤选 C。

pre 初始复制右半数组 a[mid…r−1]。从左到右处理时，pre[i−1] 已是前 i 项最大值，当前 pre[i] 仍为新元素。

把两者取最大，即 pre[i]=max(pre[i],pre[i−1])，就得到截至当前位置的前缀最大值，①选 D。

例如右半 [2,1,4] 处理成 [2,2,4]；pre 的局部下标不能直接当作原数组下标。

循环开始时，j 已是右侧第一个不小于此前左侧最大值的位置。向左加入新元素 a[i] 后，只有当它把左侧最大值提高时，分界才需要继续右移。

若 a[i] 不大于旧 max，a[j]≥旧 max≥a[i]，不会移动；若 a[i] 更大，就继续跳过 a[j]<a[i] 的元素，直至遇到新分界。

因此②填 a[j]<a[i]，选 B。max 在 while 后才更新，若比较旧 max 会漏掉新元素带来的扩展。

对一个固定左端点 i，右端点落在 [mid,j) 时，右侧最大值小于左侧 max，所以这些跨中点区间的最大值都等于 max。

右端点有 j−mid 个，贡献为 (long long)(j−mid)*max，③选 A。

左端点已经由外层循环逐个枚举，不能再乘一次左区间长度；先转 long long 是为了避免乘法溢出。