题解 | #助手招募#

题目链接

题目描述

在一个充满魔法与奇迹的世界里，一位伟大的大魔法师正准备进行一场前所未有的宏大炼金实验。为了确保实验的成功，他需要招募三名来自不同专精领域的助手：一名“巨龙血脉”（专精火与力量）、一名“精灵之森”（专精自然与敏捷）以及一名“深海智者”（专精水与智慧）。

候选者名单已经拟定。你需要帮助大魔法师从所有候选中，选出三人组成一个完美的团队。团队必须满足以下条件：

团队中必须恰好包含一名“巨龙血脉”、一名“精灵之森”和一名“深海智者”。
为了避免不同派系的魔力产生冲突，所选中的三名助手的魔力印记（即他们所掌握的独特法术符文）不能有任何重合。

你的任务是找出所有可能的、符合上述条件的团队组合。

输入描述

第一行是一个整数 $C$ ，代表候选者的总数。
接下来的 $C$ 行，每行代表一位候选者的信息，格式如下： ID Type Rune1 Rune2 Rune3 Rune4
- ID：候选者的唯一编号，是一个整数。
- Type：候选者的专精领域（类型），1 代表“巨龙血脉”，2 代表“精灵之森”，3 代表“深海智者”。
- Rune：该候选者所拥有的四个魔力印记的编号。印记编号是一个整数。如果编号为 0，则代表该位置没有印记。

输出描述

输出所有可能的团队组合。每一行代表一个组合，格式为：巨龙血脉ID 精灵之森ID 深海智者ID
输出结果需要按照“巨龙血脉”的 ID 升序排序；如果 ID 相同，则按“精灵之森”的 ID 升序排序；如果前两者 ID 也相同，则按“深海智者”的 ID 升序排序。
如果不存在任何满足条件的组合，请输出 -1。

解题思路

本题的目标是从三类候选人中各选一人，组成一个团队，要求三人的“魔力印记”（即法术符文）互不重合。这是一个典型的组合枚举问题，可以通过暴力搜索解决，关键在于如何高效地组织数据和进行检查。

整个流程可以分解为以下几个步骤：

数据预处理与分组:
- 首先，我们需要读取所有候选人的信息。
- 为了方便后续的组合，我们将所有候选人按照他们的专精领域（类型 1, 2, 3）分成三组。可以使用哈希表或字典来存储，键为类型，值为该类型所有候选人的列表。
- 对于每个候选人，我们需要存储他们的 ID 和他们所拥有的非零魔力印记。将魔力印记存储在哈希集合 (Set) 中是最高效的选择，因为这可以让我们快速地检查印记是否存在或进行交集运算。
遍历所有可能的组合:
- 要找出所有可能的团队，最直观的方法是使用三层嵌套循环，分别遍历三个专精领域的候选人列表。
- 外层循环遍历所有“巨龙血脉”，中间层循环遍历所有“精灵之森”，内层循环遍历所有“深海智者”。
检查魔力印记冲突:
- 在最内层循环中，我们得到了一个由巨龙、精灵、智者组成的三人候选团队。
- 接下来需要判断他们的魔力印记是否有重合。由于我们已经将印记存储在哈希集合中，这个检查变得非常高效。
- 我们需要进行三次两两之间的检查，确保任意两人的印记集合都是不相交 (disjoint) 的：
  1. 巨龙的印记集合与精灵的印记集合没有交集。
  2. 巨龙的印记集合与智者的印记集合没有交集。
  3. 精灵的印记集合与智者的印记集合没有交集。
- 只有当这三个条件同时满足时，这个团队组合才是有效的。
结果的存储、排序和输出:
- 每当找到一个有效的团队组合，我们就将其三名成员的 ID (按巨龙、精灵、智者的顺序) 作为一个元组或列表，存入一个最终的结果列表中。
- 在所有循环结束后，我们对这个结果列表进行排序。排序规则为：首先按“巨龙血脉”的 ID 升序，若相同则按“精灵之森”的 ID 升序，若还相同则按“深海智者”的 ID 升序。
- 最后，检查结果列表。如果列表为空，则输出 -1。否则，遍历排序后的列表，按指定格式逐行输出每个有效的团队组合。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <tuple>

using namespace std;

// 候选人结构体
struct Candidate {
    int id;
    set<int> runes;
};

// 检查两个候选人的符文是否有交集
bool has_intersection(const set<int>& s1, const set<int>& s2) {
    for (int rune : s1) {
        if (s2.count(rune)) {
            return true;
        }
    }
    return false;
}

int main() {
    int c;
    cin >> c;

    map<int, vector<Candidate>> candidates_by_type;
    for (int i = 0; i < c; ++i) {
        int id, type;
        cin >> id >> type;
        set<int> runes;
        for (int j = 0; j < 4; ++j) {
            int rune;
            cin >> rune;
            if (rune != 0) {
                runes.insert(rune);
            }
        }
        candidates_by_type[type].push_back({id, runes});
    }

    vector<tuple<int, int, int>> valid_teams;

    // 三层循环遍历所有组合
    for (const auto& dragon : candidates_by_type[1]) {
        for (const auto& elf : candidates_by_type[2]) {
            for (const auto& sage : candidates_by_type[3]) {
                // 检查符文冲突
                if (has_intersection(dragon.runes, elf.runes) ||
                    has_intersection(dragon.runes, sage.runes) ||
                    has_intersection(elf.runes, sage.runes)) {
                    continue;
                }
                valid_teams.emplace_back(dragon.id, elf.id, sage.id);
            }
        }
    }
    
    // 排序
    sort(valid_teams.begin(), valid_teams.end());

    if (valid_teams.empty()) {
        cout << -1 << endl;
    } else {
        for (const auto& team : valid_teams) {
            cout << get<0>(team) << " " << get<1>(team) << " " << get<2>(team) << endl;
        }
    }

    return 0;
}

import java.util.*;

public class Main {
    // 候选人类
    static class Candidate {
        int id;
        Set<Integer> runes;

        Candidate(int id, Set<Integer> runes) {
            this.id = id;
            this.runes = runes;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int c = sc.nextInt();

        Map<Integer, List<Candidate>> candidatesByType = new HashMap<>();
        candidatesByType.put(1, new ArrayList<>());
        candidatesByType.put(2, new ArrayList<>());
        candidatesByType.put(3, new ArrayList<>());

        for (int i = 0; i < c; i++) {
            int id = sc.nextInt();
            int type = sc.nextInt();
            Set<Integer> runes = new HashSet<>();
            for (int j = 0; j < 4; j++) {
                int rune = sc.nextInt();
                if (rune != 0) {
                    runes.add(rune);
                }
            }
            if (candidatesByType.containsKey(type)) {
                candidatesByType.get(type).add(new Candidate(id, runes));
            }
        }

        List<int[]> validTeams = new ArrayList<>();

        // 三层循环遍历所有组合
        for (Candidate dragon : candidatesByType.get(1)) {
            for (Candidate elf : candidatesByType.get(2)) {
                for (Candidate sage : candidatesByType.get(3)) {
                    // 检查符文冲突
                    if (hasIntersection(dragon.runes, elf.runes) ||
                        hasIntersection(dragon.runes, sage.runes) ||
                        hasIntersection(elf.runes, sage.runes)) {
                        continue;
                    }
                    validTeams.add(new int[]{dragon.id, elf.id, sage.id});
                }
            }
        }

        // 排序
        validTeams.sort(Comparator.comparingInt((int[] arr) -> arr[0])
                                  .thenComparingInt(arr -> arr[1])
                                  .thenComparingInt(arr -> arr[2]));

        if (validTeams.isEmpty()) {
            System.out.println(-1);
        } else {
            for (int[] team : validTeams) {
                System.out.println(team[0] + " " + team[1] + " " + team[2]);
            }
        }
    }

    // 检查两个集合是否有交集
    private static boolean hasIntersection(Set<Integer> s1, Set<Integer> s2) {
        for (int rune : s1) {
            if (s2.contains(rune)) {
                return true;
            }
        }
        return false;
    }
}

def solve():
    c = int(input())
    candidates_by_type = {1: [], 2: [], 3: []}
    for _ in range(c):
        parts = list(map(int, input().split()))
        candidate_id, candidate_type = parts[0], parts[1]
        # 使用集合存储非零符文，便于快速检查交集
        runes = {rune for rune in parts[2:] if rune != 0}
        candidates_by_type[candidate_type].append({'id': candidate_id, 'runes': runes})

    valid_teams = []
    
    # 三层循环遍历所有可能的组合
    for dragon in candidates_by_type[1]:
        for elf in candidates_by_type[2]:
            for sage in candidates_by_type[3]:
                # 检查符文是否有交集
                if not (dragon['runes'] & elf['runes'] or
                        dragon['runes'] & sage['runes'] or
                        elf['runes'] & sage['runes']):
                    valid_teams.append((dragon['id'], elf['id'], sage['id']))

    # 按要求排序
    # Python 的元组排序默认就是逐元素的，符合题目要求
    valid_teams.sort()
    
    if not valid_teams:
        print(-1)
    else:
        for team in valid_teams:
            print(*team)

solve()

算法及复杂度

算法: 暴力枚举 / 组合搜索
时间复杂度: $O(C_1 \cdot C_2 \cdot C_3)$ - 其中 $C_1, C_2, C_3$ 分别是三个专精领域的候选人数量。
空间复杂度: $O(C)$ - 其中 $C$ 是候选人的总数，主要用于存储分组后的候选人数据。