2026 CSP-S 第一轮真题

0
椰子椰子老师 LV 10 SU @ 2026-9-22 15:03:22
2026 CSP-S 第一轮题解

本题解按所提供的 S 组资料整理。若后续 CCF 官方公布的最终答案与当前资料存在差异，以官方最终公布为准。

答案速查

题号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

答案 D C D A C A B A D C B C B

题号 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

答案 √ × C B C √ × B C √ × A C

题号 34 35 36 37 38 39 40 41 42 43

答案 C D B A C B D A

一、单项选择题（15 题 · 每题 2 分 · 共 30 分）

每题有且仅有一个正确选项。

第 1 题 · 位运算

执行下列代码后，cnt 的值是（）。
```
int x = 2026, cnt = 0;
while (x) {
    x &= x - 1;
    cnt++;
}
```
- A. 6
- B. 7
- C. 11
- D. 8
答案：D

x &= x - 1 每次抹掉最低位的那个 1。2026 = $11111101010_2$ ，一共 8 个 1，循环 8 次。

第 2 题 · 哈夫曼树

用权值 {1, 2, 3, 4, 5, 6, 7, 8} 构造哈夫曼树，其带权路径长度是（）
- A. 108
- B. 96
- C. 99
- D. 102
答案：D

依次合并：1+2=3、3+3=6、4+5=9、6+6=12、7+8=15、9+12=21、15+21=36。所有合并代价之和就是 WPL：3+6+9+12+15+21+36 = 102。

第 3 题 · 计数

把 1 到 1000 的所有整数按十进制写出，数字「1」总共出现了多少次（）
- A. 300
- B. 271
- C. 301
- D. 320
答案：C

000～999 这一千个三位数里，每一位出现 1 的次数都是 300（1000×3÷10）。再加上 1000 里的那一个 1，共 301。

第 4 题 · 错排

将 5 封信随机装入 5 个写好地址的信封（每封一个），恰好有 2 封装对的方案数是（）
- A. 44
- B. 24
- C. 10
- D. 20
答案：D

先选出装对的那 2 封：C(5,2) = 10；剩下 3 封必须全部装错，3 个元素的错排数是 2。10 × 2 = 20。

第 5 题 · 模运算

$3^{2026}\bmod 100$ 的值是（）
- A. 29
- B. 9
- C. 43
- D. 81
答案：A

$3^n\bmod 100$ 的周期是 20（ $3^{20}\equiv 1\pmod{100}$ ）。 $2026\bmod 20=6$ ， $3^6=729$ ，末两位 29。

第 6 题 · 区间 DP

有 5 堆石子排成一行，重量依次为 4, 1, 3, 2, 5。每次只能把相邻的两堆合并成一堆，代价为这两堆重量之和。将所有石子合并成一堆的最小总代价是（）
- A. 36
- B. 35
- C. 34
- D. 33
答案：C

经典「石子合并」。最优合并顺序是 (1+3=4)、(2+5=7)、(4+4=8)、(8+7=15)，代价 4+7+8+15 = 34。区间 DP 跑出来也是 34。

第 7 题 · 树状数组

树状数组维护长度 n = 16 的序列。查询前缀和 sum(11) 与单点修改 add(3, x) 分别需要访问树状数组中多少个下标（）
- A. 3 和 4
- B. 4 和 4
- C. 3 和 5
- D. 4 和 3
答案：A

查询是 i -= lowbit(i)：11 → 10 → 8，共 3 个。修改是 i += lowbit(i)：3 → 4 → 8 → 16，共 4 个。

第 8 题 · 拓扑排序

有向无环图 G 顶点集为 {1, 2, 3, 4}，边集为 {(1, 2), (1, 3)}，顶点 4 与任何顶点均不相邻。该图不同的拓扑序共有多少种（）
- A. 12
- B. 8
- C. 4
- D. 6
答案：B

1 必须在 2、3 前面，所以 1、2、3 只有 2 种相对顺序（123 或 132）。4 和谁都没边，可以插进 4 个位置中的任意一个：2 × 4 = 8。

第 9 题 · 分治复杂度

某分治算法满足 T(n) = T(n/3) + T(2n/3) + Θ(n)，T(1) = O(1)，则 T(n) 是（）
- A. $\Theta(n\log n)$
- B. $\Theta(n^2)$
- C. $\Theta(n^{1.5})$
- D. Θ(n)
答案：A

递归树每往下走一层，各结点规模之和恒为 n（1/3 + 2/3 = 1），树高是 log n，所以总代价是 $\Theta(n\log n)$ 。

第 10 题 · 树的直径与重心

无根树含 9 个结点（编号为 1—9），边集为 {(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (6, 7), (7, 8), (5, 9)}。该树的直径（以边数计）与重心分别是（）
- A. 直径 6，重心为结点 3
- B. 直径 7，重心为结点 2
- C. 直径 8，重心为结点 1
- D. 直径 7，重心为结点 1
答案：D

最长路径是 9-5-2-1-3-6-7-8，一共 7 条边。去掉结点 1 后两边各剩 4 个点，是所有点里最大的连通块最小的，所以重心是 1。

第 11 题 · 强连通分量

一张有向图缩点后得到的有向无环图含 6 个顶点，其中入度为 0 的顶点有 3 个、出度为 0 的顶点有 4 个。为使原图变成强连通图，至少需要添加多少条有向边（）
- A. 7
- B. 6
- C. 4
- D. 3
答案：C

结论：最少加边数 = max(入度 0 的个数, 出度 0 的个数) = max(3, 4) = 4。

第 12 题 · 卡特兰数

含 6 个结点的不同形态的二叉树共有多少棵（结点不带标号，区分左右子树）（）
- A. 42
- B. 429
- C. 132
- D. 720
答案：C

n 个结点的二叉树形态数就是卡特兰数 Cn。C6 = C(12,6)/7 = 924/7 = 132。

第 13 题 · 字符串前后缀

字符串 S = "ababaabab"，其所有既是真前缀又是真后缀的子串（非空）的长度之和是（）
- A. 4
- B. 6
- C. 7
- D. 5
答案：B

长度 2 的 "ab" 同时是前缀和后缀；长度 4 的 "abab" 也是。再往后都不匹配，所以和是 2 + 4 = 6。

第 14 题 · 归并排序

用归并排序统计逆序对，合并部分的核心代码为（见下方代码）。若把判断条件中的 a[i] <= a[j] 改成 a[i] < a[j]，则 ans 统计出的结果是（）
```
// 归并 a[l..mid] 与 a[mid+1..r]，同时累加逆序对
if (a[i] <= a[j]) {
    tmp[k++] = a[i++]; // 取左半段元素
}
else {
    tmp[k++] = a[j++]; // 取右半段元素
    ans += mid - i + 1;
}
```
- A. 完全不变
- B. 变为原来的两倍
- C. 变为满足 i < j 且 a[i] >= a[j] 的数对个数
- D. 变为原来的一半
答案：C

改成严格小于以后，a[i] == a[j] 时会走 else 分支，把相等的数对也算进 ans。原本只统计 a[i] > a[j]，现在变成统计 a[i] >= a[j]。注意它不是「原来的两倍」——只有相等对的个数恰好等于原来那么多时才成立。

第 15 题 · 快速幂

执行 power(2, 100, 1000) 调用下列函数，返回值是（）
```
long long power(long long a, long long b, long long p) {
    long long r = 1 % p;
    while (b) {
        if (b & 1)
            r = r * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return r;
}
```
- A. 576
- B. 376
- C. 976
- D. 176
答案：B

模 125： $2^{100}\equiv 1\pmod{125}$ ；模 8： $2^{100}\equiv 0\pmod 8$ 。由中国剩余定理解出 376。

二、阅读程序（3 段 · 共 40 分）

判断题正确填 √，错误填 ×。除特殊说明外，判断题 1.5 分，选择题 3 分。

（1）模 2 除法（CRC 求余）
```
#include <iostream>
#include <string>
using namespace std;
int a[100];
string s;
int gen[13] = {1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1};
int main() {
    cin >> s;
    for (int i = 0; i < 32; ++i) {
        a[i] = s[i] - '0';
    }
    for (int i = 32; i < 44; ++i) {
        a[i] = 0;
    }
    for (int i = 0; i < 32; ++i) {
        if (a[i] == 0) continue;
        for (int j = 0; j < 13; ++j) {
            a[i + j] ^= gen[j];
        }
    }
    for (int i = 32; i < 44; ++i) {
        cout << a[i];
    }
    cout << endl;
    return 0;
}
```
说明：输入保证为一个长度恰为 32 的 '0'/'1' 字符串。

第 16 题（1 分）

当输入为 32 个 ‘0’ 时，程序输出 12 个 0。

答案：√

全 0 输入时 a[i] == 0 一律 continue，一次异或都不会执行；而 a[32]～a[43] 刚被补成 0，所以原样输出 12 个 0。

第 17 题

程序运行结束后，数组 a 中下标从 0 到 31 的元素一定全部为 0。

答案：√

处理到 i 时 gen[0] = 1 会把 a[i] 抹成 0；之后 i 更大的那些轮只会改下标 ≥ i 的位置，不会再动 a[i]。跑 3000 组随机输入，a[0..31] 全 0 无一例外。

第 18 题

若将第 12～14 行（为 a[32] 到 a[43] 补 0 的循环）删除，会改变程序输出结果。

答案：×

a 是全局数组，C++ 里全局变量默认零初始化，a[32]～a[43] 本来就是 0。删掉这个循环输出完全不变。

第 19 题

关于第 6 行定义的数组 gen，下列说法正确的是（）。
- A. gen 共有 12 个元素，表示一个 12 位的除数
- B. gen 共有 13 个元素，表示一个 13 位的被除数
- C. gen 共有 13 个元素，其中 gen[0] 是除数的最高位
- D. gen 共有 13 个元素，其中 gen[12] 是除数的最高位
答案：C

gen 有 13 个元素。因为 a[i + j] ^= gen[j] 里 gen[0] 对齐的是 a[i]，而 a[i] 正是当前要消掉的最高位，所以 gen[0] 必须是除数的最高位——它等于 1，异或后 a[i] 才归零。

第 20 题

该程序实现的功能，最准确的说法是（）。
- A. 将输入的 32 位串看成二进制数 M，输出 M 与 13 位二进制数 1100000001111 按位异或的结果
- B. 将输入串视为 32 位二进制数 M，在其后补 12 个 0（即计算 $M\times 2^{12}$ ），再对它用 1100000001111 作模 2 除法求余数，并输出 12 位余数
- C. 对输入的 32 位串逐位取反并输出结果
- D. 统计输入串中 1 的个数，并把该个数用 12 位二进制表示后输出
答案：B

这就是 CRC 的移位寄存器写法：末尾补的 12 个 0 相当于乘 212，然后用 1100000001111 做模 2（异或）除法，剩下的低 12 位就是余数。实测 3000 组随机输入，输出与 ($M\times 2^{12}$) mod2 1100000001111 全部吻合。注意是模 2 除法，不是整数取模。

第 21 题

若将第 16 行 if (a[i] == 0) continue; 删除，说法正确的是（）。
- A. 程序输出的结果不会改变
- B. 可能造成程序运行错误
- C. 程序能够正常输出一个 12 位 ‘0’/‘1’ 串，但是输出结果与输入的 s 无关
- D. 程序运行结束后，a[0] 的值一定为 0
答案：C

删掉 continue 后每一轮都要异或一次，而 gen[0] = 1 会把 a[i] 从 1 翻成 0、从 0 翻成 1，长除法的前提被破坏。此时 a[32]～a[43] 收到的异或次数只跟下标有关、跟输入无关，所以输出的 12 位串是固定的（实测 200 组随机输入输出完全相同）。D 错：a[0] 会被异或一次，取值由 s[0] 决定，不一定是 0。

（2）稀疏表求区间 GCD
```
#include <iostream>
using namespace std;
int n, m, a[100007], L, R, lg[100007], i, j, t, dp[100007][25], pw[25];
int gcd(int x, int y) {
    if (y == 0) return x;
    return gcd(y, x % y);
}
int main() {
    cin >> n >> m;
    for (i = 1; i <= n; i++) cin >> a[i];
    t = 0;
    pw[0] = 1;
    for (i = 1; i <= 24; i++) pw[i] = pw[i - 1] * 2;
    for (i = 1; i <= 100000; i++)
        if (pw[t + 1] > i) lg[i] = t;
        else t++, lg[i] = t;
    for (i = 1; i <= n; i++)
        dp[i][0] = a[i];
    for (j = 1; j <= lg[n]; j++)
        for (i = 1; i + pw[j] - 1 <= n; i++) {
            dp[i][j] = gcd(dp[i][j - 1], dp[i + pw[j - 1]][j - 1]);
        }
    for (i = 1; i <= m; i++) {
        cin >> L >> R;
        cout << gcd(dp[L][lg[R - L + 1]], dp[R - pw[lg[R - L + 1]] + 1][lg[R - L + 1]]) << endl;
    }
    return 0;
}
```
说明：保证 1 ≤ n ≤ 100000，每次查询满足 1 ≤ L ≤ R ≤ n，且数组 a 的元素均为正整数。

第 22 题

当 n = 5，a = {4, 2, 6, 3, 9}，且仅有一次查询 L = 2、R = 5 时，输出为 1。

答案：√

gcd(gcd(2,6), gcd(3,9)) = gcd(2,3) = 1。跑一遍程序确实输出 1。

第 23 题

当某次查询的区间长度为 1（即 L = R）时，这次查询的输出一定等于 a[L]。

答案：√

区间长度 1 时 k = lg[1] = 0，左右两段都退化成 a[L] 本身，gcd(a[L], a[L]) = a[L]。

第 24 题

任意一次查询的输出结果一定不小于该查询区间内的最小值。

答案：×

方向反了。gcd 一定整除区间内每一个数，所以它不可能大于最小值。例如区间 {2, 4}，最小值 2，输出 2；区间 {4, 6}，最小值 4，输出 2 < 4。

第 25 题

对于 j ≥ 1，数组 dp[i][j] 保存的是（）。
- A. 从 a[i] 开始连续 j 个数的最大公约数
- B. 从 a[i] 开始连续 $2^j$ 个数的最大公约数
- C. a[i] 与 a[j] 的最大公约数
- D. 从 a[1] 到 a[i] 的最大公约数
答案：B

转移式 dp[i][j] = gcd(dp[i][j-1], dp[i + 2^{j-1}][j-1]) 把长度 $2^j$ 劈成前后两半各 $2^{j-1}$ ，这是标准稀疏表。

第 26 题

若把一次求最大公约数的运算视为 O(1)，则第 17～22 行建表过程的时间复杂度为（）。
- A. Θ(n)
- B. $\Theta(n\log n)$
- C. $\Theta(n^2)$
- D. Θ(mn)
答案：B

j 一共 log n 层，每层扫一遍 i，共 O(n log n)。

第 27 题

设 x 为一次查询的区间长度（即 x = R − L + 1），则使得 lg[x] = 5 的 x 的取值范围是（）。
- A. [16, 31]
- B. [17, 32]
- C. [32, 63]
- D. [33, 64]
答案：C

那段预处理算出来的 lg[x] 就是 $\lfloor\log_2 x\rfloor$ 。等于 5 意味着 $2^5\le x<2^6$ ，即 32 ≤ x ≤ 63。

（3）树形 DP 求直径
```
#include <iostream>
using namespace std;
int n, fa[100007], f[100007], ans;
int main() {
    cin >> n;
    for (int i = 2; i <= n; ++i) {
        cin >> fa[i];
    }
    for (int i = n; i >= 2; --i) {
        if (f[fa[i]] + f[i] + 1 > ans) {
            ans = f[fa[i]] + f[i] + 1;
        }
        if (f[i] + 1 > f[fa[i]]) {
            f[fa[i]] = f[i] + 1;
        }
    }
    cout << ans << endl;
    return 0;
}
```
说明：输入第一行为结点个数 n，第二行为 n − 1 个整数，依次表示结点 2～n 的父结点编号，满足 2 ≤ n ≤ 100000 且 1 ≤ fa[i] < i，根结点为 1。

第 28 题

当 n = 5，fa[2]～fa[5] = {1, 2, 3, 4} 时，程序输出 4。

答案：√

这是一条链 1-2-3-4-5，直径 4 条边，程序输出 4。

第 29 题

程序输出前，f[1] 的值一定等于 ans 的值。

答案：×

f[1] 是以 1 为根往下能走多深（树高），ans 是整棵树的直径。直径不一定经过根，所以两者一般不相等。例如 n = 5、fa = {1, 1, 3, 3}，树是 1-2、1-3、3-4、3-5：f[1] 只有 2（走 1→3→4），而直径是 2-1-3-4 共 3 条边。

第 30 题

将第 10～12 行与第 13～15 行两个 if 语句的顺序交换后，程序的输出结果不受影响。

答案：×

交换后 f[fa[i]] 会先被更新，再拿更新后的值去算 ans，相当于把「从 fa[i] 往下走 i 这棵子树」这条链算了两遍，ans 会偏大。实测 5000 组随机树里 3970 组的输出发生了变化。例如 n = 9、fa = {1, 2, 3, 2, 2, 5, 4, 3}，原程序输出 5，交换后输出 8。

第 31 题

程序输出的 ans 表示的是（）。
- A. 树中距离最远的两个结点之间路径所经过的边数
- B. 根结点 1 到最远叶子结点之间路径所经过的边数
- C. 树中叶子结点的个数
- D. 所有结点的父结点编号之和
答案：A

枚举「以 fa[i] 为转折点、经过 i 这条分支」的所有路径取最长，就是树的直径（边数）。

第 32 题

当 n = 7，fa[2]～fa[7] = {1, 1, 2, 2, 3, 3} 时，输出为（）。
- A. 2
- B. 3
- C. 4
- D. 5
答案：C

结构是 1 连 2、3；2 连 4、5；3 连 6、7。最长路径 4-2-1-3-6，走过 4 条边。

第 33 题

当 n = 10，满足输出为 9 的合法输入种类数为（）。
- A. 0
- B. 9
- C. 256
- D. 512
答案：C

输出 9 说明 10 个点连成一条链。以结点 1 为根、且父编号小于子编号，必然是从 1 往两边各挂一条标号递增的链。把 {2,…,10} 这 9 个标号分到 1 的两侧，顺序就唯一确定了，共 $2^9=512$ 种分法；但左右两侧互换得到的是同一棵树，要除以 2，所以是 256 种。暴力枚举全部合法输入（9! = 362880 组）验证，正好 256 组输出 9。

三、完善程序（2 题 · 每小题 3 分 · 共 30 分）

（1）平衡路线

给定一张有 n 个顶点、m 条边的无向图，每条边带有符号 + 或 −。对于一条从顶点 s 到顶点 t 的路线，允许重复经过顶点和边，定义一条路线的权值如下：记 n+、n− 分别为经过的 + 边数和经过的 − 边数，则该路线的权值为 |n+ − n−|。

请计算从 s 到 t 的路线的最小权值。若不存在从 s 到 t 的路线，则输出 −1。

输入第一行为四个整数 n, m, s, t。接下来 m 行，每行给出两个整数 a, b 和一个字符 + 或 −，描述一条连接 a 与 b 的无向边及其符号。

数据满足 2 ≤ n ≤ $2\times 10^5$ ，1 ≤ m ≤ $4\times 10^5$ ，1 ≤ s, t ≤ n 且 s ≠ t，1 ≤ a, b ≤ n，可能出现重边。
```
#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 = ①;
        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 (②) {
        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] = ③;
                c[y] = c[x] ^ 1;
                q[tt++] = y;
            } else if (④)
                ok = 0;
        }
    }
    if (d[t] == -1) {
        std::cout << -1;
        return 0;
    }
    if (!p || !ng) {
        std::cout << d[t];
        return 0;
    }
    if (⑤) std::cout << 0;
    else std::cout << 1;
    return 0;
}
```
第 34 题

①处应填（）
- A. op[0] == '+' ? 0 : 1
- B. op[0] == '+'
- C. op[0] == '+' ? 1 : -1
- D. op[0] == '-' ? 1 : 0
答案：C

后面靠 w[i] > 0 和 w[i] < 0 分别标记「出现过 + 边」和「出现过 − 边」，所以 w 必须取 +1 / −1 两种符号。

第 35 题

②处应填（）
- A. hh < n
- B. tt < n
- C. hh <= tt
- D. hh < tt
答案：D

手写队列用 hh、tt 两个指针，队列非空的条件是 hh < tt。C 会多读一个空位；A、B 拿 n 当边界，队列没清空就可能提前退出。

第 36 题

③处应填（）
- A. d[y] + 1
- B. d[x] + 1
- C. d[x]
- D. d[x] - 1
答案：B

BFS 里首次访问到的距离就是最短路，d[y] = d[x] + 1。

第 37 题

④处应填（）
- A. c[y] == c[x]
- B. w[i] == 1
- C. c[y] != c[x]
- D. d[y] + 1 != d[x]
答案：A

c 是 BFS 层的奇偶染色。走到一个已访问的点 y 时，如果 c[y] == c[x] 说明这条边连接了两个同奇偶的点，图里有奇环，ok 置 0。

第 38 题

⑤处应填（）
- A. ok && c[s] == c[t]
- B. ok && c[s] != c[t]
- C. !ok || c[s] == c[t]
- D. !ok && c[s] != c[t]
答案：C

两种边都出现了，就有办法把权值压到 0 或 1。每条边的贡献都是 ±1，所以路线的符号和与走过的边数同奇偶；因为有 + 边也有 − 边，我们可以来回多走两条边把总量调 ±2，于是只要「符号和能取到偶数」就能压成 0。图里有奇环（!ok）时长度奇偶可以自由切换，直接能凑成 0；图是二分图时长度奇偶由 c 决定，c[s] == c[t] 就是偶数。所以条件是 !ok || c[s] == c[t]。用 2498 组随机小图对拍，这个组合全部正确，另外三个选项都被打掉。

（2）标准答案

有 n 名学生参加一次考试，考试共有 m 道选择题，每道题只有 A、B 两个选项。第 i 名学生的作答用一个长度为 m 的字符串 ai 表示。若最终公布的标准答案与该学生在某道题上的作答相同，则该学生得 1 分，否则不得分。记第 i 名学生最终得到的总分为 ri。

给定每名学生的目标分数 xi。现在需要构造一份标准答案，使 Σ|ri − xi| 尽可能大。

数据满足 1 ≤ n ≤ 20，1 ≤ m ≤ 300，0 ≤ xi ≤ m。

以下程序从枚举符号的角度处理 Σ|ri − xi|，把它写成更易优化的形式。对于非零整数 x，__builtin_ctzll(x) 返回 x 的二进制表示末尾连续 0 的个数，__builtin_popcountll(x) 返回 x 的二进制表示中 1 的个数。程序输出一组满足要求的标准答案。
```
#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] = ①;
    }
    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 = ②;
        ull d = g ^ lst;
        int k = ③;
        C -= ④;
        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 (⑤) res[j] = 'A';
        else res[j] = 'B';
    }
    cout << res << endl;
    return 0;
}
```
第 39 题

①处应填（）
- A. 2 * x[i] - m
- B. -m + 2 * x[i] + 1
- C. m - 2 * x[i]
- D. m + 2 * x[i]
答案：C

程序在最大化 2Σsi(ri − xi) = mn − 2Σxi + Σ|qj|，而 s 的初值全是 −1，所以 C 的初值要是 −Σc[i] = −mn + 2Σxi，即 c[i] = m − 2 * x[i]。填 A 的话符号正好反了，实测 120 例里 109 例拿不到最优。

第 40 题

②处应填（）
- A. mask | (mask >> 1)
- B. mask ^ (mask >> 1)
- C. mask & (mask >> 1)
- D. mask ^ ((mask >> 1) + 1)
答案：B

这是格雷码的标准写法 g = mask ^ (mask >> 1)，相邻两次只差一个二进制位，所以下面才能用 d = g ^ lst 找出「这一次翻了哪一位」。

第 41 题

③处应填（）
- A. __builtin_ctzll(d) + 1
- B. __builtin_popcountll(d)
- C. __builtin_ctzll(g)
- D. __builtin_ctzll(d)
答案：D

d 是 g 与上一次的异或，因为格雷码只差一位，d 一定是 2 的幂，取 ctz 得到的下标就是这次翻转的学生编号。

第 42 题

④处应填（）
- A. 2ll * s[k] * c[k]
- B. s[k] * c[k]
- C. 2ll * (s[k] - c[k])
- D. 2ll * c[k]
答案：A

s[k] 翻转时 Σsixi 变化 −2skxk、Σsi 变化 −2sk，合起来 C 的变化量正好是 −2 s[k] c[k]。

第 43 题

⑤处应填（）
- A. v >= (n & 1)
- B. v > (n & 1)
- C. v + (n & 1) >= 0
- D. v * (n & 1) >= 0
答案：A

对第 j 题，选 A 的贡献是 (S + v)/2、选 B 是 (S − v)/2，v ≥ 0 时选 A。又因为 v 和 n 同奇偶：n 为偶数时 v 也是偶数，v ≥ (n&1) 就是 v ≥ 0；n 为奇数时 v 是奇数，v ≥ 1 与 v ≥ 0 等价。所以填 A。填 B 在 n 为奇数、v = 1 时会错误地选 B；填 C 在 v = −1 时会选 A，都是错的。

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

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

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

ID

5283

时间

1000ms

内存

256MiB

难度

标签

递交数

已通过

上传者

椰子

1 条题解

2026 CSP-S 第一轮题解

答案速查

一、单项选择题（15 题 · 每题 2 分 · 共 30 分）

第 1 题 · 位运算

第 2 题 · 哈夫曼树

第 3 题 · 计数

第 4 题 · 错排

第 5 题 · 模运算

第 6 题 · 区间 DP

第 7 题 · 树状数组

第 8 题 · 拓扑排序

第 9 题 · 分治复杂度

第 10 题 · 树的直径与重心

第 11 题 · 强连通分量

第 12 题 · 卡特兰数

第 13 题 · 字符串前后缀

第 14 题 · 归并排序

第 15 题 · 快速幂

二、阅读程序（3 段 · 共 40 分）

（1）模 2 除法（CRC 求余）

第 16 题（1 分）

第 17 题

第 18 题

第 19 题

第 20 题

第 21 题

（2）稀疏表求区间 GCD

第 22 题

第 23 题

第 24 题

第 25 题

第 26 题

第 27 题

（3）树形 DP 求直径

第 28 题

第 29 题

第 30 题

第 31 题

第 32 题

第 33 题

三、完善程序（2 题 · 每小题 3 分 · 共 30 分）

（1）平衡路线

第 34 题

第 35 题

第 36 题

第 37 题

第 38 题

（2）标准答案

第 39 题

第 40 题

第 41 题

第 42 题

第 43 题

信息

还没有账户？

登录