CSP-S 2026 第一轮题解

gcx34580 · 2026-09-20 22:38:38 · 算法·理论

这个蒟蒻 的 S 组第一轮炸掉了，于是一怒之下写了这个题解

是的糖到写第一轮题解的也来了

题解中可能掺杂了一些个人主观评价

由本人独自完成初稿编写，使用了 DeepSeek 与 GPT 5.6 Sol 进行检验

单项选择

T1

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

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

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

答案：D

解析：

很容易观察到，x-1 相较于 x 只会改变 lowbit(x) 后的位置，所以 x&=x-1 实际上是删除 x 的末尾 1，原代码等价于求 x 二进制下 1 的个数。计算得 (2026)_{10}=(111 1110 1010)_2，有 8 个 1，故选择 D。

T2

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

答案：D

解析：

哈夫曼树合并策略是每次取权值最小的两个合并，最终带权路径长度为所有非叶子节点权值和。 如下图所示，标 a 的是叶子节点，标 b 的是非叶子节点。最终 WPL = 3 + 6 + 9 + 12 + 15 + 21 + 36 = 102。

T3

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

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

答案：C

解析：

考虑 [1,999] 中的数，显然可以依次固定百、十、个位为 1，其他两位有 10 \times 10=100 种取值，再加上 1000 中有一个 1，答案为 3 \times 100 + 1=301，不重不漏。

T4

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

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

答案：D

解析：

考虑已经确定其中 3 封装错，则方案数为错排数 D_3=2。 再考虑从 5 封信中选出要装错的 3 封，则方案数为组合数 C_5^3=10。 根据乘法原理，答案为 2 \times 10 = 20。

T5

• 3^2 \equiv 9 \pmod{100}
• 3^3 \equiv 27 \pmod{100}
• 3^4 \equiv 81 \pmod{100}
• 3^5 \equiv 43 \pmod{100}
• 3^6 \equiv 29 \pmod{100}
• ...
• 3^{20} \equiv 1 \pmod{100}
• 3^{21} \equiv 3 \pmod{100}

也就是说，3 在模 100 意义下的循环节长度是 20，即每 20 个数重复一次。这就比算 2026 次好多了。 于是我们得到 2026 \equiv 6 \pmod{20}，即3^{2026} 应该出现在循环节第 6 位，为 29。

T6

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

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

答案：C

解析：

经典的区间 DP。 让我们手动推演一下最优的合并过程： 初始状态：4, 1, 3, 2, 5

1. 先合并 1 和 3，代价为 1+3=4。剩余：4, 4, 2, 5，累计代价 = 4
2. 合并 4 和 4（原4和刚合成的4），代价为 4+4=8。剩余：8, 2, 5，累计代价 =4 + 8 = 12
3. 合并 2 和 5，代价为 2+5=7。剩余：8, 7，累计代价 =12 + 7 = 19
4. 合并 8 和 7，代价为 8+7=15。剩余：15，累计代价 =19 + 15 = 34

考场手推应该不难。

T7

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

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

答案：A

解析：

树状数组的操作与二进制中最低位 1(lowbit) 密切相关。

回顾一下代码，很容易能推出操作：

void add(int x,int v){
    for(int i=x;i<=n;i+=lowbit(i)){
        c[i]+=v;
    }
}
int query(int x){
    int res=0;
    for(int i=x;i!=0;i-=lowbit(i)){
        res+=c[i];
    }
    return res;
}

1. 查询前缀和 sum(11)： 查询过程是不断减去 lowbit(i) 直到 i 为 0。

   • 11 的二进制是 1011，lowbit 是 1，11 - 1 = 10
   • 10 的二进制是 1010，lowbit 是 2，10 - 2 = 8
   • 8 的二进制是 1000，lowbit 是 8，8 - 8 = 0 访问的下标依次为：11, 10, 8。总共访问 3 个下标。

2. 单点修改 add(3, x)： 修改过程是不断加上 lowbit(i) 直到超过数组长度 n=16。

   • 3 的二进制是 0011，lowbit 是 1，3 + 1 = 4
   • 4 的二进制是 0100，lowbit 是 4，4 + 4 = 8
   • 8 的二进制是 1000，lowbit 是 8，8 + 8 = 16
   • 16 的二进制是 10000，lowbit 是 16，16 + 16 = 32 (>16$，停止) 访问的下标依次为：3, 4, 8, 16。总共访问 4 个下标。

所以分别是 3 和 4，选 A。

T8

已知有向无环图 G 顶点集为 {1, 2, 3, 4}，边集为 {(1,2), (1,3)}，顶点 4 与任何顶点均不相邻。该图不同的拓扑序共有多少种（ ）。

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

答案：B

解析：

我们先不考虑顶点4，只看子图 {1, 2, 3} 的拓扑排序。

• b$ 为偶数，$a = 2^2 = 4 \pmod{1000}$，$b=50
• b$ 为偶数，$a = 4^2 = 16 \pmod{1000}$，$b=25
• b$ 为奇数，$r = 1 \times 16 = 16 \pmod{1000}$，$a = 16^2 = 256 \pmod{1000}$，$b=12
• b$ 为偶数，$a = 256^2 = 65536 \equiv 536 \pmod{1000}$，$b=6
• b$ 为偶数，$a = 536^2 = 287296 \equiv 296 \pmod{1000}$，$b=3
• b$ 为奇数，$r = 16 \times 296 = 4736 \equiv 736 \pmod{1000}$，$a = 296^2 = 87616 \equiv 616 \pmod{1000}$，$b=1
• b$ 为奇数，$r = 736 \times 616 = 453376 \equiv 376 \pmod{1000}$，$a = 616^2 = 379456 \equiv 456 \pmod{1000}$，$b=0
• 循环结束，返回 r = 376。

故选 B。 也可参考 T5 解法利用循环节规律求解。不过都给你快速幂算法了为什么不用呢

阅读程序

T1

#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' 字符串。

解析

本程序实现的是 CRC（循环冗余校验） 算法。

1. 数据准备：输入一个 32 位的 '0'/'1' 字符串 s，将其存入数组 a 的前 32 位，并在其后补 12 个 0（相当于将原数据左移 12 位，即乘以 2^{12}）。
2. 生成多项式：数组 gen 共有 13 个元素，对应一个 13 位的二进制除数 1100000001111。其中 gen[0] 是最高位（对应 x^{12}），gen[12] 是最低位（对应 x^0）。
3. 模 2 除法：核心循环遍历 a[0] 到 a[31]。如果当前位 a[i] 为 1，则用 gen 对其进行异或（模 2 减法），以消去当前的最高位。本质上就是做模 2 除法。
4. 输出：输出 a[32] 到 a[43]，即模 2 除法得到的 12 位余数。

判断题：

Q1：当输入为 32 个 '0' 时，程序输出 12 个 0。（ ）

• 答案：正确（T）
• 解析：a[0] 到 a[31] 全为 0。核心循环中 if (a[i] == 0) continue; 会一直执行，不进行任何异或操作。a[32] 到 a[43] 保持初始化的 0，因此输出 12 个 0。

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

• 答案：正确（T）
• 解析：当循环处理到下标 i 时，a[i] 如果是 1，则通过 a[i] ^= gen[0]（gen[0] 为 1）必然会被置为 0；如果是 0，则跳过，保持为 0。 由于后续的操作只会修改下标大于 i 的元素（j >= 0，i+j >= i），不会再回头修改 a[i]，因此a[0] 到 a[31] 最终一定全部为 0。

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

• 答案：错误（F）
• 解析：数组 a 定义在 main 函数外部，属于全局变量。全局变量在程序启动时会默认初始化为 0。 因此，即使删除了显式补 0 的循环，a[32] 到 a[43] 的初始值仍然是 0，程序的输出结果不会改变。

单选题：

Q4：关于第 6 行定义的数组 gen，下列说法正确的是（ ）。

A. gen 共有 12 个元素，表示一个 12 位的除数 B. gen 共有 13 个元素，表示一个 13 位的被除数 C. gen 共有 13 个元素，其中 gen[0] 是除数的最高位 D. gen 共有 13 个元素，其中 gen[12] 是除数的最高位

• 答案：C
• 解析：
  • gen 定义为 int gen[13]，共有 13 个元素。
  • 在 CRC 算法中，最高位对应多项式最高次项。gen[0] = 1 是最高位，gen[12] = 1 是常数项（最低位）。因此 C 选项“共有 13 个元素，其中 gen[0] 是除数的最高位”正确。

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

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

• 答案：B
• 解析：上面代码解析部分已经分析过，不再赘述。

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

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

• 答案：C
• 解析：删除该判断后，无论 a[i] 是 0 还是 1，都会无条件执行异或操作。这会导致 a 数组的最终状态只取决于循环执行的次数（固定为 32 次）和 gen 数组的内容，而与输入的 s 完全无关，变成了一个固定值。因此 C 选项正确。

T2

#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 的元素均为正整数。

解析

本程序实现的是区间最大公约数查询，使用了 ST 表算法。 代码的核心逻辑在于倍增预处理 dp[i][j]，表示从下标 i 开始，长度为 2^j 的连续区间的最大公约数。查询时，将区间拆分为两个长度为 2^k 的重叠子区间进行合并。

关键陷阱：第 12—15 行的 lg 数组递推逻辑是错误的（与标准 ST 表不同）。 标准 ST 表应该满足 lg[2] = 1，即下取整，但该代码中的条件 pw[t + 1] >= i 会导致：

• lg[1] = 0
• lg[2] = 0
• lg[3..4] = 1
• lg[5..8] = 2
• lg[9..16] = 3
• lg[17..32] = 4
• lg[33..64] = 5
• \dots

lg[64]=5说是 即 lg[x] = t 当且仅当 2^t < x \le 2^{t+1}。这个错误的 lg 数组会导致查询时选取的块比标准 ST 表略小，但也能覆盖整个区间。

CCF 真神了，这不比去年 have no egg 搞

判断题

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

• 答案：正确（T）

• 解析： 查询区间 [2, 5]，对应元素为 \{2, 6, 3, 3\}。区间长度 x = 5 - 2 + 1 = 4。根据前述 lg 数组逻辑，lg[4] = 1。 查询代码：gcd(dp[2][1], dp[5 - 2^1 + 1][1])，即 gcd(dp[2][1], dp[4][1])。 dp[2][1] 为 \gcd(a[2], a[3]) = \gcd(2, 6) = 2。 dp[4][1] 为 \gcd(a[4], a[5]) = \gcd(3, 3) = 3。 最终结果 \gcd(2, 3) = 1。输出为 1，正确。

  也可直接手动求区间 \gcd，答案与刚才相同。

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

• 答案：正确（T）
• 解析：区间长度 x = 1，lg[1] = 0。查询代码：gcd(dp[L][0], dp[R - 2^0 + 1][0])。因为 R = L，所以 dp[R - 1 + 1][0] = dp[L][0]。而 dp[L][0] = a[L]。最终计算的是 \gcd(a[L], a[L]) = a[L]。正确。

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

• 答案：错误（F）
• 解析：区间查询的结果是最大公约数（GCD）。由于 GCD 一定能整除区间内的每一个数，所以 GCD 一定 \le 区间内的最小值。例如区间 \{4, 6\}，最小值是 4，GCD 是 2，2 小于 4。所以“不小于”的说法是错误的，应该是“不大于”。

单选题

Q4 对于 j \ge 1，数组 dp[i][j] 保存的是（ ）。

• 答案：B
• 解析：根据代码 dp[i][j] = gcd(dp[i][j - 1], dp[i + pw[j - 1]][j - 1])，dp[i][j] 维护的是从下标 i 开始，长度为 2^j 的区间的最大公约数。pw[j] 恰好为 2^j。故选 B。

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

• 答案：B
• 解析：代码包含两重循环：

  for (j = 1; j <= lg[n]; j++) {
      for (i = 1; i + pw[j] - 1 <= n; i++) {
          // O(1) gcd
      }
  }

  外层循环 j 执行约 \log_2 n 次，内层循环 i 执行约 n 次。因此总时间复杂度为 \Theta(n \log n)。选 B。

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

• 答案：D
• 解析：根据题目代码中 lg 数组的生成逻辑：
  • 当 t = 4 时，要求 pw[5] = 32 >= i，此时 lg[i] = 4（对应 x \in [17, 32]）。
  • 当 i = 33 时，条件 32 >= 33 失败，t 增加为 5，lg[33] = 5。
  • 此时条件变为 pw[6] = 64 >= i。
  • 因此当 x \in [33, 64] 时，lg[x] 保持为 5。当 x = 65 时，lg[65] 将变为 6。
• 所以取值范围是 [33, 64]，选 D。

啊啊啊啊啊CCF还我3分

这个故事告诉我们一定要以代码为准。QAQ

T3

#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\sim n 的父结点编号，满足 1\le fa[i]<i，根结点为 1。

解析

由于题目保证 fa[i]<i，所以每个结点的父结点编号都小于自己的编号。反过来说，一个结点的所有子结点编号一定大于该结点。 因此，程序按照：

for (int i = n; i >= 2; --i)

从大到小处理结点时，处理结点 i 之前，它的所有子结点都已经处理完毕。

f[i] 表示从结点 i 出发，向其子树中的叶子结点延伸，最多能经过多少条边。也就是以 i 为根的子树高度。 更新语句：

if (f[i] + 1 > f[fa[i]]) {
    f[fa[i]] = f[i] + 1;
}

表示从父结点 fa[i] 经过一条边到达 i，再沿着 i 的最长路径继续向下。因此 f[fa[i]]=\max(f[fa[i]],f[i]+1)。

ans 在更新 f[fa[i]] 之前执行：

ans = max(ans, f[fa[i]] + f[i] + 1);

此时 f[i] + 1 是从父结点 fa[i] 经过 i 向下延伸的最长路径，f[fa[i]] 是此前处理过的其他子树提供的最长路径。 把这两条路径在父结点处连接起来，长度为 f[fa[i]]+f[i]+1。

程序枚举了所有可能作为路径转折点的结点，因此最终 ans 表示树的直径，即树中距离最远的两个结点之间路径所经过的边数。

Q1：当 n=5，fa[2]\sim fa[5]=\{1,2,3,4\} 时，程序输出 4。（ ）

答案：正确（T） 解析：

对应的树是一条链：

从结点 1 到结点 5 一共经过 4 条边，因此树的直径为 4。

也可以模拟程序：

最终输出：

4

所以该说法正确。

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

答案：错误（F）

解析：

f[1] 表示从根结点 1 到最远叶子结点的距离，也就是树的高度；ans 表示树中任意两个结点之间的最大距离，也就是树的直径。

树的直径不一定经过根结点，所以二者不一定相等，该说法错误。

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

答案：错误（F）

解析

原程序必须先计算 ans，再更新 f[fa[i]]：

ans = max(ans, f[fa[i]] + f[i] + 1);
f[fa[i]] = max(f[fa[i]], f[i] + 1);

计算 ans 时，f[fa[i]] 应当表示父结点此前处理过的其他子树所提供的最长路径。

如果交换顺序，先执行：

f[fa[i]] = max(f[fa[i]], f[i] + 1);

那么 f[fa[i]] 可能已经包含当前结点 i 所在的路径。随后再计算：

f[fa[i]] + f[i] + 1

就可能把当前这条路径计算两遍。因此交换顺序会影响结果，该说法错误。

Q4：程序输出的 ans 表示的是（ ）。

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

答案：A 解析：

上面程序解析已经讲过，不再赘述。

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

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

答案：C 解析：

树中最长路径可以从结点 2 的子树中的某个叶子出发，经过结点 1，到达结点 3 的子树中的某个叶子。 因此树的直径为 4，程序输出 4，故选 C。

Q6：当 n=10 时，满足程序输出为 9 的合法输入种类数为（ ）。

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

答案：C 解析：

一棵含 10 个结点的树最多只有 9 条边。如果程序输出 9，说明树的直径为 9，也就是存在一条包含 9 条边的路径，这条路径会经过全部 10 个结点。因此整棵树必须是一条链。

结点 1 不一定处在链的端点，也可能位于链的中间。例如：

8 - 5 - 2 - 1 - 3 - 4 - 6 - 7 - 9 - 10

由于题目要求 fa[i]<i，从根结点 1 沿着任意一条分支向外走时，结点编号必须严格递增。因此可以把结点 2\sim10 分配到根结点 1 的两条链上。每条链中的排列顺序是唯一的，即按照编号从小到大排列。 先暂时区分“第一条链”和“第二条链”。结点 2\sim10 一共有 9 个，每个结点都有两种选择，放入第一条链或放入第二条链。因此得到 2^9=512 种分配。

但是输入只记录每个结点的父结点，并没有记录哪条链是“第一条”、哪条链是“第二条”。交换两条链后，父结点数组完全相同。

以上面的划分为例：

第一组：{2, 5, 8}
第二组：{3, 4, 6, 7, 9, 10}

与：

第一组：{3, 4, 6, 7, 9, 10}
第二组：{2, 5, 8}

都会得到同一个父结点数组：

fa[2]=1
fa[3]=1
fa[4]=3
fa[5]=2
fa[6]=4
fa[7]=6
fa[8]=5
fa[9]=7
fa[10]=9

所以每一种合法输入都被重复统计了两次。最终输入种类数为：

故选 C。

完善程序

T1

题目描述

给定一张有 n 个顶点、m 条边的无向图，每条边带有符号 '+' 或 '-'。

对于一条从顶点 s 到顶点 t 的路线，允许重复经过顶点和边。记 n^+、n^- 分别为路线中经过的 '+' 边数和 '-' 边数，则该路线的权值为：

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

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

数据满足 2\le n\le 2\times 10^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;
}

解析

可以将 '+' 边的边权记为 1，将 '-' 边的边权记为 -1。这样，一条路线所经过边的权值之和就是：

题目要求最小化其绝对值：

程序从顶点 s 开始进行 BFS，同时完成以下三项工作：

1. 判断 t 是否与 s 连通；
2. 计算从 s 到每个顶点的最短边数 d[i]；
3. 对 s 所在的连通块进行二分图染色，判断其中是否存在奇环。

其中：

• p 表示从 s 出发能够访问到的连通块中是否存在 '+' 边；
• ng 表示该连通块中是否存在 '-' 边；
• d[i] 表示从 s 到 i 的最短路所经过的边数；
• c[i] 表示二分图染色中顶点 i 的颜色；
• ok 表示该连通块是否为二分图。

如果 d[t] == -1，说明 s 无法到达 t，输出 -1。

如果连通块中只存在一种符号的边，那么路线权值的绝对值就是路线经过的边数。此时应选择边数最少的路线，因此答案为 d[t]。

如果连通块中同时存在 '+' 边和 '-' 边，由于允许重复经过边，可以通过往返经过某条边来调整路线权值：

• 往返经过一条 '+' 边，权值之和增加 2；
• 往返经过一条 '-' 边，权值之和减少 2。

因此可以将路线权值调整到绝对值为 0 或 1，奇偶性与路线长度相同。

• 若存在偶数长度路线，答案为 0；
• 若所有从 s 到 t 的路线长度均为奇数，答案为 1。

这是因为每条边的权值都是 1 或 -1，在模 2 意义下均与 1 同余，所以路线的权值之和与路线长度奇偶性相同。

若图不是二分图，即 ok == 0，说明存在奇环。可以通过额外绕行一次奇环改变路线长度的奇偶性，因此一定存在偶数长度的 s 到 t 路线。

若图是二分图，则所有从 s 到 t 的路线长度奇偶性相同：

• c[s] == c[t] 时，路线长度为偶数，答案为 0；
• c[s] != c[t] 时，路线长度为奇数，答案为 1。

所以输出 0 的条件为：

!ok || c[s] == c[t]

Q1：①处应填（ ）。

A. op[0] == '+' ? 0 : 1
B. op[0] == '+'
C. op[0] == '+' ? 1 : -1
D. op[0] == '-' ? 1 : 0

答案：C

解析：

程序需要记录每条边对 n^+-n^- 的贡献：

• 经过一条 '+' 边，n^+-n^- 增加 1；
• 经过一条 '-' 边，n^+-n^- 减少 1。

因此应将 '+' 边的权值记为 1，将 '-' 边的权值记为 $-1`：

int z = op[0] == '+' ? 1 : -1;

故选 C。

Q2：②处应填（ ）。

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

答案：D

解析：

数组 q 用来模拟 BFS 队列：

• hh 指向队首；
• tt 指向队尾的下一个位置；
• q[hh] 到 q[tt-1] 是尚未取出的元素。

只要 hh < tt，队列中就还有待处理的顶点。因此 BFS 的循环条件为：

while (hh < tt)

不能使用 hh <= tt，因为当 hh == tt 时队列已经为空，继续访问 q[hh] 会取出无效元素。 类似于 STL 容器中 q.begin(),q.end() 的逻辑。

故选 D。

Q3：③处应填（ ）。

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

答案：B

解析：

d[x] 表示从起点 s 到顶点 x 的最短路长度。

当 BFS 第一次从 x 访问到相邻顶点 y 时，从 s 到 y 的路线比从 s 到 x 的路线多经过一条边，因此：

对应代码为：

d[y] = d[x] + 1;

故选 B。

Q4：④处应填（ ）。

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

答案：A

解析：

程序使用 c[i] 对图进行二分图染色。第一次访问顶点 y 时，将其颜色设置为与 x 相反：

c[y] = c[x] ^ 1;

如果 y 已经被访问过，那么对于边 (x,y)，两端点的颜色应当不同。

若出现：

c[y] == c[x]

说明一条边连接了两个颜色相同的顶点，该连通块不是二分图，其中存在奇环，此时将：

ok = 0;

故选 A。

Q5：⑤处应填（ ）。

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。当存在从 s 到 t 的偶数长度路线时，可以将路线权值调整为 0。

分两种情况讨论。

1. 图不是二分图

此时 ok == 0，图中存在奇环。通过额外绕行奇环，可以改变路线长度的奇偶性，因此一定能够得到一条偶数长度的 s 到 t 路线，答案为 0。

2. 图是二分图

此时路线长度的奇偶性由两端点颜色决定：

• c[s] == c[t]，从 s 到 t 的路线长度为偶数，答案为 0；
• c[s] != c[t]，从 s 到 t 的路线长度为奇数，答案为 1。

所以输出 0 的条件是：

!ok || c[s] == c[t]

故选 C。

补全后的关键代码为：

int z = op[0] == '+' ? 1 : -1;

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 (!ok || c[s] == c[t]) std::cout << 0;
else std::cout << 1;

T2

请输入文本

题目描述

给定 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;
}

解析

这道题的关键是把绝对值转化为可以枚举的形式。

对于第 j 道题，将学生答案与标准答案分别表示为 1 或 -1：

• 学生选择 A，记为 v_{i,j}=1；
• 学生选择 B，记为 v_{i,j}=-1；
• 标准答案为 A，记为 y_j=1；
• 标准答案为 B，记为 y_j=-1。

当学生答案与标准答案相同时，v_{i,j}y_j=1；不同时，v_{i,j}y_j=-1。因此第 i 名学生的得分为：

从而：

由于所有方案的目标值都同时乘以常数 \frac12，因此最大化原式等价于最大化：

利用恒等式：

可以为每名学生设置一个 s_i\in\{-1,1\}，于是目标变为：

交换求和顺序可得：

令：

以及：

对于一组固定的 s_i，每道题的标准答案可以独立选择。为了让 y_jq_j 最大：

• 当 q_j\ge0 时，令 y_j=1，即标准答案选择 A；
• 当 q_j<0 时，令 y_j=-1，即标准答案选择 B。

第 j 道题的最大贡献就是 |q_j|，因此固定 s_i 后的最优值为：

程序枚举全部 2^n 种 s_i。由于 n\le18，这样的枚举可以接受。

为了让相邻两种状态之间只有一名学生的 s_i 改变，程序使用格雷码：

相邻格雷码只有一个二进制位不同。找到发生变化的位置 k 后，只需要更新第 k 名学生对 C 和所有 q[j] 的贡献，不需要重新计算整个状态。

总时间复杂度为：

你CCF能把25年都从大纲删了的格雷码考出来，还有什么是CCF做不到的

Q1：①处应填（ ）。

A. 2 * x[i] - m
B. -m + 2 * x[i] + 1
C. m - 2 * x[i]
D. m + 2 * x[i]

答案：C

解析：

根据前面的推导，第 i 名学生对应的式子为：

其中与标准答案无关的常数部分为：

因此①处应填：

m - 2 * x[i]

程序最初令所有 s[i] 均为 -1，所以初始化时执行：

C -= c[i];

正好得到：

故选 C。

Q2：②处应填（ ）。

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

答案：B

解析：

程序需要使用格雷码枚举，使相邻两个状态恰好只有一个二进制位发生改变。

整数 mask 对应的格雷码为：

对应代码为：

ull g = mask ^ (mask >> 1);

这样 g 与上一个格雷码 lst 之间只有一个二进制位不同，程序便可以只修改一名学生对应的状态。

故选 B。

Q3：③处应填（ ）。

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

答案：D

解析：

g 表示当前格雷码，lst 表示上一个格雷码，因此：

ull d = g ^ lst;

d 中为 1 的二进制位就是两个状态之间发生改变的位置。

由于相邻格雷码只有一位不同，所以 d 中恰好只有一个 1。__builtin_ctzll(d) 返回末尾连续 0 的个数，也就是这个 1 所在的下标。

例如：

d = 001000

其末尾有 3 个连续的 0，发生改变的是下标 3，因此：

int k = __builtin_ctzll(d);

故选 D。

Q4：④处应填（ ）。

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

答案：A

解析：

当前 C 为：

本次格雷码变化后，s[k] 将从原来的 s_k 变为 -s_k。

变化前，第 k 项对 C 的贡献为：

变化后，其贡献为：

所以 C 的变化量为：

因此更新方式为：

C -= 2ll * s[k] * c[k];

需要注意，这里使用的是翻转前的 s[k]，所以程序在更新完 C 和 q[j] 后，才执行：

s[k] = -s[k];

故选 A。

Q5：⑤处应填（ ）。

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

答案：A

解析：

确定最优的 s[i] 后，程序对每道题计算：

ll v = 0;
for (int i = 0; i < n; i++) {
    if (a[i][j] == 'A') v += s[i];
    else v -= s[i];
}

这里的 v 就是：

你CCF还能混用变量名

如果第 j 道题选择 A，其贡献为 v；如果选择 B，其贡献为 -v。因此：

• 当 v\ge0 时，选择 A；
• 当 v<0 时，选择 B。

不过选项中没有直接给出 v >= 0，需要结合 v 的奇偶性判断。

v 是 n 个 1 或 -1 的和，所以：

分两种情况：

• 当 n 为偶数时，n & 1 等于 0，条件 v >= (n & 1) 就是 v >= 0；
• 当 n 为奇数时，v 一定是奇数，不可能等于 0，所以 v >= 0 等价于 v >= 1。此时 n & 1 等于 1，条件仍然成立。

因此：

v >= (n & 1)

与 v >= 0 完全等价，⑤处应填：

if (v >= (n & 1)) res[j] = 'A';
else res[j] = 'B';

故选 A。

补全后的关键代码为：

c[i] = m - 2 * x[i];

// ...

ull g = mask ^ (mask >> 1);
ull d = g ^ lst;
int k = __builtin_ctzll(d);
C -= 2ll * s[k] * c[k];

// ...

if (v >= (n & 1)) res[j] = 'A';
else res[j] = 'B';

总结

还好我在滚木省份，不然可能得考虑是否有过的风险。 第一轮挂的分全都给我 rp++ 到 NOIP 上！！！