CSP-S 2026 第一轮 第 42 题：标准答案：④处应填

题目

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

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

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

尽可能大。

数据满足 $1 \le n \le 18$，$1 \le m \le 300$，$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;
}

④处应填（ ）。

选项

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

答案

A

题解

选 **A：2ll * s[k] * c[k]**。

关键是理解：C 保存的是 \[ C=\sum_{i=0}^{n-1}s[i]\cdot c[i]. \] 每次循环要把 s[k] 取反，因此第 \(k\) 项从 \(s[k]c[k]\) 变成 \(-s[k]c[k]\)，变化量为 \[ -s[k]c[k]-s[k]c[k]=-2s[k]c[k]. \] 所以应写： ``cpp C -= 2ll * s[k] * c[k]; ``

下面解释这个维护式是怎么来的。

1. 把得分表示成代数形式

将 A 记为 \(+1\)，B 记为 \(-1\)。设学生 \(i\) 对题目 \(j\) 的作答为 \(a_{ij}\)，标准答案为 \(b_j\)。

两者相同时 \(a_{ij}b_j=1\)，不同时为 \(-1\)，因此 \[ r_i=\frac{m+\sum_j a_{ij}b_j}{2}. \] 令 \(c_i=m-2x_i\)，就有 \[ 2(r_i-x_i)=c_i+\sum_j a_{ij}b_j. \]

2. 用正负号消去绝对值

利用 \[ |z|=\max_{s\in\{-1,1\}}sz, \] 可得 \[ 2\sum_i|r_i-x_i| =\max_{s_i\in\{-1,1\}} \left(\sum_i s_ic_i+\sum_j b_j\sum_i s_i a_{ij}\right). \]

枚举所有 \(s_i\) 后，记 \[ C=\sum_i s_ic_i,\qquad q_j=\sum_i s_i a_{ij}. \] 每道题独立选择 \(b_j\)：当 \(q_j\ge0\) 时选 A，否则选 B。这样这一题的贡献就是 \(|q_j|\)，所以要最大化 \[ C+\sum_j|q_j|=C+S. \]

3. 对照代码更新

代码用格雷码枚举，使相邻两次只有一个符号 s[k] 改变。更新 C 时，s[k] 还没有取反，所以必须减去旧贡献的两倍。

其余空也可以对应出来：

总时间复杂度为 \(O(m2^n)\)。