2026 CCF 非专业级别软件能力认证第一轮（CSP-S1）提高级 C++ 语言试题

认证时间：2026 年 9 月 19 日 14:30 ~ 16:30

考生注意事项：

• 试题共 11 页，答题纸共有 1 页，满分 100 分。请在答题纸上作答，写在试题纸上的一律无效。
• 不得使用任何电子设备（如计算器、手机、电子词典、电子手表等）或查阅任何书籍资料。

一、单项选择题（共 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，cnt 统计 1 的个数。2026 = 11111101010₂，共 8 个 1。

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。带权路径长度等于各次合并权值之和：3+6+9+12+15+21+36 = 102。

3.把 1 到 1000 的所有整数按十进制写出，数字“1”总共出现了多少次（ ）

A. 300　　B. 271　　C. 301　　D. 320

【答案】C

【解析】 000–999 共 1000 个三位串，百/十/个位上 1 各出现 100 次，共 300 次；1000 再贡献 1 次。合计 301。

4.将 5 封信随机装入 5 个写好地址的信封（每封一个），恰好有 2 封装对的方案数是（ ）

A. 44　　B. 24　　C. 10　　D. 20

【答案】D

【解析】 选出装对的 2 封：C(5,2)=10；其余 3 封必须全部装错（错排 D₃=2）。共 10×2=20。

5.3^2026 mod 100 的值是（ ）

A. 29　　B. 9　　C. 43　　D. 81

【答案】A

【解析】 3^20 ≡ 1 (mod 100)，2026 = 20×101+6，故 3^2026 ≡ 3^6 = 729 ≡ 29 (mod 100)。

6.有 5 堆石子排成一行，重量依次为 4, 1, 3, 2, 5。每次只能把相邻的两堆合并成一堆，代价为这两堆重量之和。将所有石子合并成一堆的最小总代价是（ ）

A. 36　　B. 35　　C. 34　　D. 33

【答案】C

【解析】 区间 DP：dp[l][r] = min(dp[l][k]+dp[k+1][r]) + sum(l,r)。计算得 dp[1][5] = min(24, 20, 19, 19) + 15 = 34。一种最优方案：并(1,3)代价 4 → 与 4 并代价 8 → 并(2,5)代价 7 → 最后两堆合并代价 15，合计 34。

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

A. 3 和 4　　B. 4 和 4　　C. 3 和 5　　D. 4 和 3

【答案】A

【解析】 查询：11→10→8→0，访问 3 个下标；修改：3→4→8→16→32（越界停），访问 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 种；孤立点 4 可插入 4 个位置，共 2×4=8。

9.某分治算法满足 T(n) = T(n/3) + T(2n/3) + Θ(n)，T(1) = O(1)，则 T(n) 是（ ）

A. Θ(n log n)　　B. Θ(n²)　　C. Θ(n^1.5)　　D. Θ(n)

【答案】A

【解析】 递归树每层的子问题规模之和恒为 n，每层代价 Θ(n)；最长分支按 2n/3 收缩，深度 Θ(log n)。故 T(n)=Θ(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 与 8：9-5-2-1-3-6-7-8，共 7 条边。删去结点 1 后两连通块各 4 个结点（≤9/2），故重心为 1；删 2 或 3 都会留下 5 个结点的连通块。

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

A. 7　　B. 6　　C. 4　　D. 3

【答案】C

【解析】 缩点 DAG 转强连通至少加 max(入度 0 点数, 出度 0 点数) = max(3, 4) = 4 条边（一条新边可同时补一个入口和一个出口）。

12.含 6 个结点的不同形态的二叉树共有多少棵（结点不带标号，区分左右子树）（ ）

A. 42　　B. 429　　C. 132　　D. 720

【答案】C

【解析】 即卡特兰数 C₆ = 132。

13.字符串 S = "ababaabab"，其所有既是真前缀又是真后缀的子串（非空）的长度之和是（ ）

           A. 4　　B. 6　　C. 7　　D. 5

【答案】B

【解析】 由 KMP 前缀函数，border 链为 4 → 2 → 0。长度 4（"abab"）与长度 2（"ab"）符合，之和为 6。

14.用归并排序统计逆序对，合并部分的核心代码为：

// 归并 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[i] <= a[j] 改成 a[i] < a[j]，则 ans 统计出的结果是（ ）

A. 完全不变　　            B. 变为原来的两倍　　

C. 变为满足 i < j 且 a[i] >= a[j] 的数对个数　　D. 变为原来的一半

【答案】C

【解析】 改成严格小于后，相等的元素对也进入 else 分支被计数，即统计 i<j 且 a[i]≥a[j] 的数对（每一对下标有序的元素恰在归并树某层被统计一次）。反例：[1,1] 原来计 0，修改后计 1。

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

【解析】 即 2^100 mod 1000。反复平方法：2^4≡16，2^8≡256，2^16≡536，2^32≡296，2^64≡616；2^100 ≡ 616×296×16 ≡ 336×16 = 5376 ≡ 376。

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

阅读程序（1）

#include#includeusing 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 时第 16 行始终 continue，无任何异或，输出 a[32..43] 即 12 个 0。

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

【答案】√

【解析】 处理第 i 位时若 a[i]=1 则与 gen[0]=1 异或变为 0；之后的循环起点都大于 i，不再访问第 i 位。故前 32 位最终全 0。

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

【答案】×

【解析】 a 是全局数组，编译期已零初始化，a[32..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] 共 13 个元素；第 18 行 gen[j] 与 a[i+j] 对齐，gen[0] 对应当前最高位，即除数 1100000001111 的最高位。

20.该程序实现的功能，最准确的说法是（ ）。

A. 将输入的 32 位串看成二进制数 M，输出 M 与 13 位二进制数 1100000001111 按位异或的结果

B. 将输入串视为 32 位二进制数 M，在其后补 12 个 0（即计算 M × 2^12），再对它用 1100000001111 作模 2 除法求余数，并输出 12 位余数

C. 对输入的 32 位串逐位取反并输出结果

D. 统计输入串中 1 的个数，并把该个数用 12 位二进制表示后输出

【答案】B

【解析】 程序是 CRC 校验：读入 32 位后补 12 个 0，逐位做模 2 多项式除法（借位用异或实现），最后输出低 12 位余数。

21.若将第 16 行 if (a[i] == 0) continue; 删除，说法正确的是（ ）。

A. 程序输出的结果不会改变

B. 可能造成程序运行错误

C. 程序能够正常输出一个 12 位 '0'/'1' 串，但是输出结果与输入的 s 无关

D. 程序运行结束后，a[0] 的值一定为 0

【答案】C

【解析】 删除后每一步的异或位置与次数完全固定（不再由 a[i] 决定），输出段 a[32..43] 初值全 0，只接受固定异或，故输出与 s 无关。无越界（最大下标 43），不会运行错误；a[0] 会被翻成 s[0]^1，不一定为 0。

阅读程序（2）

#includeusing 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。（ ）

【答案】√

【解析】 查询 {2,6,3,9} 的 gcd：lg[4]=2，取 dp[2][2]=gcd(2,6,3,9)=1，两块重叠不影响，输出 1。

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

【答案】√

【解析】 lg[1]=0，两块均为 dp[L][0]=a[L]，gcd(a[L],a[L])=a[L]。

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

【答案】×

【解析】 区间 gcd 必整除区间内每个数，故 gcd ≤ 区间最小值，方向相反。反例 {2,6}：gcd=2 < 6。

单选题

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

【解析】 转移把两个长度 2^(j-1) 的相邻块合并，故 dp[i][j] 覆盖从 a[i] 起 2^j 个数。

26.若把一次求最大公约数的运算视为 O(1)，则第 17~22 行建表过程的时间复杂度为（ ）。

          A. Θ(n)　　B. Θ(n log n)　　C. Θ(n²)　　D. Θ(mn)

【答案】B

【解析】 j 共 Θ(log n) 层，每层 Θ(n) 个起点，每层转移 O(1)：Θ(n log n)。与 m 无关。

27.设 x 为一次查询的区间长度（即 x = R - L + 1），则使得 lg[x] = 5 的 x 的取值范围是（ ）。

A. [16, 31]　　B. [17, 32]　　C. [32, 63]　　D. [33, 64]

【答案】C（本卷代码为 pw[t+1] > i）

【解析】 按本卷代码 if (pw[t+1] > i)：lg[x]=⌊log₂x⌋，lg[x]=5 ⟺ 32 ≤ x ≤ 63。

阅读程序（3）

#includeusing 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，逆序传递得 ans = 4（= 端点 1 到 5 的边数）。

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

【答案】×

【解析】 f[1] 是根到最远后代的距离，ans 是直径。反例 n=3，fa={1,1}（星形）：f[1]=1，ans=2。

30.将第 1012 行与第 1315 行两个 if 语句的顺序交换后，程序的输出结果不受影响。（ ）

【答案】×

【解析】 反例 n=2，fa[2]=1：交换后先令 f[1]=1 再算 ans=1+0+1=2，一条边的树输出 2，结果改变（同一分支被重复计入）。

单选题

31.程序输出的 ans 表示的是（ ）。

A. 树中距离最远的两个结点之间路径所经过的边数　　

B. 根结点 1 到最远叶子结点之间路径所经过的边数

C. 树中叶子结点的个数　　

D. 所有结点的父结点编号之和

【答案】A

【解析】 f[i] 记录 i 向下子树的最长距离；处理 i 时用“父结点已存的最长分支 + 当前分支 + 1”更新 ans，取遍所有转折点后即树的直径（边数）。

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 条边。程序模拟：处理完 3 的子树后 f[1]=2、ans=2；处理结点 2 时 ans = f[1]+f[2]+1 = 2+1+1 = 4。

33.当 n = 10，满足输出为 9 的合法输入种类数为（ ）。

A. 0　　B. 9　　C. 256　　D. 512

【答案】C

【解析】 输出 9 即直径为 9 = n−1，整棵树必须是一条链，但根 1 不必在链端。按编号 1~10 依次加入：结点 2 只能接 1（1 种）；之后每个新结点必须接到当前链的两个端点之一，否则产生度为 3 的分叉（各 2 种）。共 1×2⁸ = 256 种。

三、完善程序（单选题，每小题 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×10⁵，1 ≤ m ≤ 4×10⁵，1 ≤ s, t ≤ n 且 s ≠ t，1 ≤ a, b ≤ n，可能出现重边。

以下程序通过 BFS 求出最小权值。请补全程序。

#includeconstexpr 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 区分两种符号，故 '+' 边记 +1，'-' 边记 −1。

35.②处应填（ ）

A. hh < n　　B. tt < n　　C. hh <= tt　　D. hh < tt

【答案】D

【解析】 入队 q[tt++]、出队 q[hh++]，有效区间为 [hh, tt)，非空条件是 hh < tt；图可能不连通，与 n 比较无意义。

36.③处应填（ ）

A. d[y] + 1　　B. d[x] + 1　　C. d[x]　　D. d[x] - 1

【答案】B

【解析】 BFS 记录最少边数：y 由 x 走一步到达，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

【解析】 首次访问时令相邻点异色；若 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

【解析】 两种符号都有时：D = n⁺−n⁻ 与路线长度同奇偶。非二分图（!ok）可借奇环改变奇偶性 → 0；二分图中 s、t 同色（即 d[t] 为偶）→ 0，异色 → 1。故条件为 !ok || c[s]==c[t]。

（2）标准答案

给定 n 名学生参加一次考试，考试共有 m 道选择题，每道题只有 A、B 两个选项。第 i 名学生的作答用一个长度为 m 的字符串 aᵢ 表示。若最终公布的标准答案与该学生在某道题上的作答相同，则该学生在这道题上得 1 分，否则不得分。记第 i 名学生最终得到的总分为 rᵢ。每名学生还有一个预期得分 xᵢ。现在需要构造一份标准答案，使 Σ|rᵢ − xᵢ| 尽可能大。

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

提示：可以换一个角度处理 Σ|rᵢ − xᵢ|，把它写成更易优化的形式；对非零整数 x，__builtin_ctzll(x) 返回 x 的二进制表示末尾连续 0 的个数；__builtin_popcountll(x) 返回 x 的二进制表示中 1 的个数。

程序输出一组满足要求的标准答案。请补全程序。

#include#include#include#includeusing namespace std;typedef long long ll;typedef unsigned long long ull;int main() {    int n, m;    cin >> n >> m;    vector x(n), c(n);    for (int i = 0; i < n; i++) {        cin >> x[i];        c[i] = ____①____;    }    vector a(n);    for (int i = 0; i < n; i++)        cin >> a[i];    vector s(n, -1);    vector 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

【解析】 设 v_ij 为学生作答（A=+1, B=−1），b_j 为标准答案，则 2(r_i−x_i) = (m−2x_i) + Σ v_ij·b_j。故 c[i] = m − 2x[i]，目标值同乘 2 不影响最优。

40.②处应填（ ）

A. mask | (mask >> 1)　　B. mask ^ (mask >> 1)

C. mask & (mask >> 1)　　D. mask ^ ((mask >> 1) + 1)

【答案】B

【解析】 二进制转格雷码 mask^(mask>>1)：相邻两个状态恰好只有一位不同（保证 d 只有一位 1），且 0~2^n−1 各出现一次。

41.③处应填（ ）

A. __builtin_ctzll(d) + 1　　B. __builtin_popcountll(d)

C. __builtin_ctzll(g)　　D. __builtin_ctzll(d)

【答案】D

【解析】 相邻格雷码只差一位，d = g^lst 恰有一个二进制位为 1，ctzll(d) 即被翻转的学生下标（从 0 开始）。

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] 翻转后 C 中第 k 项的贡献由 s[k]·c[k] 变为 −s[k]·c[k]，相差 −2·s[k]·c[k]；代码写的是 C -= ...，故填 2ll*s[k]*c[k]（此时 s[k] 仍是旧值，更新完成后第 48 行才翻转）。

43.⑤处应填（ ）

A. v >= (n & 1)　　B. v > (n & 1)

C. v + (n & 1) >= 0　　D. v * (n & 1) >= 0

【答案】A

【解析】 v 是 n 个 ±1 之和，与 n 同奇偶。第 j 题选 A 的贡献为 v，选 B 为 −v：v>0 必选 A，v=0 平局任选。n 偶时 v≥0 即 v≥(n&1)=0；n 奇时 v≥1 即 v>0。A 恰好等价于正确判断。B 在 n 奇时会漏掉 v=1；C、D 均有反例。