【初赛出分】CSP-J/S 2026 初赛集中讨论帖

重要声明：洛谷更新讨论贴内容的时候，不会更新帖子发布时间，不存在 CSP 赛前泄题的情况。

CSP-J

题面

:::info[OCR 版本]

考生注意事项

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

一、单项选择题

共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项。

1

下列 C++ 数据类型中，能够精确存储 10^{18}+1 这个整数的是（ ）。

A. float　B. long long　C. double　D. int

2

十六进制数 2F5 转换为八进制数是（ ）。

A. 1364　B. 1635　C. 1405　D. 1365

3

执行下列 C++ 代码，输出是（ ）。

int a = 7, b = 3;
std::cout << a / b * b + a % b;

A. 9　B. 10　C. 7　D. 6

4

初始时栈为空，将 1、2、3、4 依次入栈，入栈过程中允许随时出栈。下列出栈序列中不可能出现的是（ ）。

A. 2，4，3，1
B. 1，2，3，4
C. 3，1，2，4
D. 1，4，3，2

5

一棵有 100 个结点的完全二叉树，其叶子结点个数是（ ）。

A. 49　B. 50　C. 64　D. 51

6

执行下列代码后 s 的值是（ ）。

int s = 0;
for (int i = 1; i <= 100; i++)
    if (i % 3 == 0 || i % 5 == 0)
        s += i;

A. 3048　B. 2733　C. 2318　D. 2418

7

上楼梯每步可上 1 级、2 级或 3 级，从地面（可视为第 0 级）走到第 8 级台阶共有多少种不同走法（ ）。

A. 44　B. 121　C. 149　D. 81

8

下图为 5\times5 网格，行号、列号均从 0 开始，# 为障碍，. 为可通行格：

S..#.
...#.
...#.
##..E
...#.

从 S 出发做广度优先搜索（BFS）：初始时把 S 入队；每次取出队首格子，按“上、下、左、右”（上 = 行号减 1，下 = 行号加 1，左 = 列号减 1，右 = 列号加 1）的顺序遍历它的四个相邻格子，越界、障碍或已访问的格子跳过，其余格子标记为已访问并入队。当 E 第一次入队时，已经入队过的格子（含 S 和 E）共有多少个（ ）。

A. 15　B. 12　C. 14　D. 13

9

满足 1\le n\le100 且 \gcd(n,60)=6 的正整数 n 共有多少个（ ）。

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

10

某国硬币面值为 1 元、4 元、6 元且数量不限，凑出 9 元最少需要多少枚（ ）。

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

11

执行下列代码，输出是（ ）。

int a[5] = {1, 3, 5, 7, 9};
int *p = a + 2;
*(p - 1) = p[0] + p[2];
p[1] = *(a + 1) - a[0];
cout << a[1] << "," << a[3];

A. 14,13　B. 8,13　C. 14,7　D. 14,2

12

在含 1000 个互不相同元素的升序数组中，用二分法查找给定值（返回元素位置或报告不存在），最坏情况下需要与数组元素比较多少次（ ）。

A. 500　B. 9　C. 11　D. 10

13

数组 a[1..n] 的前缀和数组 S（即 S[i]=a[1]+a[2]+\cdots+a[i]）满足 S[i]=3i^2+i。则 a[10] 的值是（ ）。

A. 252　B. 310　C. 58　D. 61

14

数轴上有 7 个点，坐标分别为 1、3、4、7、10、15、20。在数轴上选取一个整数坐标点 P，使 P 到这 7 个点的距离之和最小，这个最小距离和是（ ）。

A. 37　B. 42　C. 40　D. 38

15

一个无向图有 10 个顶点，其中 4 个顶点的度为 3，其余顶点的度均为 4，则该图的边数是（ ）。

A. 36　B. 18　C. 17　D. 20

二、阅读程序

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

（1）

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int x = 1, y = 1;
    while (n > 0) {
        if (n % 2 == 0) {
            ++x;
        } else {
            ++x;
            ++y;
        }
        n = n / 2;
    }
    cout << x << ' ' << y << endl;
    return 0;
}

识别注：上面第 12 行 ++y; 被手写笔迹遮盖较重，属于暂恢复内容；不是把旁边的手写修改视作题面。

以下问题均假定输入的 n 为不超过 2^{31}-1 的非负整数。

判断题

16. （1 分）当输入为 3 时，程序输出为 3 3。（ ）
17. 将第 11 行的 ++x; 删除后，程序输出的两个数一定相等。（ ）
18. 假设输入为非负整数，则程序输出的第一个数一定不小于第二个数。（ ）

单选题

19. 将第 7 行的 while (n > 0) 改为 while (n >= 0) 后，程序可能出现的问题是（ ）。

    A. 陷入死循环
    B. 输出结果比原来大
    C. 输出结果比原来小
    D. 输出结果不受影响

20. 当输入为 6 时，输出为（ ）。

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

21. 若输入 n 依次取遍 0,1,2,\ldots,2^{31}-1 中的所有整数，则程序输出的第二个数恰好为 2 的次数为（ ）。

    A. 16　B. 30　C. 31　D. 32

（2）

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
int a[100007], b[100007], c[100007], carry[100007];
string input_str;
int a_len, b_len;
int main() {
    cin >> input_str;
    a_len = input_str.size();
    for (int i = 0; i < a_len; i++) {
        a[i] = input_str[a_len - i - 1] - '0';
    }
    cin >> input_str;
    b_len = input_str.size();
    for (int i = 0; i < b_len; i++) {
        b[i] = input_str[b_len - i - 1] - '0';
    }
    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;
        }
    }
    for (int i = max(a_len, b_len); i >= 0; i--) {
        cout << c[i];
    }
    cout << endl;
    return 0;
}

本题输入的两个数均为非负整数，位数不超过 100000，可能包含前导零。

判断题

22. 当输入为 123 456 时，程序输出为 0579。（ ）
23. 假设输入的两个数均不含前导零，则程序输出的结果也一定不会含有前导零。（ ）
24. 将第 21 行改为 c[i] = a[i] + b[i]; 后，程序输出的结果一定比原来的结果小。（ ）

单选题

25. 当输入为 12345 678 时，输出为（ ）。

    A. 012923　B. 013023　C. 13023　D. 130230

26. 将第 22 行的 if (c[i] >= 10) 改为 if (c[i] > 10) 后，当输入为 95 15 时，输出为（ ）。

    A. 01010　B. 110　C. 140　D. 1410

27. 假设输入的两个数均为 n 位正整数（不含前导零），且它们的和小于 10^n，则程序输出的字符串一定满足（ ）。

    A. 第一个字符一定不为 '0'
    B. 长度一定为 n
    C. 长度一定为 n+1，且第一个字符为 '0'
    D. 长度可能为 n+2

（3）

#include <iostream>
using namespace std;
bool check_prime(int x) {
    if (x <= 1) return false;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}
int n;
void search_result(int x) {
    if (!check_prime(x)) return;
    if (x >= n) {
        cout << x << endl;
        return;
    }
    for (int i = 0; i <= 9; i++) {
        search_result(x * 10 + i);
    }
}
int main() {
    cin >> n;
    for (int i = 1; i <= 9; i++) search_result(i);
    return 0;
}

判断题

28. 当输入为 10 时，程序的输出共有 10 行。（ ）
29. 若输入的 n 不大于 5，则程序的输出中一定包含 5。（ ）
30. 若输入的 n 大于 10，将第 17 行的 for (int i = 0; i <= 9; i++) 改为 for (int i = 1; i <= 9; i += 2) 后，程序的输出结果一定不变。（ ）

单选题

31. 当输入为 24 时，程序输出的第 3 行为（ ）。

    A. 23　B. 29　C. 31　D. 239

32. 下列关于该程序输出的说法中，正确的是（ ）。

    A. 输出的数一定按照从小到大的顺序排列
    B. 随着输入 n 的增大，输出的行数一定不会增加
    C. 输出的数的个位数字只可能是 3 或 7
    D. 输出的每个大于等于 10 的数，十进制下删去它的末位数字后得到的数一定是质数

33. 当输入为 200 时，程序输出的行数为（ ）。

    A. 12　B. 13　C. 14　D. 15

三、完善程序

单选题，每小题 3 分，共计 30 分。

（1）进制减半

给定 n,m，再给定一个 mn 进制下的数 A，其各个数位上的数按照从高位到低位的顺序给出，请你将其转化为 n 进制，并同样按照从高位到低位的顺序输出。

输入的第一行依次为 n,m 和 A 的位数 d，接下来 d 个数 a_d,a_{d-1},\ldots,a_1 从高位到低位描述各个数位上的数。

数据满足 2\le n,m\le10，1\le d\le18，0\le A<2^{63}；对于所有 1\le i\le d，0\le a_i<mn。

以下程序按“逐位除以 n”的方法完成进制转换。请补全程序。

#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[0] = /* ② */;
        len++;
        for (int j = 0; j < len; j++)
            if (b[j] >= n) {
                b[j + 1] += /* ③ */;
                b[j] = /* ④ */;
                if (j + 1 == len) len++;
            }
    }
    while (/* ⑤ */) len--;
    for (int i = len - 1; i >= 0; i--)
        std::cout << b[i] << ' ';
    return 0;
}

34. ①处应填（ ）。

    A. b[j] * n
    B. b[j] * m
    C. b[j - 1] * n
    D. b[j - 1] * m

35. ②处应填（ ）。

    A. x * n　B. x　C. 0　D. m

36. ③处应填（ ）。

    A. b[j] / m　B. b[j] % n　C. b[j] % m　D. b[j] / n

37. ④处应填（ ）。

    A. b[j] / m　B. b[j] % n　C. b[j] % m　D. b[j] / n

38. ⑤处应填（ ）。

    A. len > 0 && b[len - 1] == 0
    B. len > 0 && b[0] == 0
    C. len > 1 && b[len - 1] == 0
    D. len > 1 && b[0] == 0

（2）平衡分割

给定一个长度为 n 的字符串，其中每个字符都是一个十六进制数位。例如，字符串 016A 表示十进制下的四个数 0,1,6,10。

现在请选择 k 个（k 是你选定的数）切分位置 p_1,p_2,\ldots,p_k，其中 1\le k<n，且 1\le p_1<p_2<\cdots<p_k<n。再令 p_0=0，p_{k+1}=n。

对于每个 0\le i\le k，计算第 p_i+1 个数到第 p_{i+1} 个数的平均值，记作 b_i。你的目标是使 b_0,b_1,\ldots,b_k 中最大值与最小值之差尽可能小，并输出这个最小值。

其中 2\le n\le20。输入字符串中的字符只可能是 0—9 或 A—F。本题假定字符采用 ASCII 编码。输出答案时保留小数点后 6 位。

以下程序通过递归枚举所有可能的连续分段方案。请补全程序。

#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 /* ① */; }

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 (/* ② */) {
        sum += a[r];
        double nwb = /* ③ */;
        split(/* ④ */);
    }
}

int main() {
    cin >> n >> s + 1;
    for (int i = 1; i <= n; ++i)
        a[i] = value(s[i]);
    split(/* ⑤ */);
    cout << fixed << setprecision(6) << ans;

39. ①处应填（ ）。

    A. c - (c < '9' ? '0' : 'A' - 10)
    B. c - (c < 'A' ? '0' : 'A' - 10)
    C. c - (c < 'A' ? 'A' - 10 : '0')
    D. c - (c < 'A' ? '0' : 'A' + 10)

40. ②处应填（ ）。

    A. int r = l + 1; r <= n; ++r
    B. int r = l; r < n; ++r
    C. int r = l; r <= n; r += 2
    D. int r = l; r <= n; ++r

41. ③处应填（ ）。

    A. sum / (r - l + 1) * 1.0
    B. sum * 1.0 / (r - l) + 1
    C. sum * 1.0 / (r - l + 1)
    D. (sum - a[r]) * 1.0 / (r - l + 1)

42. ④处应填（ ）。

    A. r + 1, cnt + (r < n), min(mnb, nwb), max(mxb, nwb)
    B. r + 1, cnt + (r <= n), min(mnb, nwb), max(mxb, nwb)
    C. r + 1, cnt + (r < n), max(mnb, nwb), min(mxb, nwb)
    D. r + 1, cnt + (r <= n), max(mnb, nwb), min(mxb, nwb)

43. ⑤处应填（ ）。

    A. 0, 0, 1e100, -1e100
    B. 0, 0, -1e100, 1e100
    C. 1, 0, -1e100, 1e100
    D. 1, 0, 1e100, -1e100 :::

答案（GPT-6 Astra）

:::info[答案]

答案速查

:::

CSP-S

题面

:::info[OCR 部分]

一、单项选择题

共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项。

1

执行下列代码后，cnt 的值是（ ）。

int x = 2026, cnt = 0;
while (x) {
    x &= x - 1;
    cnt++;
}

A. 6　B. 7　C. 11　D. 8

2

用权值 {1, 2, 3, 4, 5, 6, 7, 8} 构造哈夫曼树，其带权路径长度是（ ）。

A. 108　B. 96　C. 99　D. 102

3

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

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

4

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

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

5

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

11

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

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

12

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

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

13

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

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

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]\ge a[j] 的数对个数
D. 变为原来的一半

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

二、阅读程序

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

（1）

#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。（ ）
17. 程序运行结束后，数组 a 中下标从 0 到 31 的元素一定全部为 0。（ ）
18. 若将第 12—14 行（为 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] 是除数的最高位

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

    A. 将输入的 32 位串看成二进制数 M，输出 M 与 13 位二进制数 1100000001111 按位异或的结果
    B. 将输入串视为 32 位二进制数 M，在其后补 12 个 0（即计算 M\times2^{12}），再对它做模 2 除法求余数，并输出 12 位余数
    C. 对输入的 32 位串逐位取反并输出结果
    D. 统计输入串中 1 的个数，并把该个数用 12 位二进制表示后输出

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

    A. 程序输出的结果不会改变
    B. 可能造成程序运行错误
    C. 程序能够正常输出一个 12 位 '0' / '1' 串，但是输出结果与输入的 s 无关
    D. 程序运行结束后，a[0] 的值一定为 0

（2）

#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\le n\le100000，每次查询满足 1\le L\le R\le n，且数组 a 的元素均为正整数。

判断题

22. 当 n=5，a=\{4,2,6,3,3\}，且仅有一次查询 L=2,R=5 时，输出为 1。（ ）
23. 当某次查询的区间长度为 1（即 L=R）时，该次查询的输出一定等于 a[L]。（ ）
24. 任意一次查询的输出结果一定不小于该查询区间内的最小值。（ ）

单选题

25. 对于 j\ge1，数组 dp[i][j] 保存的是（ ）。

    A. 从 a[i] 开始连续 j 个数的最大公约数
    B. 从 a[i] 开始连续 2^j 个数的最大公约数
    C. a[i] 与 a[j] 的最大公约数
    D. 从 a[1] 到 a[i] 的最大公约数

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

    A. \Theta(n)　B. \Theta(n\log n)　C. \Theta(n^2)　D. \Theta(mn)

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

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

（3）

#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\le n\le10000 且 1\le fa[i]<i，根结点为 1。

判断题

28. 当 n=5，fa[2]\sim fa[5]=\{1,2,3,4\} 时，程序输出 4。（ ）
29. 程序输出前，f[1] 的值一定等于 ans 的值。（ ）
30. 将第 10—12 行与第 13—15 行两个 if 语句的顺序交换后，程序输出结果不受影响。（ ）

单选题

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

    A. 树中距离最远的两个结点之间路径所经过的边数
    B. 根结点 1 到最远叶子结点之间路径所经过的边数
    C. 树中叶子结点的个数
    D. 所有结点的父结点编号之和

32. 当 n=7，fa[2]\sim fa[7]=\{1,1,2,2,3,3\} 时，输出为（ ）。

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

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

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

三、完善程序

单选题，每小题 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\le n\le2\times10^5，1\le m\le4\times10^5，1\le s,t\le n 且 s\ne t，1\le a,b\le n，可能出现重边。

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

#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

35. ②处应填（ ）。

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

36. ③处应填（ ）。

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

37. ④处应填（ ）。

    A. c[y] == c[x]
    B. w[i] == 1
    C. c[y] != c[x]
    D. d[y] + 1 != d[x]

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]

（2）标准答案

给定 n 名学生参加一场考试，考试共有 m 道选择题，每道题只有 A、B 两个选项。

第 i 名学生的作答为一个长度为 m 的字符串。若最终公布的标准答案与该学生在某道题上的作答相同，则该学生在这道题上得 1 分，否则不得分。记第 i 名学生最终得到的总分为 r_i。

每名学生还有一个预期得分 x_i。现在需要构造一份标准答案，使

尽可能大。

数据满足 1\le n\le18，1\le m\le300，0\le x_i\le m。

提示：可以换一个角度处理 \sum_{i=1}^{n}|r_i-x_i|，把它写成更易优化的形式；对正整数 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]

40. ②处应填（ ）。

    A. mask | (mask >> 1)
    B. mask ^ (mask >> 1)
    C. mask & (mask >> 1)
    D. mask ^ ((mask >> 1) + 1)

41. ③处应填（ ）。

    A. __builtin_ctzll(d) + 1
    B. __builtin_popcountll(d)
    C. __builtin_ctzll(g)
    D. __builtin_ctzll(d)

42. ④处应填（ ）。

    A. 2ll * s[k] * c[k]
    B. s[k] * c[k]
    C. 2ll * (s[k] - c[k])
    D. 2ll * c[k]

43. ⑤处应填（ ）。

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

:::

答案

:::info[答案]

单项选择题

阅读程序

完善程序

:::

广告

基础组（面向 CSP-J）：
https://class.luogu.com.cn/course/yugu26ajc
提高组（面向 CSP-S、NOIP）：
https://class.luogu.com.cn/course/yugu26atg

洛谷网校秋令营是面向已经掌握算法的学员。通过讲题和模拟增加经验，分别提升 CSP-J 和 CSP-S 组应试能力。

每个组别计划包括：

• 4 次专题直播讲座，介绍解题策略和题目选讲。
• 2 次全真模拟模拟比赛
• 1 次线上模拟比赛及讲评
• 考前必刷题单

点击下方课程图报名对应课程。多组别同时报名享有优惠！已经报名今年初赛课程，继续报名秋令营，优惠 100 元.

注意：

• 基础组包含于 2026 基础-提高衔接计划 A 组中。
• 提高组包含于 NOIP 冲刺计划【2026 / 后期】中。

已经报名衔接计划或者NOIP计划的同学，无需报名对应包含的秋令营课程。