CF1622E 题解

差一点想出来，大意了呀。

---

link

有 $n$ 个人参加了 $m$ 道题的一场考试，已知老师对每个人的期望分值 $x_i$ 和 $s_{i,j}$ 表示每个人每道题是否做对。做对得分，做错不等分，令学生真实分数为 $r_i$。

要求你输出一种分数的分配方案，使老师的惊讶度最高。其中，$m$ 道题的分数是一个 $1$ 道 $m$ 的排列，老师的惊讶值等于 $\sum_{i=1}^n |r_i-x_i|$。

$1 \le n \le 10$，$1\le m \le 10^4$，$0 \le x_i \le \dfrac{m(m+1)}{2}$，$s_{i,j} \in \{0,1\}$。

$n$ 这么小，状压搞起来，用每一位表示 $r_i-x_i$ 的正负。这样可以直接把 $x$ 都计算入答案，就不用考虑了。

求出每道题的一个系数 ，表示这道题计入贡献加或减了多少次，这样直接给系数最大的题分配最大的分值，最小的分配最小分值即可，显然正确。

时间复杂度 $O(2^nnm)$。

CODE

#include <bits/stdc++.h>
using namespace std;

inline int read() {
    int x = 0, f = 0; char c = 0;
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c & 15), c = getchar();
    return f ? -x : x;
}

#define N 20
#define M 10010

int n, m, x[N], res, r[M];
pair<int, int> s[M];
char a[N][M];

signed main() {
    for (int T = read(); T --;) {
        n = read(), m = read(), res = -1;
        for (int i = 1; i <= n; i ++) {
            x[i] = read();
        }
        for (int i = 1; i <= n; i ++) {
            scanf("%s", a[i] + 1);
        }
        for (int st = 0; st < 1 << n; st ++) {
            int now = 0;
            for (int i = 1; i <= m; i ++) {
                s[i].first = 0;
                s[i].second = i;
            }
            for (int i = 1; i <= n; i ++) {
                int op = (st >> i - 1) & 1;
                now += op ? -x[i] : x[i];
                for (int j = 1; j <= m; j ++) {
                    if (a[i][j] == '1') {
                        s[j].first += op ? 1 : -1;
                    }
                }
            }
            sort(s + 1, s + m + 1);
            for (int i = 1; i <= m; i ++) {
                now += i * s[i].first;
            }
            if (now > res) {
                res = now;
                for (int i = 1; i <= m; i ++) {
                    r[s[i].second] = i;
                }
            }
        }
        for (int i = 1; i <= m; i ++) {
            printf("%d ", r[i]);
        }
        puts("");
    }
    return 0;
}