『JROI-1』蒟蒻火锅的盛宴 - 解题思路与代码实现 - 常规

『JROI-1』蒟蒻火锅的盛宴 - 解题思路与代码实现

题目背景

传说专门服务神仙们的蒟蒻火锅店前面有一首诗：

灶前无用煮青山，不识神炉自往还。玉碗琼浆谁乞赐，瑶琴银箭可容攀。风生夜气通云汉，雨歇秋光上碧湾。却笑老奴真倦眼，此心空处一团闲。

Qiuly 是洛谷著名餐厅“蒟蒻火锅店”的主厨，当中的伙计很多，比如呆呆的 Aw 顿顿，机智的 Cocoly1990 还有珂爱的 45dino。Qiuly 喜欢让顿顿为他准备丰富多样的食材，制作火锅的必需品包括但不限于七星章鱼和芥末鱼子酱，当然，还有各种各样珍稀而奇怪的食材：

蒟蒻果冻制成的蒟蒻团子。
糯米（雾）制成的糯米青团。
Aw 顿顿制成的菜鸡糕。
Bamboo（45dino）。

这些食材难以收集，但是神仙 Qiuly 还是全部弄到手了。接下来她要让顿顿分类这些食材。但是顿顿是菜鸡，根本不会分类，他崩溃了。于是他请你，IOI 的 AKer，帮助他分类这些食材，因为这个问题事关 Qiuly 的成绩（IOI 第一名还是第二名），所以你必须尽快。

每一个食材都有各种各样的奇怪特性，根据这些特性，Aw 顿顿咨询了全世界的专家们，评价出了一个食材的美味程度，根据这个程度可以有效的分类食材。如果你不能在 400 毫秒内给出答案，你就会成为一个食材，光荣的沉没在 Qiuly 精心调制的汤底中。

题目描述

有 n 个互不相同的整数，现有 m 个整数属于集合 G 中。

Aw顿顿规定这个集合有如下规定：

若 x ∈ G，则 x + a ∈ G。
若 x + a 不在 n 个整数中就不做处理。
若对于一个集合 G 不存在需要加入的元素，那么它是完善的。

若集合是完善的，输出 Great Set!，反之输出至少还要按规定加入几个食材才能完善该级别。

输入格式

第一行是一个整数 n，表示一共有 n 个整数。

接下来一行存在 n 个用空格隔开的整数 A_i，互不相同。

下一行一个正整数 m，表示集合 G 当中有 m 个整数，均属于 n 个整数当中。

接下来一行是 m 个用空格隔开的整数。

最后是一个正整数 a。

输出格式

如果这个集合已经完善，输出 Great Set!。

反之输出需要完善该集合所需的整数数量。

样例 #1

样例输入 #1

样例输出 #1

Great Set!

样例 #2

样例输入 #2

15
13 2 10 3 1 12 8 4 5 7 9 6 15 14 11 
7
13 2 1 12 8 3 10 
2

样例输出 #2

样例 #3

样例输入 #3

50
13 2 10 50 1 28 37 32 30 46 19 47 33 41 24 34 27 42 49 18 9 48 23 35 31 8 7 12 6 5 3 22 43 36 11 40 26 4 44 17 39 38 15 14 25 16 29 20 21 45 
10
50 46 30 32 10 2 28 37 1 13 
3

样例输出 #3

提示

【样例解释】

样例 1 解释

这个集合包含 1, 3, 5，其中 1 + 2 = 3，3 + 2 = 5，5 + 2 = 7 不存在，所以这个集合是完善的。

样例 2 解释

剩下的所有整数都属于这个集合。

【数据范围】

1 ≤ m < n ≤ 6 × 10⁴。
1 ≤ A_i ≤ n。
0 ≤ a ≤ 10⁴。

【捆绑测试情况】

|测试点编号|时间限制|分数分配|n, m ≤ | |:--------:|:------:|:------:|:------:| |Subtask 1|400ms|10pts|10³| |Subtask 2|400ms|15pts|10⁴| |Subtask 3|400ms|35pts|3 × 10⁴| |Subtask 4|400ms|40pts|6 × 10⁴|

P.S. 这题的时限已经开到 std 的 15 倍，附件内有部分测试点。

解题思路

本题的核心在于如何判断集合是否完善，并快速计算出需要添加的元素数量。我们可以采用以下思路：

排序： 首先将所有 n 个整数进行排序，以便于进行后续的操作。
哈希表： 利用哈希表来存储集合 G 中的元素，以便于快速判断一个元素是否属于集合 G。
逐个判断： 遍历所有 n 个整数，对于每个整数 x，判断 x 是否属于集合 G，如果 x 不属于集合 G，则将 x + a 添加到集合 G 中，并记录添加的元素数量。
判断完善： 遍历结束后，如果添加的元素数量为 0，则集合 G 已经完善，输出 Great Set!；否则输出添加的元素数量。

代码实现

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    int m;
    cin >> m;
    unordered_set<int> G;
    for (int i = 0; i < m; i++) {
        int num;
        cin >> num;
        G.insert(num);
    }
    int a;
    cin >> a;

    sort(nums.begin(), nums.end());
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (G.find(nums[i]) == G.end()) {
            cnt++;
            G.insert(nums[i] + a);
        }
    }
    if (cnt == 0) {
        cout << "Great Set!" << endl;
    } else {
        cout << cnt << endl;
    }

    return 0;
}

总结

本题是一个简单的集合扩展问题，利用排序和哈希表可以快速高效地解决问题。需要注意的是，由于数据规模较大，需要使用高效的数据结构和算法，才能在规定的时间限制内得到正确的结果。

『JROI-1』蒟蒻火锅的盛宴 - 解题思路与代码实现