CSP-S 2026 第一轮参考题解

本题解依据所给洛谷帖子中的 S 组题面整理，参考答案经独立推导及程序核验。判断题中，A 表示正确，B 表示错误。全卷43小题，共100分。

答案速查

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

一、单项选择题

1．D：8

x & (x - 1) 每次清除二进制表示中最低的一个1，因此循环次数等于1的个数。$2026=(11111101010)_2$，共有8个1，所以 cnt = 8。

2．D：102

哈夫曼树每次合并当前权值最小的两个结点。依次产生的新权值为

$$3,6,9,12,15,21,36.$$

每次合并让两棵子树的全部叶子深度增加1，带权路径长度恰好增加两棵子树的权值和。因此答案为这些合并权值之和：$102$。

3．C：301

先把 $0$ 到 $999$ 都写成三位数，不足处补0。在百、十、个位上，数字1各出现100次，合计300次。补上的前导0不会增加1的数量，且数字0自身不含1。最后，1000还含有一个1，故总数为301。

4．D：20

先选出恰好装对的两封信，有 $\binom52=10$ 种。余下三封必须全部装错，三元素错排共有2种。因此答案为 $10\times2=20$。不能让余下三封任意排列，否则会计入超过两封装对的情况。

5．A：29

$3^{10}=59049\equiv49\pmod{100}$，所以 $3^{20}\equiv49^2\equiv1\pmod{100}$。又因为 $2026=20\times101+6$，所以

$$3^{2026}\equiv3^6=729\equiv29\pmod{100}.$$

6．C：34

令 $f(l,r)$ 表示把连续石堆 $[l,r]$ 合成一堆的最小代价。最后一次合并一定发生在某个分界点 $k$，于是

$$f(l,r)=\min_{l\le k<r}\{f(l,k)+f(k+1,r)\}+\sum_{i=l}^r a_i,$$

且 $f(i,i)=0$。按区间长度递推，长度2的代价依次是 $5,4,5,7$；长度3是 $12,10,15$；长度4是 $20,21$；最终

$$f(1,5)=15+\min(21,5+15,12+7,20)=34.$$

一种最优过程为：合并中间的 $1+3$，代价4；将最左的4与新产生的4合并，代价8；合并 $2+5$，代价7；最后合并 $8+7$，代价15。总计34。这里限制了相邻合并，不能直接套哈夫曼树的贪心。

7．A：3和4

查询前缀和时不断执行 i -= lowbit(i)，访问下标 $11\to10\to8$，共3个。单点修改时执行 i += lowbit(i)，访问 $3\to4\to8\to16$，共4个；下一项32越界，不再访问。

8．B：8

先只考虑顶点1、2、3。顶点1必须排在另外两点之前，因此只有 1 2 3 和 1 3 2 两种顺序。孤立点4可以插入每个序列的4个位置，得到 $2\times4=8$ 种拓扑序。

9．A：$\Theta(n\log n)$

每次划分后两个子问题的规模之和仍为 $n$，所以递归树上每一层尚未终止的结点，其规模总和不超过 $n$，本层代价为 $O(n)$。最长分支每次缩小到原来的 $2/3$，层数为 $O(\log n)$，总上界为 $O(n\log n)$。

前 $\Theta(\log n)$ 层中也有一段完整展开的层次：在深度小于约 $\log_3 n$ 时，即使沿最小的 $1/3$ 子问题继续递归，也还没有到达常数规模。每个这样的完整层代价为 $\Theta(n)$，得到相同的下界。因此总复杂度为 $\Theta(n\log n)$。

10．D：直径7，重心1

从9到8的路径为 $9\to5\to2\to1\to3\to6\to7\to8$，共有7条边，也是最长路径。删除结点1后得到两个大小均为4的连通块，最大连通块大小4不超过 $9/2$，因此1是重心。直径经过结点不代表这些结点都是重心；重心看的是删除后的连通块大小。

11．C：4

对含有多个结点的缩点DAG，使其强连通所需的最少添加边数为

$$\max(\text{入度为0的结点数},\text{出度为0的结点数}).$$

每个源点都需要一条新入边，每个汇点都需要一条新出边，故答案至少是这两个数量的最大值；标准的强连通补边构造可以达到这个下界。本题为 $\max(3,4)=4$。孤立点会同时计入源点与汇点，不能简单把两类数量相加。

12．C：132

设 $C_n$ 为含 $n$ 个结点、区分左右子树的二叉树数量。选择根后，若左子树有 $i$ 个结点，右子树就有 $n-1-i$ 个，因此

$$C_0=1,\qquad C_n=\sum_{i=0}^{n-1}C_iC_{n-1-i}.$$

这就是卡特兰数，前几项为 $1,1,2,5,14,42,132$，故 $C_6=132$。

13．B：6

长度2的前后缀都是 ab，长度4的前后缀都是 abab。其余长度1、3、5、6、7、8均不匹配，而长度9是整个字符串，不是真前缀或真后缀。因此长度之和为 $2+4=6$。

14．C：把相等元素对也计入

修改后，仅当 a[i] < a[j] 时取左边，否则取右边并增加 mid - i + 1。进入 else 意味着 a[i] >= a[j]，而左半段已经有序，因此左边剩余元素都大于或等于当前右元素。这会统计全部满足原下标 $i<j$ 且 $a[i]\ge a[j]$ 的数对，包括原先没有计入的相等元素对。

15．B：376

函数使用二进制快速幂，计算 $2^{100}\bmod1000$。例如，$2^{10}\equiv24$，$2^{20}\equiv576$，$2^{40}\equiv776$，$2^{80}\equiv176\pmod{1000}$，所以

$$2^{100}\equiv176\times576\equiv376\pmod{1000}.$$

二、阅读程序

阅读（1）：模2多项式除法

程序把输入串从高位到低位存入 a[0..31]，再补12个0。数组 gen 对应13位串 1100000001111，即多项式 $x^{12}+x^{11}+x^3+x^2+x+1$。它的最高项系数为1。

逐位处理 a[i] 时，若它为1，就对齐除数并异或，消去这一位；若它已经为0，就跳过。模2多项式的减法等于异或，没有借位。最后保留的12位是余数，不能把这个过程误解为普通整数带借位的除法。

16．A：正确

输入全0，补位也全0。每次都会被 continue 跳过，没有任何位改变，最终输出12个0。

17．A：正确

处理位置 $i$ 时，该位如果为1，就与 gen[0]=1 异或变为0；否则保持0。后续只会修改更靠后的位置，不会再访问它。所以 a[0..31] 最终全为0。

18．B：错误

a 定义在函数外，具有静态存储期，所有元素在程序开始时自动初始化为0。输入循环只改写 a[0..31]，因此 a[32..43] 本来就是0。删除这段显式补0代码，结果不变。若换成未初始化的局部数组，则不能使用这个结论。

19．C：gen[0] 是除数最高位

数组有13个元素。每次处理被除式的当前最高位 a[i] 时，都将 gen[0] 与它对齐，所以下标越小，表示的位越高。

20．B：补12个0后做模2除法

输入串右侧补12个0，在二进制位模式上相当于 $M\times2^{12}$，在多项式表示中相当于乘 $x^{12}$。随后执行模2除法，最终输出次数低于12的余数对应的12位串。

21．C：结果不再依赖输入

删去条件后，外层循环固定执行32次异或，每次修改的位置和掩码也固定。被输出的 a[32..43] 初始均为0；它们只会被这些固定掩码改变，而不会从 a[0..31] 读取数据。因此输出与输入无关，实际固定输出为 100000000101。

所有异或下标仍在 $0$—$43$ 内，不会越界。a[0] 只与1异或一次，输入首位为0时它最终为1，因此D不成立。

阅读（2）：ST表求区间最大公约数

对已建立的有效表项，dp[i][j] 表示长度为 $2^j$、左端点为 $i$ 的区间GCD。长度为 $2^j$ 的区间拆成两个长度为 $2^{j-1}$ 的相邻区间，因此第22行的转移正确。

本题必须按原代码理解 lg。它使用 pw[t + 1] >= i，于是

$$lg[1]=0,\qquad lg[x]=\lceil\log_2x\rceil-1\quad(x\ge2).$$

对于 $x\ge2$，令 $k=lg[x]$，有 $2^k<x\le2^{k+1}$。查询使用两端各一个长度为 $2^k$ 的区间。这两段覆盖整个询问区间，没有空隙；当长度恰为2的幂时两段恰好相邻，其余时候可能重叠。GCD满足 $\gcd(v,v)=v$，重叠元素重复参与计算不会改变答案。长度1另由 lg[1]=0 正确处理。

22．A：正确

区间 $[2,5]$ 中的数为 $2,6,3,3$，最大公约数为1。按程序，此时 $lg[4]=1$，两段为 $[2,3]$ 和 $[4,5]$，其GCD分别为2和3，最终结果仍是1。

23．A：正确

$L=R$ 时使用 lg[1]=0，两个表项都是 dp[L][0]=a[L]。$\gcd(a[L],a[L])=a[L]$。

24．B：错误

正整数的公约数不会大于任意一个数，所以区间GCD一定不大于区间最小值，并非一定不小于它。例如区间 $\{2,3\}$ 的GCD是1，小于最小值2。

25．B：连续 $2^j$ 个数的GCD

dp[i][0] 对应一个元素。每提高一层，都把两个上一层区间合并，区间长度翻倍。因此 dp[i][j] 对应 $a_i,a_{i+1},\ldots,a_{i+2^j-1}$。这里指程序实际建立、没有越过右端点的表项。

26．B：$\Theta(n\log n)$

建表有 $\Theta(\log n)$ 层，每层最多处理 $n$ 个起点；前面若干层也都有 $\Theta(n)$ 个有效起点。题目将一次GCD计算视为常数时间，因此总时间为 $\Theta(n\log n)$。这问只统计建表，不包含 $m$ 次查询。当前排版中的完整建表范围是第17—24行。

27．D：$[33,64]$

t=4 时，$pw[5]=32$，所以直到32仍取4。处理33时，条件 $32\ge33$ 不成立，t 增为5。之后直到64都满足 $pw[6]=64\ge i$，到65才增为6。因此范围是 $[33,64]$。

阅读（3）：树形DP求直径

由于 $fa[i]<i$，从大编号向小编号处理时，一个结点的全部后代一定已处理完。f[i] 在结点 $i$ 被处理时，是从它出发向子树内部走的最长距离；父结点当前的 f 则来自已经合并过的其他孩子。

处理孩子 $i$ 时，f[fa[i]] + f[i] + 1 把父结点已有的一条下行链，与经过当前孩子的新下行链拼起来。两条链来自不同的分支，可以组成一条简单路径。先尝试更新直径，再更新父结点的最长下行链，才能避免使用同一分支两次。每条最长路径都在其最高结点合并两侧分支时被考虑到，因此 ans 等于树的直径。时间、空间复杂度均为 $O(n)$。

28．A：正确

输入构成链 $1-2-3-4-5$，最远的两点为1与5，其间4条边。

29．B：错误

f[1] 是根到最远后代的距离，ans 是任意两点间的最大距离。例如 $n=3$，父结点为 1 1，树为2—1—3。此时 f[1]=1，而 ans=2。

30．B：错误

如果先更新父结点的 f，再计算 ans，父结点记录的最长链可能恰好来自当前孩子，导致把同一段路径用两遍。最小反例是 $n=2,fa[2]=1$：原程序输出1；交换后先令 f[1]=1，随后算出 1+0+1=2，输出错误。

31．A：直径的边数

ans 枚举的是两条不同下行分支连接后的路径长度，最终对应全树最远两点的距离。根高度、叶子数和父编号之和都不是它维护的量。

32．C：4

给定父数组形成一棵三层满二叉树。比如路径 $4\to2\to1\to3\to6$ 长度为4，已经最长，因此输出4。

33．C：256

10个结点的树直径为9，当且仅当整棵树是一条链。由于父编号严格小于子编号，以1为根后，沿根的任一侧走向链端，编号必须严格递增。

将结点 $2,3,\ldots,10$ 分配到根的两侧，每侧按编号递增连接，就得到所有合法的链。9个结点各有2种归属，共 $2^9$ 种。交换两侧得到的是同一个父数组，因此每个父数组恰好被计算两次，答案为 $2^9/2=256$。允许一侧为空；交换后仍是两种不同的分配，不影响除以2。

三、完善程序

完善（1）：平衡路线

把正边记为 $+1$，负边记为 $-1$。一条路线的带符号和为 $W=n_+-n_-$，要最小化的是 $|W|$。路线允许重复走边，这一点决定了做法。

先从 $s$ 做BFS，记录最少边数 d，同时用 c 将每条树边两端染成不同颜色。p 和 ng 分别记录 $s$ 所在连通块中是否出现正、负边；ok 记录该连通块是否为二分图。

可以分三类处理：

1. $t$ 不可达，输出 $-1$。
2. 连通块内只有一种符号，任何路线的权值都等于经过的边数，故直接输出最短路长度 d[t]。
3. 连通块同时含有两种符号，此时最小值只与路线长度的奇偶性有关。

第三类的原因可以完整地说明。来回走一次正边使带符号和增加2；来回走一次负边使它减少2。从 $s$ 出发，选择一条闭合往返路线，让它能访问到某条正边和某条负边。这条固定往返路线的带符号和是偶数。在正、负边处分别额外往返若干次，就能把该闭合路线的带符号和调成任意指定的偶数。因此，可以在原路线前插入闭合路线，把原来的带符号和调成任意同奇偶性的整数。

每走一条边，不论符号为何，带符号和的奇偶性都会翻转。所以 $W$ 与路线的边数同奇偶。若连通块是二分图，同色两点间的路线都是偶数长度，可以调到0；异色两点间都是奇数长度，绝对值最小为1。若连通块不是二分图，就存在奇环，绕行一次可改变奇偶性，再利用前面的偶数调整，总能得到0。

34．C：op[0] == '+' ? 1 : -1

后面用 w[i] > 0 与 w[i] < 0 分别判断正、负边。只有C正确地保留两种符号。若把负边存成0，ng 就永远不能被置为1。

35．D：hh < tt

队列有效区间是左闭右开 $[hh,tt)$。只有队首严格小于队尾时才有待处理结点。使用 hh <= tt 会在队列已空时多取一次；与 $n$ 比较也不能表达当前队列是否为空。

36．B：d[x] + 1

首次沿 $x\to y$ 发现 $y$，它的最短距离是 $x$ 的距离加一，这是无权图BFS的距离转移。

37．A：c[y] == c[x]

若一条边连接了相同颜色的两个结点，则二分图染色发生冲突，存在奇环，令 ok=0。边的正负号与图是否为二分图没有关系。重边也按同一规则处理；若有自环，同样会产生冲突。

38．C：!ok || c[s] == c[t]

运行到这里时已经确认可达，且正负边都存在。非二分图能改变路线奇偶性，答案为0；二分图中同色端点之间也能调到0。仅剩二分图异色端点的情况输出1，因此条件为C。

补全后的参考代码

#include <iostream>
constexpr int N = 200005;
constexpr int M = 400005;
int n, m, s, t;
int h[N], e[M << 1], ne[M << 1], w[M << 1], idx;
int q[N], d[N], c[N];
void add(int a, int b, int z) {
    e[idx] = b;
    w[idx] = z;
    ne[idx] = h[a];
    h[a] = idx++;
}
int main() {
    std::cin >> n >> m >> s >> t;
    for (int i = 1; i <= n; i++)
        h[i] = d[i] = c[i] = -1;
    for (int i = 0; i < m; i++) {
        int a, b;
        char op[2];
        std::cin >> a >> b >> op;
        int z = op[0] == '+' ? 1 : -1;
        add(a, b, z);
        add(b, a, z);
    }
    int hh = 0, tt = 0;
    int p = 0, ng = 0, ok = 1;
    q[tt++] = s;
    d[s] = c[s] = 0;
    while (hh < tt) {
        int x = q[hh++];
        for (int i = h[x]; i != -1; i = ne[i]) {
            int y = e[i];
            if (w[i] > 0) p = 1;
            if (w[i] < 0) ng = 1;
            if (d[y] == -1) {
                d[y] = d[x] + 1;
                c[y] = c[x] ^ 1;
                q[tt++] = y;
            } else if (c[y] == c[x])
                ok = 0;
        }
    }
    if (d[t] == -1) {
        std::cout << -1;
        return 0;
    }
    if (!p || !ng) {
        std::cout << d[t];
        return 0;
    }
    if (!ok || c[s] == c[t]) std::cout << 0;
    else std::cout << 1;
    return 0;
}

BFS只处理 $s$ 所在连通块，整体时间复杂度为 $O(n+m)$，邻接表、队列和数组占用 $O(n+m)$ 空间。即使别的连通块出现另一种符号，也不应该影响本题的判断。

完善（2）：标准答案

直接枚举标准答案有 $2^m$ 种，$m\le300$，不可行。学生数最多18，程序转而枚举每名学生对应的一个正负号，共 $2^n$ 种。

设学生 $i$ 在题 $j$ 的作答对应 $b_{ij}\in\{+1,-1\}$，A为 $+1$、B为 $-1$；标准答案对应 $z_j\in\{+1,-1\}$。两者相同得到1分，因此

$$r_i=\frac{m+\sum_jb_{ij}z_j}{2}.$$

令 $c_i=m-2x_i$，便有 $2(r_i-x_i)=c_i+\sum_jb_{ij}z_j$。利用恒等式 $|u|=\max_{s\in\{-1,1\}}su$，将目标乘以2后得到

$$\max_{z}\sum_i\left|c_i+\sum_jb_{ij}z_j\right| =\max_{s,z}\left(\sum_is_ic_i+\sum_jz_j\sum_is_ib_{ij}\right).$$

固定学生符号 $s_i$，记 $C=\sum_is_ic_i$、$q_j=\sum_is_ib_{ij}$。每道题可独立决定：$q_j>0$ 选A，$q_j<0$ 选B，等于0时任选。固定 $s$ 的最优值就是

$$C+S,\qquad S=\sum_j|q_j|.$$

所以只要遍历全部 $2^n$ 种学生符号，找到最大的 C + S，保存该组符号，再逐题恢复标准答案即可。ans 保存的是原目标最优值的两倍，但程序最终只需要输出答案字符串，无须再除以2。

为了减少更新量，程序用格雷码枚举学生符号。相邻格雷码只改变一个二进制位，即只翻转一个学生的 $s_k$。这样无需重新计算整个 $n\times m$ 矩阵，只需更新第 $k$ 名学生对各列的贡献。

39．C：m - 2 * x[i]

由 $2(r_i-x_i)=m-2x_i+\sum_jb_{ij}z_j$，常数项必须是 $c_i=m-2x_i$。初始所有 s[i] 为 $-1$，故初始化时执行 C -= c[i]。

40．B：mask ^ (mask >> 1)

二进制反射格雷码为 $g=mask\oplus(mask\gg1)$。它按顺序枚举所有 $n$ 位状态，且相邻两个状态只有一位不同。普通二进制计数在进位时会同时改变多位，不能直接用于此处的单行更新。

41．D：__builtin_ctzll(d)

d = g ^ lst 只在被翻转的那一位上为1。末尾连续0的个数就是这一位从0开始的编号，对应需要改变的学生下标。d 一定非零，满足函数对参数的要求。popcount(d) 恒为1，无法定位该学生；对 g 本身求末尾0也无法定位此次变化。

42．A：2ll * s[k] * c[k]

翻转前，学生 $k$ 对 C 的贡献是 $s_kc_k$，翻转后是 $-s_kc_k$，变化量为 $-2s_kc_k$。由于代码写的是 C -= ...，应填 $2s_kc_k$。这里使用的是翻转之前的 s[k]；真正执行 s[k] = -s[k] 在后面。

同理，列和改变 $-2s_kb_{kj}$，正好对应 q[j] -= 2ll * s[k] * v，再用新旧绝对值之差维护 S。

43．A：v >= (n & 1)

恢复答案时，v 就是对应列的 $q_j$，是 $n$ 个 $+1$ 或 $-1$ 之和，因此与 $n$ 同奇偶。

• $n$ 为偶数时，条件变为 v >= 0，非负选A；$v=0$ 时两种答案一样好。
• $n$ 为奇数时，$v$ 不可能为0，最小的正值是1，所以 v >= 1 恰好等价于 $v>0$。

其他条件都存在反例：B在 $n$ 为奇数且 $v=1$ 时错选B；C在 $n$ 为奇数且 $v=-1$ 时错选A；D在 $n$ 为偶数时恒为真，即使 $v<0$ 也会选A。因此只能选择A。

补全后的参考代码

#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int main() {
    int n, m;
    cin >> n >> m;
    vector<ll> x(n), c(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i];
        c[i] = m - 2 * x[i];
    }
    vector<string> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    vector<int> s(n, -1);
    vector<ll> q(m, 0);
    ll C = 0, S = 0;
    for (int i = 0; i < n; i++) {
        C -= c[i];
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 'A') q[j]--;
            else q[j]++;
        }
    }
    for (int j = 0; j < m; j++) S += abs(q[j]);
    ll ans = C + S;
    ull best = 0, lst = 0;
    for (ull mask = 1; mask < (1ULL << n); mask++) {
        ull g = mask ^ (mask >> 1);
        ull d = g ^ lst;
        int k = __builtin_ctzll(d);
        C -= 2ll * s[k] * c[k];
        for (int j = 0; j < m; j++) {
            ll old = q[j];
            int v = (a[k][j] == 'A' ? 1 : -1);
            q[j] -= 2ll * s[k] * v;
            S += abs(q[j]) - abs(old);
        }
        s[k] = -s[k];
        if (C + S > ans) {
            ans = C + S;
            best = g;
        }
        lst = g;
    }
    for (int i = 0; i < n; i++) {
        if ((best >> i) & 1) s[i] = 1;
        else s[i] = -1;
    }
    string res(m, 'A');
    for (int j = 0; j < m; j++) {
        ll v = 0;
        for (int i = 0; i < n; i++) {
            if (a[i][j] == 'A') v += s[i];
            else v -= s[i];
        }
        if (v >= (n & 1)) res[j] = 'A';
        else res[j] = 'B';
    }
    cout << res << endl;
    return 0;
}

初始化和恢复答案各需 $O(nm)$，格雷码枚举的每个状态用 $O(m)$ 更新，总时间为 $O(nm+2^n m)$，空间为 $O(nm+n+m)$。在 $n=18,m=300$ 时，核心枚举约处理 $7.9\times10^7$ 个列更新；相较直接对每个状态重算所有学生，减少了一个 $n$ 因子。

难度与训练定位

本包整数难度配置为 5（提高，独立估计）。这是对整卷完整理解难度的概括，不是官方评级，也不表示每道题都达到该难度。选择题主要考察组合计数、常见数据结构和复杂度；阅读程序侧重准确追踪状态、边界及算法不变量。两道完善程序的理解上限较高，分别涉及无向图路线的奇偶性，以及绝对值目标转换和格雷码增量枚举。

本卷本身按 CSP-S 第一轮客观题的结构组织，适合提高组第一轮训练。做题时应重点区分“认识算法名称”与“能解释这份代码为什么正确”：例如 ST 表的非标准对数边界、树形DP的更新顺序、格雷码恢复答案时的奇偶条件，都需要逐行理解。这个客观题包不用于衡量第二轮独立编程完成度，也不据此推测分数线。