题目(材料题)
（2）标准答案
给定$n$名学生参加一场考试，考试共有$m$道选择题，每道题只有A、B两个选项。
第$i$名学生的作答为一个长度为$m$的字符串。若最终公布的标准答案与该学生在某道题上的作答相同，则该学生在这道题上得$1$分，否则不得分。记第$i$名学生最终得到的总分为$r_i$。
每名学生还有一个预期得分$x_i$。现在需要构造一份标准答案，使$\sum_{i=1}^n|r_i-x_i|$尽可能大。
数据满足$1≤n≤18，1≤m≤300，0≤x_i≤m$。
提示：可以换一个角度处理$\sum_{i=1}^n|r_i-x_i|$，把它写成更易优化的形式。对于正整数$x$，_builtin_popcountl1(x)返回$x$的二进制表示末尾连续0的个数。
以下程序构造出一组满足要求的标准答案。请补全程序。
01 #include <cstdlib>
02 #include <iostream>
03 #include <string>
04 #include <vector>
05
06 using namespace std;
07
08 typedef long long ll;
09 typedef unsigned long long ull;
10
11 int main() {
12 int n, m;
13 cin >> n >> m;
14 vector<ll> x(n), c(n);
15 for (int i = 0; i < n; i++) {
16 cin >> x[i];
17 c[i] = ____①____;
18 }
19 vector<string> a(n);
20 for (int i = 0; i < n; i++)
21 cin >> a[i];
22
23 vector<int> s(n, -1);
24 vector<ll> q(m, 0);
25 ll C = 0, S = 0;
26 for (int i = 0; i < n; i++) {
27 C -= c[i];
28 for (int j = 0; j < m; j++) {
29 if (a[i][j] == 'A') q[j]--;
30 else q[j]++;
31 }
32 }
33 for (int j = 0; j < m; j++) S += abs(q[j]);
34 ll ans = C + S;
35 ull best = 0, lst = 0;
36
37 for (ull mask = 1; mask < (1ULL << n); mask++) {
38 ull g = ____②____;
39 ull d = g ^ lst;
40 int k = ____③____;
41 C -= ____④____;
42 for (int j = 0; j < m; j++) {
43 ll old = q[j];
44 int v = (a[k][j] == 'A' ? 1 : -1);
45 q[j] -= 2ll * s[k] * v;
46 S += abs(q[j]) - abs(old);
47 }
48 s[k] = -s[k];
49 if (C + S > ans) {
50 ans = C + S;
51 best = g;
52 }
53 lst = g;
54 }
55
56 for (int i = 0; i < n; i++) {
57 if ((best >> i) & 1) s[i] = 1;
58 else s[i] = -1;
59 }
60
61 string res(m, 'A');
62 for (int j = 0; j < m; j++) {
63 ll v = 0;
64 for (int i = 0; i < n; i++) {
65 if (a[i][j] == 'A') v += s[i];
66 else v -= s[i];
67 }
68 if (____⑤____) res[j] = 'A';
69 else res[j] = 'B';
70 }
71 cout << res << endl;
72 return 0;
73 }
||
关注我们
