2026 CSP-J 第一轮试题题解

本题解依据用户提供的13页试卷PDF独立推导，并经程序核验，不作为官方标准答案。判断题中 A 表示正确，B 表示错误。

答案速查

题号	答案	分值
1—5	B D C C B	各2分
6—10	D D C B A
11—15	A D C A B
16—21	A B A A C C	1、1.5、1.5、3、3、3分
22—27	A B B B A C	1.5、1.5、1.5、3、3、3分
28—33	B A A B D C
34—38	D B D B C	各3分
39—43	A A A B A

一、单项选择题

1．B

long long 至少能表示 $-2^{63}$ 到 $2^{63}-1$，能精确保存 $10^{18}+1$。通常的32位 int 不够大。float 和 double 是浮点类型，虽然能表示这个数量级，却不能精确区分这一范围内所有相邻整数；“表示范围足够”和“整数值精确”是两回事。

2．D

先转为十进制：$2\times16^2+15\times16+5=757$。再连续除以8，余数依次为5、6、3、1，逆序得到八进制 $1365$。

也可以将十六进制写成二进制 $0010\ 1111\ 0101$，从右往左每三位分组，得到 $001\ 011\ 110\ 101$，对应 $1,3,6,5$。

3．C

两个操作数都是整数，$7/3=2$，$7\bmod3=1$。表达式为 $2\times3+1=7$。乘除同级，从左向右结合。

4．C

为了先弹出3，必须已经依次压入1、2、3。弹出3之后，栈顶是2，不能越过2先弹出1，所以 3,1,2,4 不可能出现。

A可以压入1、2后弹出2，再压入3、4并依次弹出4、3、1；B逐个压入并立即弹出；D先弹出1，再压入2、3、4并依次弹出4、3、2。

5．B

将完全二叉树按层序编号为1到100。结点 $i$ 有左孩子的条件是 $2i\le100$，所以1到50是非叶结点，51到100是叶结点，共50个。不能直接把最后一层结点数当作叶子总数。

6．D

程序累加100以内能被3或5整除的数。按容斥，结果为

$$3\frac{33\times34}{2}+5\frac{20\times21}{2}-15\frac{6\times7}{2}=1683+1050-315=2418.$$

15的倍数同时出现在前两项中，需要减去一次。

7．D

令 $f_i$ 为到第 $i$ 级的走法数。最后一步可能走1、2、3级，因此 $f_i=f_{i-1}+f_{i-2}+f_{i-3}$；令 $f_0=1$，负下标对应0种走法。

从0到8的数值依次为 $1,1,2,4,7,13,24,44,81$，答案为81。

8．C

按题目规定的方向顺序，并在入队时立即标记，入队序列是：

 1 (0,0)   2 (1,0)   3 (0,1)   4 (2,0)
 5 (1,1)   6 (0,2)   7 (2,1)   8 (1,2)
 9 (2,2)  10 (3,2)  11 (4,2)  12 (3,3)
13 (4,1)  14 (3,4)

E位于 $(3,4)$，是第14个入队的格子。这里数的是“已经入队过”，不是“已经出队过”，所以不能只数到E的路径上的格子。

9．B

由 $\gcd(n,60)=6$，令 $n=6t$，便得到 $1\le t\le16$ 且 $\gcd(t,10)=1$。也就是 $t$ 不能被2或5整除。

满足条件的 $t$ 为 $1,3,7,9,11,13$，对应 $n=6,18,42,54,66,78$，共6个。

10．A

$9=4+4+1$，所以3枚可以凑出。1枚不能凑出9；2枚硬币的可能总值为 $2,5,7,8,10,12$，也没有9，因此最少3枚。每次先拿最大面值的贪心会得到 $6+1+1+1$，不是最优。

11．A

p=a+2，所以 p[0] 是 a[2]=5，p[2] 是 a[4]=9。第一条赋值把 a[1] 改为14。

第二条赋值把 p[1]，也就是 a[3]，改为当前的 a[1]-a[0]=14-1=13。因此输出 14,13。必须按顺序使用已经更新的数组值。

12．D

二分每比较一次，就把仍需搜索的区间缩小到原来的一半左右。深度9最多容纳 $2^9-1=511$ 个中点，深度10可容纳 $2^{10}-1=1023$ 个中点，足以覆盖1000个元素。

因此最坏需要10次与数组中点元素的比较。这里按题意统计一次中点比较，不把程序内部的相等、大小条件分别当作新的访问次数。

13．C

由前缀和定义，$a[10]=s[10]-s[9]$。其中 $s[10]=310$，$s[9]=252$，所以 $a[10]=58$。

14．A

将最左与最右的点配对，再将次左与次右配对。对任意P，它到1、20的距离之和至少为19，到3、15至少为12，到4、10至少为6。

选P为中位数7，上述三个下界同时取得，且到7自身的距离为0，因此最小值为 $19+12+6=37$。

15．B

无向图的所有顶点度数之和等于边数的两倍。度数之和为 $4\times3+6\times4=36$，所以边数为18。

二、阅读程序

阅读（一）：二进制位数与1的个数

循环每次将 $n$ 整除2，相当于删去当前二进制表示的最低位。无论最低位是0还是1，x 都增加1；只有最低位是1时，y 才增加1。

因此，原输入大于0时，x 等于二进制位数加1，y 等于二进制中1的个数加1。输入为0时循环不执行，输出 1 1。时间为 $O(\log(n+1))$，额外空间为 $O(1)$。

16．A（正确）。 $3=(11)_2$，位数与1的个数都是2，因此输出 3 3。

17．B（错误）。 删除奇数分支的 ++x 后，x 只统计0位，y 统计1位，两者不一定相等。输入1就是反例，修改后输出 1 2。

18．A（正确）。 二进制中1的个数不超过总位数，所以 $x\ge y$；输入0时二者相等。

19．A。 非负整数反复整除2最终到0；条件改为 n>=0 后，0仍满足循环条件，且下一次仍为0，循环无法结束。

20．C。 $6=(110)_2$，共有3位、2个1，所以输出 4 3。

21．C。 第二个数为2，等价于二进制中恰有一个1，即输入为 $2^0,2^1,\ldots,2^{30}$。共有31个；0的输出第二项为1，不计入。

阅读（二）：保留最高位0的高精度加法

程序将两个十进制数倒序存入数组：下标0表示个位。全局数组的其他位置初始为0。每位计算两个数字加上低位进位，满10时向高位进1并减10。

设两个输入字符串的最大长度为 $L$，程序从下标 $L$ 输出到0，共输出 $L+1$ 个数位。它没有删掉最高位多余的0，所以输出可能有前导零。时间为 $O(L)$；按使用的有效位数计空间为 $O(L)$，原代码实际预留了固定长度数组。

22．A（正确）。 $123+456=579$，但程序固定输出4位，结果是 0579。

23．B（错误）。 123 456 本身不含前导零，输出仍为 0579，已构成反例。

24．B（错误）。 删除进位后并不保证结果严格变小。对于完全没有进位的 123 456，两份程序都输出 0579。

25．B。 $12345+678=13023$，最大输入长度为5，程序输出6位，即 013023。

26．A。 条件改为严格大于10后，个位的 $5+5=10$ 不再进位，十位的 $9+1=10$ 也不再进位。最高额外位为0。cout 按顺序输出整数0、10、10，拼成字符串 01010。

27．C。 最大输入长度为 $n$，所以固定输出 $n+1$ 位。又因为和小于 $10^n$，下标 $n$ 的最高位为0，输出以字符 '0' 开头。

阅读（三）：逐位扩展的质数搜索

check_prime 使用试除法判断质数。search_result(x) 先判断当前数是否为质数；若不是就停止该分支。若它已经达到 $n$，立即输出且不再扩展；否则按照0到9的顺序在末尾添加一位并递归。

每个被输出的数，以及它去掉若干末位后得到的每个非空十进制前缀，都必须是质数。搜索顺序是深度优先顺序，不是数值大小顺序。

28．B（错误）。 输入10时输出

23 29 31 37 53 59 71 73 79

上述每个数各占一行，共9行。

29．A（正确）。 主函数一定调用 search_result(5)。5是质数，且当 $n\le5$ 时满足 $5\ge n$，因此会输出5。

30．A（正确）。 递归扩展形成的数都至少是两位数。末位是偶数时，这个数是大于2的偶数，不可能是质数。因此不必尝试末位0、2、4、6、8，去掉这些立即失败的分支不改变输出和顺序。

31．B。 输入24时，先沿前缀2进入23。23还没达到24，于是继续输出233、239；回到前缀2后才输出29，所以第3行是29。

32．D。 被输出的两位及以上的数来自某个已经通过质数判断的父结点；删掉末位正好得到父结点，所以它一定是质数。

A的反例是输入24时先输出233，再输出239、29，不是递增顺序。B的反例是输入从10增大到24，输出行数从9增加到10。C也不成立，例如输入10时输出29，个位是9；输入不大于2时还会输出2。

33．C。 输入200时输出如下14个数：

233 239 293 311 313 317 373
379 593 599 719 733 739 797

同样每个数各占一行，所以答案为14。

三、完善程序

完善（一）：进制减半

读入 $mn$ 进制数的一个新数位 $x$ 后，已经读入的数值应从 $V$ 更新为 $Vmn+x$。数组 b 用小端方式保存 $n$ 进制数，即 b[0] 表示个位。

把每个旧数位乘 $m$ 并向高位移动一格，整体正好乘以 $mn$；再把最低位设为新读入的 $x$，最后按 $n$ 进制逐位进位，就完成这一更新。

34．D：b[j - 1] * m。 原下标 $j-1$ 的项移动到下标 $j$，相当于乘 $n$，再乘 $m$。循环从高位向低位写入，避免覆盖尚未使用的旧数位。

35．B：x。 移位后最低位空出，放入新读入的数位。虽然 $x$ 可以大于等于 $n$，后面的进位会将它规范为合法的 $n$ 进制表示。

36．D：b[j] / n。 第 $j$ 位每凑满 $n$ 就向第 $j+1$ 位进1，因此向高位增加整数商。必须是 +=，因为高位可能已有移位得到的值。

37．B：b[j] % n。 当前位留下除以 $n$ 的余数，范围为0到 $n-1$。

38．C：len > 1 && b[len - 1] == 0。 删除的是最高位多余的0。数值为0时仍应保留一位0，所以不能一直删到长度为0，也不能根据最低位是否为0来删最高位。

归纳看，每处理一个输入数位，进位后的数组都准确表示已读前缀的数值。处理完所有数位并删除冗余最高位0后，从高位到低位输出，就是所求结果。设过程中最多使用 $L$ 个数位，时间为 $O(dL)$，有效数位空间为 $O(L)$；原程序使用固定长度数组预留空间。

进制减半补全程序

#include <iostream>

constexpr int N = 100005;
long long b[N];

int main() {
    long long n, m, d;
    std::cin >> n >> m >> d;
    int len = 1;
    for (int i = 0; i < d; i++) {
        long long x;
        std::cin >> x;
        for (int j = len; j >= 1; j--)
            b[j] = b[j - 1] * m;
        b[0] = x;
        len++;
        for (int j = 0; j < len; j++)
            if (b[j] >= n) {
                b[j + 1] += b[j] / n;
                b[j] = b[j] % n;
                if (j + 1 == len) len++;
            }
    }
    while (len > 1 && b[len - 1] == 0) len--;
    for (int i = len - 1; i >= 0; i--)
        std::cout << b[i] << ' ';
    return 0;
}

完善（二）：平衡分割

字符串中的每个字符单独表示一个0到15的整数，不能把整个字符串当成一个十六进制整数。程序要将数列分成至少两段，比较各段平均值的最大值与最小值之差，并在所有连续划分中取最小。

递归状态 split(l, cnt, minb, maxb) 中，l 是还未划分部分的起点，minb、maxb 是已选各段平均值的最小值和最大值。主函数从 cnt=-1 开始，每选一段加1，因此完成划分时，cnt 等于段数减1，也就是切分位置的数量。cnt==0 对应整串不切分，必须排除。

39．A：c <= '9' ? c - '0' : c - 'A' + 10。 合法字符只可能是 '0'～'9' 或 'A'～'F'。数字字符减去 '0' 得到0到9；字母减去 'A' 得到0到5，还要加10。例如 'A' 应转换成10，'F' 应转换成15。其他选项会使数字或字母的数值错位。

40．A：int r = l; r <= n; r++。 当前段从 l 开始，右端点必须从 l 枚举到 n，既允许单元素段，也允许本段一直延伸到串尾。B漏掉末尾位置；C可能枚举出右端点小于左端点的情况；D按给定文本缺少 for 所需的第二个分号，而且不能正确枚举右端点。

41．A：get_val(s[r])。 每次将右端点向右扩展一位，需要把新加入的第 r 个字符对应的数值加入段和。字符串从 s[1] 开始存放，所以不能取 s[r-1]；直接累加 s[r] 得到的是字符编码，也不是它表示的十六进制数位值。

42．B：1.0*sum/(r-l+1)。 闭区间 [l,r] 有 r-l+1 个数，段平均值等于段和除以段长。先乘 1.0，可使后面的除法按浮点数计算。A会先执行整数除法再转成 double；C在单元素段上除以0；D错误地除以整个字符串长度。

43．A：r+1, cnt+1, min(minb,nwb), max(maxb,nwb)。 当前段已经覆盖到 r，下一段从 r+1 开始。每确定一段，计数加1，并将本段平均值 nwb 纳入已有的最小值和最大值。B、D没有向下一位置推进，C则丢掉历史极值且没有正确更新段数。

每个合法连续划分都有唯一的右端点序列，递归恰好沿这串右端点枚举到它；反过来，每条走到 l>n 的递归路径都按顺序覆盖整个字符串，各段非空。排除不切分的情况后，枚举的正好是题目允许的所有方案。在每个完整方案处计算 maxb-minb，再取最小值，就得到答案。

有 $n-1$ 个相邻位置，每个位置选择切或不切，因此共有 $2^{n-1}$ 种连续划分，排除完全不切的一个。程序在枚举右端点时增量维护段和，每条搜索树边只做常数工作；含中间状态在内，递归树共有 $2^n$ 个结点，故时间为 $O(2^n)$，递归栈空间为 $O(n)$，适用于 $n\le20$。

平衡分割补全程序

#include <algorithm>
#include <iomanip>
#include <iostream>

using namespace std;

constexpr int N = 25;
int n;
char s[N];
double ans = 1e100;

int get_val(char c) { return c <= '9' ? c - '0' : c - 'A' + 10; }

void split(int l, int cnt, double minb, double maxb) {
    if (l > n) {
        if (cnt == 0) return;
        ans = min(ans, maxb - minb);
        return;
    }
    int sum = 0;
    for (int r = l; r <= n; r++) {
        sum += get_val(s[r]);
        double nwb = 1.0*sum/(r-l+1);
        split(r+1, cnt+1, min(minb,nwb), max(maxb,nwb));
    }
}

int main() {
    cin >> n >> s + 1;
    split(1, -1, 1e100, -1e100);
    cout << fixed << setprecision(6) << ans;
    return 0;
}

难度与 CSP 风格适配度

本卷按 Hydro 整数难度3（普及）归档，属于本地教学估计，不是官方难度或得分预测。单选主要考查基础语义、树图性质和短计算；阅读部分重在输出长度、边界改动、DFS顺序；两道完善涉及数位表示不变量和连续分段枚举。

参照对象为 CSP-J 第一轮整卷，按原卷逐题计分，满分100分。程序骨架已给出，考查重点是阅读、推演及选取正确表达式，不能直接按第二轮独立编程题的题位套用评分。难度判断置信度中等，未使用选手作答统计校准通过率。