D. The Strongest Build - 题解

比赛与标签

比赛: Educational Codeforces Round 114 (Rated for Div. 2) 标签: binary search, brute force, data structures, dfs and similar, graphs, greedy, hashing, implementation 难度: *2000

喵喵，这道题要我们做什么呀？

主人，这道题是这样的呐：我们扮演一个英雄，有 n 个装备槽。每个槽 i 都有 c_i 件不同的装备可以选择，每件装备都能增加一定的实力值。我们要做的是，从每个槽里选一件装备，组成一个“配装”（build）。

一个配装的总实力，就是所有选中的装备实力值加起来的总和。但是呢，游戏里有一些配装是被GM禁止的，我们有一个包含 m 个配装的“黑名单”。

我们的任务就是，在所有没有被禁止的配装中，找到一个总实力值最高的配装，然后把这个配装的方案（也就是每个槽选的是第几件装备）打印出来。题目保证了至少有一种配装是可行的哦！

简单来说，就是要在不触犯规则的前提下，当最强的那个仔，喵~！

寻找最强配装的秘密喵！

一看到要找“最强”的，本猫娘的DNA就动了！最强的配装，那肯定是每个装备槽都选当前槽里最厉害的那个装备呀，对不对？也就是每个槽都选列表里的最后一个装备。这样组合出来的配装，其实力值一定是整个游戏里最高的，没有任何配装能比它更强了！我们叫它“理想最强配装”好了。

好，现在我们拿着这个“理想最强配装”，去黑名单上查一下。

如果它不在黑名单上，那简直太棒了！我们直接找到了答案，任务完成，可以去晒太阳了喵~！
如果它在黑名单上...呜...出师不利。那说明最终的答案，实力肯定比这个“理想最强配装”要低一些。

那实力值第二强的配装会是什么样子的呢？它肯定和我们的“理想最强配装”非常接近。具体来说，它只可能是在“理想最强配装”的基础上，把某一个槽的装备降一级（换成当前槽里第二强的装备）。

比如说，“理想最强配装”是 [b_1, b_2, ..., b_n] (这里的 b_i 都是各个槽里最强的装备的索引)，那么实力值仅次于它的配装们，就可能是 [b_1-1, b_2, ..., b_n], [b_1, b_2-1, ..., b_n], ..., [b_1, b_2, ..., b_n-1] 这些。

这给了我们一个绝妙的思路！我们可以把每一种配装都看作一个状态。我们从“理想最强配装”这个状态开始，如果它被禁了，我们就把它所有“邻居”状态（就是只把一件装备降一级得到的新配装）找出来。在这些邻居中，我们肯定优先想尝试那个实力值最高的，对吧？

这不就是一个经典的优先队列（大顶堆）的应用场景嘛！我们可以用它来做一次广度优先搜索（BFS），但不是普通的BFS，而是最佳优先搜索（Best-First Search）！

本猫娘的寻宝计划是这样哒：

创建一个优先队列 pq，用来存放待检查的配装方案。队列会根据配装的总实力值，自动把最强的排在队首。
创建一个 set 叫做 banned_set，把所有被禁止的配装方案都存进去，方便我们快速查询。
创建一个 set 叫做 visited，用来记录已经检查过或者已经放入队列的配装，防止我们走回头路或者重复计算，这很重要哦！
首先，计算出“理想最强配装”和它的总实力，把它作为第一个候选者放入 pq 和 visited 中。
然后开始循环，只要 pq 不为空： a. 从 pq 顶部取出一个当前实力最高的配装 current_build。 b. 去 banned_set 里查一下，current_build 是不是被禁了？ c. 如果没有被禁，恭喜！我们找到了！因为我们总是从最强的开始检查，所以第一个找到的没被禁的配装，一定就是答案！直接输出它，然后开心地结束程序。 d. 如果被禁了，那只好继续寻找。我们以 current_build 为基础，生成它所有的“邻居”配装（即尝试把它的 n 个槽位的装备分别降一级）。 e. 对于每个新生成的“邻居”配装，如果它没有在 visited 里出现过，就把它加入 pq 和 visited。

因为题目保证了总有解，所以这个过程最后一定会找到答案的！这个方法就像是在一个由所有配装方案构成的巨大地图里，从“实力最高峰”出发，一步步向实力稍低的山峰探索，直到找到第一个没有被地雷（banned）标记的安全山峰，喵~！

让代码动起来喵！

下面就是把我们的寻宝计划变成代码实现啦！

cpp

#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
    // 使用C++的黑魔法让输入输出更快，喵~
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    // 用一个二维 vector 来存放所有装备的实力值
    vector<vector<long long>> items(n);
    for (int i = 0; i < n; i++) {
        int c_i;
        cin >> c_i;
        vector<long long> a(c_i);
        for (int j = 0; j < c_i; j++) {
            cin >> a[j];
        }
        items[i] = a;
    }

    int m;
    cin >> m;
    // 用一个 set 来存放所有被禁止的配装，这样查找起来会很快的说！O(log m)
    set<vector<int>> banned_set;
    for (int i = 0; i < m; i++) {
        vector<int> b(n);
        for (int j = 0; j < n; j++) {
            cin >> b[j];
            // 注意！题目给的是 1-based index，我们程序里用 0-based 更方便，所以要减一哦
            b[j]--;
        }
        banned_set.insert(b);
    }

    // best 是我们的初始配装，每个槽都选最强的（也就是列表里最后一个）
    vector<int> best(n);
    long long best_strength = 0;
    for (int i = 0; i < n; i++) {
        best[i] = items[i].size() - 1;
        best_strength += items[i][best[i]];
    }

    // 这是我们的寻宝核心！一个优先队列，会自动按实力值从大到小排序
    // pair 的第一个元素是实力值，第二个是配装方案 (vector<int>)
    priority_queue<pair<long long, vector<int>>> pq;
    pq.push({best_strength, best});

    // visited 集合，防止我们重复探索同一个配装方案，很重要的喵！
    set<vector<int>> visited;
    visited.insert(best);

    // 主循环开始！只要队列里还有候选配装，就继续找
    while (!pq.empty()) {
        // 取出当前队列中实力值最高的配装
        auto top = pq.top();
        pq.pop();
        long long strength = top.first;
        vector<int> state = top.second;

        // 检查一下这个配装是不是被禁止了
        if (banned_set.find(state) == banned_set.end()) {
            // 如果没被禁止，太棒了！这就是答案！直接输出然后结束程序喵~
            for (int i = 0; i < n; i++) {
                cout << state[i] + 1 << " "; // 输出时记得变回 1-based
            }
            cout << endl;
            return 0;
        }

        // 如果被禁止了，就要从这个配装出发，寻找实力值稍低一点点的邻居们
        for (int i = 0; i < n; i++) {
            // 尝试将第 i 个槽的装备降一级，前提是它不是最弱的装备（索引 > 0）
            if (state[i] > 0) {
                vector<int> new_state = state;
                new_state[i]--;
                
                // 如果这个新的配装我们还没见过
                if (visited.find(new_state) == visited.end()) {
                    // 把它标记为已访问
                    visited.insert(new_state);
                    // 计算新实力值，然后塞进优先队列里，等待宠幸~
                    long long new_strength = strength - items[i][state[i]] + items[i][new_state[i]];
                    pq.push({new_strength, new_state});
                }
            }
        }
    }

    return 0;
}

算算时间会不会超时喵？

时间复杂度: O(m * n * log(m + k)) 的说。这里的 k 是我们从优先队列中取出并处理的被禁配装的数量，最坏情况下 k 约等于 m。每次我们从队列中取出一个被禁配装，我们可能会生成 n 个新的配装。将新配装插入 set 和 priority_queue 的操作，其复杂度与集合/队列的大小有关。set<vector<int>> 的比较操作需要 O(n)。所以，处理一个状态的成本大约是 O(n * log(size))。总的来说，这个复杂度足以在规定时间内通过此题，因为 n 很小。
空间复杂度: O((m + k) * n) 的说。 banned_set 最多存储 m 个配装，visited 和 pq 最多存储 k (约 m) 个配装。每个配装方案都是一个大小为 n 的向量。所以总空间消耗和被禁配装数量以及我们探索的配装数量成正比。

这次学到了什么新姿势？

这道题真是太棒了，让我们学会了好多东西呐！

最佳优先搜索 (Best-First Search): 它是解决这类“在巨大搜索空间中寻找最值”问题的强大武器。通过优先队列，我们总能保证先探索最有可能成为答案的节点。
从最优解出发的逆向思维: 当直接求解很困难时，可以先找到一个不受限制的“理想最优解”，然后把它作为起点，一步步向可行解逼近。这是一个非常巧妙的思路！
数据结构的选择:
- priority_queue 是实现最佳优先搜索的不二之选。
- set<vector<int>> 用来去重和快速查找，虽然 unordered_set 加上自定义哈希会更快，但 set 在这种情况下已经足够好用且写起来方便多啦！
细节决定成败: 千万不要忘记处理 1-based 和 0-based 索引的转换，以及使用 visited 集合来避免无限循环和重复工作，这些都是保证代码正确又高效的关键点哦！

希望本猫娘的讲解对你有帮助！下次遇到类似的题目，你也能像小猫一样敏锐地发现解题的线索啦！加油喵~！

D. The Strongest Build - 题解 ​

比赛与标签 ​

喵喵，这道题要我们做什么呀？ ​

寻找最强配装的秘密喵！ ​

让代码动起来喵！ ​

算算时间会不会超时喵？ ​

这次学到了什么新姿势？ ​