BalticOI 2019 Day2 T3. Olympiads 题解

题目分析

这道题要求我们找到一个城市中第 $C$ 好的代表队得分。代表队由 $K$ 名选手组成，每名选手参加所有 $K$ 场比赛。代表队的得分计算方式是：对于每场比赛，取该代表队中选手在该场比赛的最高分作为该场比赛的得分，然后将所有 $K$ 场比赛的得分相加。

解题思路

核心观察

1. 得分计算特性：对于每场比赛，代表队的得分实际上是该场比赛中代表队成员的最高分
2. 组合数量：总共有 $\binom{N}{K}$ 种可能的代表队组合方式，但 $C$ 最多为 2000，我们不需要枚举所有组合
3. 贪心性质：最优代表队通常包含每场比赛得分最高的选手

算法设计

代码采用了优先队列+BFS+组合计数的方法来按得分从高到低枚举代表队，直到找到第 $C$ 个。

主要步骤：

1. 预处理组合数：计算 $\binom{n}{k}$，当值超过 2000 时截断为 2001
2. 数据排序：对每场比赛的选手按得分从高到低排序
3. 状态表示：用长度为 $K$ 的向量表示状态，其中第 $i$ 个元素表示在第 $i$ 场比赛中选择了排名第几的选手
4. 优先队列搜索：从最优状态开始，逐步扩展相邻状态
5. 组合计数排除：对于每个状态，计算比它差但未被考虑的组合数量

代码详解

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

const int NN = 505;
int binom[NN][7];  // 组合数表，NN=505 因为 N≤500

int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    // 预处理组合数
    binom[0][0] = 1;
    for (int i = 1; i <= NN - 5; i++) {
        for (int j = 0; j <= min(i, 6); j++) {
            if (!j || i == j)
                binom[i][j] = 1;
            else
                binom[i][j] = min(2001, binom[i - 1][j - 1] + binom[i - 1][j]);
        }
    }

    int N, K, C;
    cin >> N >> K >> C;
    
    // 存储每个选手在各场比赛的得分
    vector<vector<int>> a(N);
    // 存储每场比赛的选手得分及编号
    vector<vector<pair<int, int>>> b(K);

    for (int i = 0; i < N; i++) {
        a[i].resize(K);
        for (int j = 0; j < K; j++) {
            cin >> a[i][j];
            b[j].push_back({a[i][j], i});
        }
    }

    // 每场比赛按得分降序排序
    for (int i = 0; i < K; i++) {
        sort(b[i].begin(), b[i].end(), greater<pair<int, int>>());
    }

    vector<int> ban(N);  // 标记被排除的选手
    
    // 计算当前状态的得分
    auto calc = [&](auto & u) {
        int sum = 0;
        for (int i = 0; i < K; i++) {
            sum += b[i][u[i]].first;  // 取每场比赛选择选手的得分
        }
        return sum;
    };
    
    // 处理一个状态
    auto solve = [&](auto & u) {
        int num = N;  // 剩余可选选手数
        
        // 标记必须排除的选手（比当前选择更好的选手）
        for (int i = 0; i < K; i++) {
            for (int j = 0; j < u[i]; j++) {
                if (!ban[b[i][j].second]) {
                    ban[b[i][j].second] = 1;
                    num--;
                }
            }
        }

        // 检查当前状态是否有效（所有选择的选手都可用）
        int fl = 1;
        for (int i = 0; i < K; i++) {
            if (ban[b[i][u[i]].second]) {
                fl = 0;
                break;
            }
        }

        if (fl) {
            // 标记当前选择的选手
            int ct = 0;
            for (int i = 0; i < K; i++) {
                if (!ban[b[i][u[i]].second]) {
                    ban[b[i][u[i]].second] = 1;
                    num--;
                    ct++;
                }
            }

            // 计算比当前状态差但未被考虑的组合数
            int v = binom[num][K - ct];
            
            if (C <= v) {
                // 当前状态就是第C个
                cout << calc(u) << "\n";
                exit(0);
            } else {
                // 跳过这些组合
                C -= v;
            }
        }

        // 重置ban数组
        for (int i = 0; i < K; i++) {
            for (int j = 0; j <= u[i]; j++) {
                ban[b[i][j].second] = 0;
            }
        }
    };
    
    // 优先队列按得分从高到低搜索
    priority_queue<pair<int, vector<int>>> q;
    map<vector<int>, int> vis;  // 记录访问过的状态
    
    vector<int> s(K, 0);  // 初始状态：每场比赛选择排名第0的选手
    q.push({calc(s), s});
    vis[s] = 1;

    while (!q.empty()) {
        auto u = q.top().second;
        q.pop();
        solve(u);  // 处理当前状态

        // 扩展相邻状态：每场比赛选择排名稍低的选手
        for (int i = 0; i < K; i++) {
            if (u[i] + 1 < N) {
                u[i]++;
                if (vis.find(u) == vis.end()) {
                    vis[u] = 1;
                    q.push({calc(u), u});
                }
                u[i]--;
            }
        }
    }

    return 0;
}

关键技巧

1. 状态表示

状态是一个长度为 $K$ 的向量 u，其中 u[i] 表示在第 $i$ 场比赛中选择了排名第 u[i] 的选手（排名从0开始，0表示得分最高的选手）。

2. 组合数剪枝

对于每个状态，计算比它差但未被考虑的组合数：

• 必须排除比当前选择更好的选手
• 剩余选手中选择 $K - ct$ 个选手组成代表队
• 如果剩余组合数 $v \geq C$，说明第 $C$ 个在当前分支中
• 否则跳过 $v$ 个组合，继续搜索

3. 优先队列搜索

使用最大堆确保按得分从高到低枚举状态，保证找到的是真正的第 $C$ 好。

复杂度分析

• 时间复杂度：主要取决于访问的状态数，由于 $C \leq 2000$ 且 $K \leq 6$，实际访问状态数不会太多
• 空间复杂度：$O(NK + \text{状态数})$，在可接受范围内

样例分析

对于样例输入：

5 4 4
7 0 4 9
3 0 8 4
1 1 3 7
5 1 3 4
4 2 2 9

算法会：

1. 找到得分 26 的组合（可能有多个）
2. 找到得分 25 的组合
3. 最终找到第4好的组合，得分24

总结

这道题的关键在于：

1. 理解代表队得分的计算方式
2. 使用合适的状态表示方法
3. 通过组合计数避免枚举所有可能
4. 使用优先队列确保按正确顺序搜索

算法巧妙地结合了贪心、BFS和组合数学，在保证正确性的同时提高了效率。