标准答案 CSP-S 2026 初赛

[CSP-S 2026 初赛] 标准答案

神秘技巧。

题目链接： 标准答案 。

题目描述：

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

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

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

∑i=1n∣ri−xi∣\sum_{i=1}^{n}|r_i-x_i|

尽可能大。

n≤18,m≤300n\le 18,m\le 300 。

考虑拆开绝对值，钦定集合 SS ，则转化为最大化 ∑i∈S(xi−ri)+∑i∉S(ri−xi)\sum\limits_{i\in S}(x_i-r_i)+\sum\limits_{i\notin S}(r_i-x_i) 。由于绝对值的定义，必然存在一个 SS 使得 SS 达到最大值。

定义 sks_k 表示枚举集合 SS 的情况下 xix_i 项的系数。

接着对 rir_i 做一些转化：

令答案 A=−1,B=1A=-1,B=1 ，第 ii 题的答案 ansians_i ，则有：

ri=m+∑jansjai,j2r_i=\frac{m+\sum_j ans_ja_{i,j}}{2}

则：

ri−xi=m−2xi+∑jansjai,j2r_i-x_i=\frac{m-2x_i+\sum_j ans_ja_{i,j}}{2}

那么我们就立马可以令 ci=m−2xic_i=m-2x_i ，问题变为最大化 ∑isi∑jansjai,j\sum_i s_i\sum_j ans_ja_{i,j} 。

此时我们就完成了 CCF 提示的那一步转化。后面的十分简单，主要是枚举 A,BA,B 谁优秀（对应 abs ）以及格雷码优化。这两个十分简单。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
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] =m-2*x[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 = mask^(mask>>1);
        ull d = g ^ lst;
        int k = __builtin_ctzll(d);
        C -= 2ll*s[k]*c[k];
        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 (v>=(n&1)) res[j] = 'A';
        else res[j] = 'B';
    }
    cout << res << endl;
    return 0;
}