CSP-S 提高级 · CSP 2026 提高级第一轮 第 20 题

【完善程序2 （标准答案）】

有 n 名学生参加一次考试，考试共有 m 道选择题，每道题只有 A、B 两个选项。第 i 名学生的作答用一个长度为 m 的字符串 a_i 表示。若最终公布的标准答案与该学生在某道题上的作答相同，则该学生得 1 分，否则不得分。记第 i 名学生最终得到的总分为 r_i。给定每名学生的目标分数 x_i。现在需要构造一份标准答案，使 Σ|r_i - x_i| 尽可能大。数据满足 1 ≤ n ≤ 20，1 ≤ m ≤ 300，0 ≤ x_i ≤ m。以下程序从枚举符号的角度处理 Σ|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++) {
      

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

看到绝对值最大化 → 先想符号枚举 + 格雷码增量

①符号反了（2x−m）；②用二进制递增导致多位翻转；③ctz取错对象（应取d）；④忘记乘2；⑤漏掉v=0情形。

考点：格雷码构造｜符号枚举优化｜内置函数ctz/popcount

程序在做什么

枚举 n 位学生的符号组合，用格雷码使相邻状态仅翻转一位，增量维护目标函数 C+S，最后按每列 q 的符号决定答案。