2026 CSP-J 初赛题解

本题解对应本题题面整理。判断题使用 √ / × 表示。若后续官方答案与当前版本存在差异，以官方最终公布为准。

使用说明

建议先独立完成整套试卷，再查看答案速查。错题不要只记选项，重点看“为什么其他选项不对”和程序执行过程。

答案速查

一、单项选择题

题号	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
答案	B	D	C		B	D		C	B	A		D	C	A	B

二、阅读程序

题号	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33
答案	√	×	√	A	C		√	×		B	A	C	×	√		B	D	C

三、完善程序

题号	34	35	36	37	38	39	40	41	42	43
答案	D	B	D	B	C	B	D	C	A	D

---

一、单项选择题解析

第 1 题：精确存储整数的数据类型

答案：B，long long。

题目要求精确存储

$$10^{18}+1=1000000000000000001.$$

常见的有符号 64 位 long long 上限为

$$2^{63}-1=9223372036854775807,$$

能够存下该整数。32 位 int 的范围明显不足。

float 和 double 虽然数值范围很大，但有效精度有限。常见 double 只有 53 位二进制有效精度，在 $10^{18}$ 附近无法保证每一个整数都能被精确表示；float 精度更低。

易错点： 数值范围足够，不等于能精确表示范围内的每一个整数。

---

第 2 题：十六进制转八进制

答案：D，1365。

先把每一位十六进制数改写为 4 位二进制：

$$(2F5)_{16}=(0010\ 1111\ 0101)_2.$$

从右向左每 3 位分组：

001 011 110 101
 1   3   6   5

因此：

$$(2F5)_{16}=(1365)_8.$$

也可以用十进制校验：

$$2\times256+15\times16+5=757,$$ $$1\times512+3\times64+6\times8+5=757.$$

---

第 3 题：整数除法与取余

答案：C，7。

a、b 都是整数，因此：

7 / 3 = 2
7 % 3 = 1

乘除取模优先级高于加法，且同级运算从左到右：

a / b * b + a % b
= 2 * 3 + 1
= 7

本质上利用了整数除法恒等式：

$$a=(a/b)\times b+a\%b.$$

---

第 4 题：栈的合法出栈序列

答案：C，3, 1, 2, 4 不可能出现。

若第一个要弹出 3，则必须先依次将 1、2、3 入栈。弹出 3 后，栈顶是 2，下面才是 1，所以接下来只能先弹出 2，不可能先弹出 1。

其余序列可以构造：

• A：压入 1、2，弹出 2；再压入 3、4，依次弹出 4、3、1。
• B：每压入一个数就立即弹出。
• D：先弹出 1，再压入 2、3、4，依次弹出 4、3、2。

易错点： 栈只能访问栈顶，不能从中间取元素。

---

第 5 题：完全二叉树的叶子数量

答案：B，50。

完全二叉树按层序从 1 到 100 编号。编号为 $i$ 的结点若存在左孩子，则左孩子编号为 $2i$。

有孩子的条件：

$$2i\le100\Rightarrow i\le50.$$

因此 1～50 为非叶结点，51～100 为叶结点，共：

$$100-50=50.$$

一般地，含 $n$ 个结点的完全二叉树有 $\lfloor n/2\rfloor$ 个非叶结点。

---

第 6 题：3 或 5 的倍数之和

答案：D，2418。

代码统计 1～100 中能被 3 或 5 整除的整数之和，需要用容斥避免 15 的倍数重复计算。

3 的倍数之和：

$$S_3=3(1+2+\cdots+33)=1683.$$

5 的倍数之和：

$$S_5=5(1+2+\cdots+20)=1050.$$

15 的倍数之和：

$$S_{15}=15(1+2+\cdots+6)=315.$$

所以：

$$1683+1050-315=2418.$$

易错点： || 表示“或”，15 的倍数同时满足两个条件，但循环中只加一次。

---

第 7 题：每次走 1、2、3 级楼梯的计数

答案：D，81。

设 $f(i)$ 表示走到第 $i$ 级的方案数。最后一步只能从 $i-1$、$i-2$ 或 $i-3$ 级走来：

$$f(i)=f(i-1)+f(i-2)+f(i-3).$$

初值：

$$f(0)=1,\quad f(1)=1,\quad f(2)=2.$$

依次得到：

$i$	0	1	2	3	4	5	6	7	8
$f(i)$	1		2	4	7	13	24	44	81

因此答案为 81。

---

第 8 题：BFS 入队顺序

答案：C，14。

坐标采用 (行, 列)，S=(0,0)，E=(3,4)。按照“上、下、左、右”的顺序扩展，并在入队时立即标记访问。

关键入队过程如下：

本次出队	新入队格子	累计入队数
初始	(0,0)	1
(0,0)	(1,0), (0,1)	3
(1,0)	(2,0), (1,1)	5
(0,1)	(0,2)	6
(2,0)	(2,1)	7
(1,1)	(1,2)	8
(0,2)	无
(2,1)	(2,2)	9
(1,2)	无
(2,2)	(3,2)	10
(3,2)	(4,2), (3,3)	12
(4,2)	(4,1)	13
(3,3)	(3,4)=E	14

当 E 第一次入队时，累计入队 14 个格子。

易错点： 题目问的是累计入队数量，不是最短路长度，也不是当前队列长度。

---

第 9 题：最大公约数条件计数

答案：B，6。

由 $\gcd(n,60)=6$，可令：

$$n=6k.$$

于是：

$$\gcd(6k,60)=6\gcd(k,10)=6,$$

所以要求：

$$\gcd(k,10)=1.$$

又因为 $1\le n\le100$，故 $1\le k\le16$。

在 1～16 中既不是 2 的倍数，也不是 5 的倍数的数为：

1, 3, 7, 9, 11, 13

共 6 个。

---

第 10 题：最少硬币数

答案：A，3。

可以用：

$$4+4+1=9,$$

所以 3 枚可以做到。

再检查两枚是否可能。两枚硬币的可能和为：

2, 5, 7, 8, 10, 12

没有 9，因此至少 3 枚。

易错点： 直接贪心先取最大面值会得到 $6+1+1+1$ 共 4 枚，并非最优。

---

第 11 题：指针偏移与数组修改

答案：A，14,13。

p = a + 2，所以 p 指向 a[2]。

对应关系：

*(p - 1) = a[1]
p[0]     = a[2]
p[2]     = a[4]
p[1]     = a[3]

第一条赋值：

*(p - 1) = p[0] + p[2];

即：

a[1] = a[2] + a[4] = 5 + 9 = 14

第二条赋值：

p[1] = *(a + 1) - a[0];

此时 *(a+1) 已是修改后的 a[1]=14：

a[3] = 14 - 1 = 13

因此输出 14,13。

---

第 12 题：二分查找最坏比较次数

答案：D，10。

每比较一次，待查区间大约缩小一半：

1000 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1 → 0

最坏需要 10 次与数组元素比较。

也可用：

$$\lfloor\log_2 1000\rfloor+1=9+1=10.$$

---

第 13 题：由前缀和还原数组元素

答案：C，58。

由前缀和定义：

$$a[i]=s[i]-s[i-1].$$

因此：

$$a[10]=(3\times10^2+10)-(3\times9^2+9)=310-252=58.$$

也可以先化简：

$$a[i]=(3i^2+i)-\bigl(3(i-1)^2+i-1\bigr)=6i-2,$$

代入 $i=10$ 得 58。

---

第 14 题：绝对距离之和最小

答案：A，37。

数轴上到多个点的绝对距离之和，在中位数处取得最小值。

7 个点已经有序：

1, 3, 4, 7, 10, 15, 20

中位数是 7，取 $P=7$：

$$6+4+3+0+3+8+13=37.$$

---

第 15 题：无向图的度数和

答案：B，18。

所有顶点度数之和：

$$4\times3+(10-4)\times4=12+24=36.$$

无向图中每条边会对两个顶点各贡献 1 个度，因此：

$$|E|=36/2=18.$$

易错点： 度数和不是边数，要再除以 2。

---

二、阅读程序解析

程序（1）：二进制位数与 1 的个数

核心循环：

int x = 1, y = 1;
while (n > 0) {
    if (n % 2 == 0) {
        ++x;
    } else {
        ++x;
        ++y;
    }
    n = n / 2;
}

每轮 n % 2 读取当前最低二进制位，随后 n / 2 去掉最低位。

对正整数：

• x = 1 + 二进制位数
• y = 1 + 二进制表示中 1 的个数

输入 0 时循环不执行，输出 1 1。

第 16 题：输入 3

答案：√。

3 的二进制是 11，共两位且有两个 1。

执行过程：

本轮 n	奇偶性	更新后 x	更新后 y	n/2
3	奇	2		1
1		3		0

所以输出 3 3。

---

第 17 题：删除奇数分支中的 ++x

答案：×。

删除后，x 只会在遇到二进制位 0 时增加，而 y 在遇到二进制位 1 时增加，两者并不保证相等。

反例：输入 1。循环只执行一次奇数分支，最终 x=1, y=2。

---

第 18 题：第一个数是否一定不小于第二个数

答案：√。

原程序中：

• 每一轮 x 都增加 1；
• 只有遇到 1 位时 y 才增加 1。

所以始终有 x >= y。输入 0 时二者都等于 1，也成立。

---

第 19 题：把条件改为 n >= 0

答案：A，陷入死循环。

非负整数不断除以 2，最终会变为 0。此时：

0 >= 0

仍为真，而 0 / 2 还是 0，循环条件再也无法变为假，因此程序不会结束。

---

第 20 题：输入 6

答案：C，4 3。

6 的二进制是 110，有 3 位，其中 2 个 1。

所以：

x = 1 + 3 = 4
y = 1 + 2 = 3

---

第 21 题：第二个数恰好为 2 的输入个数

答案：C，31。

y=2 表示二进制表示中恰好有一个 1，也就是 n 必须是 2 的非负整数次幂。

在范围 $0\le n\le2^{31}-1$ 中有：

$$2^0,2^1,\ldots,2^{30},$$

共 31 个。0 的输出为 1 1，不符合。

---

程序（2）：保留固定输出位数的高精度加法

程序将两个十进制字符串反向存入数组：

• a[0]、b[0] 是个位；
• a[1]、b[1] 是十位；
• 依此类推。

核心加法：

carry[0] = 0;
for (int i = 0; i < max(a_len, b_len) + 1; i++) {
    c[i] = a[i] + b[i] + carry[i];
    if (c[i] >= 10) {
        carry[i + 1] = 1;
        c[i] -= 10;
    } else {
        carry[i + 1] = 0;
    }
}

输出时固定从 c[max(a_len,b_len)] 一直输出到 c[0]，没有删除最高位的前导 0。

第 22 题：输入 123 456

答案：√。

正常和为 579，最大输入长度 $L=3$，程序依次输出：

c[3], c[2], c[1], c[0]
0,    5,    7,    9

因此输出：

0579

---

第 23 题：输入无前导零，输出是否一定无前导零

答案：×。

即使两个输入都没有前导零，程序仍会固定输出第 $L+1$ 位 c[L]。当最高位没有产生进位时，这一位就是 0。

例如 123 + 456 就输出 0579。

---

第 24 题：忽略进位后结果是否一定更小

答案：×。

把第 21 行改成：

c[i] = a[i] + b[i];

只是让当前位的计算不再加上上一位产生的进位，并不能推出输出结果一定严格更小。

反例：输入 123 456，每一位相加都不产生进位，修改前后都输出 0579。

---

第 25 题：输入 12345 678

答案：B，013023。

正常数值之和：

$$12345+678=13023.$$

最大输入长度为 5，程序会固定输出 6 个数组元素 c[5] 到 c[0]，最高位 c[5]=0，因此：

013023

---

第 26 题：把进位条件误写为 > 10

答案：A，01010。

输入 95 15：

• 个位：$5+5=10$，因为条件是 >10，不进位，c[0]=10；
• 十位：$9+1=10$，仍不进位，c[1]=10；
• 百位：c[2]=0。

随后：

cout << c[2] << c[1] << c[0];

注意 c[1] 和 c[0] 是整数 10，各会输出两个字符，所以得到：

01010

易错点： 此时 c[i] 已不再保证是一个十进制数位。

---

第 27 题：两个 n 位数相加但不增加位数

答案：C。

两个输入都是 $n$ 位数，因此 $L=n$。若它们的和小于 $10^n$，正确结果仍只有 $n$ 位，说明额外的最高位 c[n] 必为 0。

但程序仍固定输出 c[n] 到 c[0]，所以输出字符串长度为 $n+1$，且第一个字符为 '0'。

---

程序（3）：沿质数前缀进行深度优先搜索

程序首先判断当前 x 是否是质数：

• 若不是质数，立即返回；
• 若 x >= n，输出 x 并返回；
• 否则，在末尾依次追加数字 0～9，继续递归。

主函数依次从 1～9 开始搜索，但只有 2、3、5、7 能通过质数判断。

因此每个被继续扩展的十进制前缀本身都必须是质数。

第 28 题：输入 10，是否输出 10 行

答案：×，实际输出 9 行。

首位只能是 2、3、5、7。由于这些一位质数都小于 10，需要再追加一位，并且两位数本身也必须是质数。

输出为：

23
29
31
37
53
59
71
73
79

共 9 行。

---

第 29 题：当 n <= 5 时是否一定输出 5

答案：√。

主函数一定会调用：

search_result(5);

5 是质数，并且当 n <= 5 时有 5 >= n，所以程序会直接输出 5。

---

第 30 题：只追加奇数位是否影响结果

答案：√。

修改后追加的数字变为：

1, 3, 5, 7, 9

对于大于 10 的质数，末位不可能是偶数；末位为 5 的多位数也一定是合数，所以合法的多位质数本来就不会以 0、2、4、6、8 结尾。

虽然修改后的循环仍会尝试末位 5，但这些分支会被 check_prime 立即剪枝。最终输出集合与顺序不变。

---

第 31 题：输入 24 时第三行输出

答案：B，29。

程序按深度优先搜索顺序处理。

从首位 2 开始，23 是质数且小于 24，因此继续扩展 23 的整棵子树。满足阈值的最先两个输出是：

233
239

23 的子树完全搜索结束后，才处理同层的 29。29 是质数且 29 >= 24，因此第三行输出：

29

易错点： DFS 会先完整搜索 23 的整棵子树，再回到同层处理 29，输出并不是全局从小到大。

---

第 32 题：关于输出性质

答案：D。

每个大于等于 10 的输出值，都是从一个更短的数字前缀递归扩展而来。只有当父前缀通过 check_prime 后，程序才会继续递归，因此删去输出值最后一位后得到的前缀一定是质数。

其余选项：

• A 错：DFS 输出不保证全局递增，例如输入 24 时先输出 233、239，再输出 29。
• B 错：改变阈值会改变递归停止的位置，输出行数不具备“输入越大一定不增加”的单调性质。
• C 错：输出的个位还可能是 1 或 9，例如 31、59。

---

第 33 题：输入 200 时输出行数

答案：C，14。

两位质数前缀都小于 200，需要继续扩展一位。各前缀产生的三位质数如下：

两位质数前缀	输出的三位质数	数量
23	233, 239	2
29	293	1
31	311, 313, 317	3
37	373, 379	2
53	无	0
59	593, 599	2
71	719	1
73	733, 739	2
79	797	1

总数：

$$2+1+3+2+0+2+1+2+1=14.$$

完整输出顺序为：

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

---

三、完善程序解析

程序（1）：进制减半

题意与数组含义

原数以 $mn=m\times n$ 为底输入，要求转换为 $n$ 进制。

数组 b 用低位在前的方式保存当前数的 $n$ 进制表示：

$$V=\sum_{j=0}^{len-1}b[j]n^j.$$

从高位到低位读入原进制的下一位 x 时，当前值应更新为：

$$V_{new}=V\times(mn)+x.$$

也就是先乘 $m$，再整体左移一个 $n$ 进制位，最后把 x 加到最低位。

---

第 34 题：①处的移位与乘法

答案：D，b[j - 1] * m。

要把原来的第 j-1 位移动到第 j 位，并同时乘以 $m$：

for (int j = len; j >= 1; j--)
    b[j] = b[j - 1] * m;

之所以必须从高位向低位循环，是为了防止低位原数据先被覆盖。

---

第 35 题：②处如何加入新数位

答案：B，x。

完成整体乘以 $mn$ 的变换后，新读入的低位 x 直接放到最低位：

b[0] = x;

虽然 x 是原来 $mn$ 进制的一位，可能大于等于 $n$，但后面的进位循环会继续规范化。

---

第 36 题：③处向高位进多少

答案：D，b[j] / n。

在 $n$ 进制中，每满 $n$ 个当前单位，就应向高一位进 1。

若当前 b[j]=t，则：

$$t=\left\lfloor\frac{t}{n}\right\rfloor n+(t\bmod n).$$

因此向高位增加：

b[j + 1] += b[j] / n;

这里必须使用 +=，因为高一位本身可能已有数值，不能直接覆盖。

---

第 37 题：④处本位保留多少

答案：B，b[j] % n。

进位完成后，本位只保留除以 $n$ 的余数：

b[j] = b[j] % n;

这样可保证每个 $n$ 进制数位满足：

$$0\le b[j]<n.$$

---

第 38 题：⑤处删除前导零的条件

答案：C，len > 1 && b[len - 1] == 0。

数组低位在前，所以最高位是 b[len-1]。只应删除最高位的 0，同时至少保留一位，以便数值 0 仍能正确输出一个 0。

while (len > 1 && b[len - 1] == 0) len--;

---

补全后的程序

#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;
}

一次完整转换示例

下面给出一个转换示例取 $n=2,m=5$，则原进制为 $mn=10$。输入十进制数 13 的数位 1 3。

• 初始 b 表示 0。
• 读入 1 后，当前值为 1，二进制有效位可记作 [1]。
• 再读入 3，应更新为 $1\times10+3=13$；经乘移和逐位进位后，有效位最终为低位在前的 [1,0,1,1]。
• 从高位向低位输出，得到 1101，即 $(1101)_2=13$。

---

程序（2）：平衡分割

题意与递归状态

先把十六进制字符转换为 0～15 的整数，然后把整个序列切成至少两段连续非空区间。

递归状态：

split(l, cnt, mnb, mxb)

含义：

• l：下一段的起点，从位置 l 开始；
• cnt：目前已经选出的内部切分位置数量；
• mnb：已经确定的各段平均值中的最小值；
• mxb：已经确定的各段平均值中的最大值。

在一次调用中，枚举本段右端点 r。选定 [l,r] 后，下一段从 r+1 开始。

当 l > n 时，说明所有元素已经分完。若 cnt==0，说明整个序列从未切分，不满足题目至少切一次的要求；否则用 mxb-mnb 更新答案。

---

第 39 题：①十六进制字符转数值

答案：B。

合法字符只有 '0'～'9' 和 'A'～'F'，并采用 ASCII 编码。

对于数字字符：

c - '0'

对于字母字符：

c - 'A' + 10

可合并为：

c - (c < 'A' ? '0' : 'A' - 10)

所以答案为 B。

---

第 40 题：②枚举本段右端点

答案：D，int r = l; r <= n; ++r。

当前段必须非空，所以右端点至少是 l；同时需要枚举到 n，才能覆盖“当前段就是最后一段”的情况。

for (int r = l; r <= n; ++r)

---

第 41 题：③计算本段平均值

答案：C，sum * 1.0 / (r - l + 1)。

区间 [l,r] 有：

$$r-l+1$$

个元素，所以平均值为：

$$\frac{a[l]+a[l+1]+\cdots+a[r]}{r-l+1}.$$

sum 和区间长度都是整数，必须先引入浮点数 1.0，否则会发生整数除法丢失小数部分。

double nwb = sum * 1.0 / (r - l + 1);

---

第 42 题：④更新递归参数

答案：A。

选定当前段 [l,r] 后：

1. 下一段从 r+1 开始；
2. 只有 r<n 时，r 才是一个真正的内部切分位置，因此 cnt 增加 1；
3. 新段平均值 nwb 要更新当前最小值；
4. 同时更新当前最大值。

所以：

split(
    r + 1,
    cnt + (r < n),
    min(mnb, nwb),
    max(mxb, nwb)
);

即选项 A。

---

第 43 题：⑤初始化递归

答案：D，1, 0, 1e100, -1e100。

第一次调用时：

• 序列从下标 1 开始，因此 l=1；
• 尚未选择任何内部切分位置，cnt=0；
• 为了让第一次平均值能正确更新最小值，mnb 应初始化为极大的正数；
• 为了让第一次平均值能正确更新最大值，mxb 应初始化为极小的负数。

因此：

split(1, 0, 1e100, -1e100);

---

补全后的程序

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

using namespace std;

constexpr int N = 25;

int n, a[N];
char s[N];

double ans = 1e100;

int value(char c) {
    return c - (c < 'A' ? '0' : 'A' - 10);
}

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

int main() {
    cin >> n >> s + 1;
    for (int i = 1; i <= n; ++i)
        a[i] = value(s[i]);
    split(1, 0, 1e100, -1e100);
    cout << fixed << setprecision(6) << ans;
    return 0;
}

分割示例

以 n=3、字符串 012 为例。两个内部位置共有 $2^2=4$ 种“切或不切”的组合，但完全不切不满足“至少切一次”，因此有效方案有 3 种：

分割方案	各段平均值	最大值减最小值
`0	12`	0, 1.5
`01	2`	0.5, 2
`0	1	2`

最优答案为：

1.500000

正确性与复杂度要点

递归在每个阶段枚举当前连续段的右端点，因此每一种连续分段方案都恰好对应一条递归路径，不会遗漏，也不会重复。

到达 l>n 时，所有段都已经确定；此时用所有段平均值中的最大值减最小值更新全局答案，即可在遍历完全部合法方案后得到最小差值。

长度为 $n$ 的序列有 $n-1$ 个内部间隙，每个间隙可“切”或“不切”，总方案量级为 $2^{n-1}$，因此整体复杂度约为 $O(2^n)$，递归栈与数组使用 $O(n)$ 空间。对 $n\le20$ 可以接受。

---

四、考后复盘

知识点	对应题号	需要掌握的关键动作
数据类型与表达式	1、3、11、39、41	区分精度和范围；正确处理整数除法、指针和类型转换
进制表示	2、16～21、34～38	读二进制位；理解位权、商与余数、低位在前的数组
基础数据结构	4、5、8、15	模拟栈和队列；利用完全二叉树编号和度数和
数学与计数	6、7、9、10、13、14	容斥、递推、公约数、反例、前缀和差分、中位数
二分查找	12	跟踪待查区间缩小过程
高精度加法	22～27	从低位向高位进位，严格控制输出循环确定字符串
递归搜索	28～33、40、42、43	明确进入、剪枝、输出和返回顺序，区分状态含义

做阅读程序题时，先明确每个变量“记录什么”，再手动跟踪关键输入和边界输入；遇到“一定”“不会”等绝对表述，优先寻找反例。

做完善程序题时，不要只看单个空，要把选项放回完整程序中检查：变量含义、循环边界、进位方向、递归状态、初始化值、输出格式是否一致。