DDOSvoid's Blog

CF 1622E Math Test

发表于 分类于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

题目描述

https://codeforces.com/contest/1622/problem/E

简要题意：现在有 $n$ 个学生正在考试，试卷有 $m$ 到题目，现在已知每个学生每道题目正确与否，要求给每道题目赋一个 $[1,m]$ 的分值，同时要求 $m$ 道题目的分值为一个排列，同时每个学生心中有一个预期分数 $a_i$，我们令学生真正的分数为 $b_i$，现在要求最大化 $\sum_{i=1}^n|a_i-b_i|$

$n\le 10,m\le 10^4$

Solution

注意到我们只需要最大值，所以我们可以直接 $O(2^n)$ 枚举 $a_i$ 和 $b_i$ 符号将绝对值拆开，然后我们就只需要统计每道题目贡献，按照贡献从小到大赋值即可

时间复杂度 $O(nm2^n)$

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define maxn 11
#define maxm 10010
#define ll long long
using namespace std;

int n, m, a[maxn], cnt[maxm];
char s[maxn][maxm];

int Ans[maxm];
void work() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> s[i] + 1;
    int M = (1 << n) - 1; ll ans = 0;
    for (int S = 0; S <= M; ++S) {
        ll sum = 0;
        for (int i = 1; i <= m; ++i) cnt[i] = 0;
        for (int i = 1; i <= n; ++i) {
            int opt = (S >> i - 1 & 1) ? 1 : -1;
            sum -= opt * a[i];
            for (int j = 1; j <= m; ++j)
                if (s[i][j] == '1') cnt[j] += opt;
        } vector<pair<int, int>> vec;
        for (int i = 1; i <= m; ++i) vec.emplace_back(cnt[i], i);
        sort(vec.begin(), vec.end());
        for (int i = 0; i < m; ++i) sum += 1ll * vec[i].first * (i + 1);
        if (sum >= ans) {
            for (int i = 0; i < m; ++i) Ans[vec[i].second] = i + 1; 
            ans = sum;
        }
    } for (int i = 1; i <= m; ++i) cout << Ans[i] << " \n"[i == m]; 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work(); 
    return 0;
}