前置知识:

二进制枚举操作:https://oi-wiki.org/math/binary-set/

不知道这个知识点，接下来的方法将举步维艰。

题目大意

给定若干猎人和猎物，每名猎人有8种技能，每种猎物有若干弱点。猎人要击杀猎物需满足：技能覆盖所有弱点，技能中包含A~F其中一个，且最后一个技能能命中任意一个弱点。计算每个猎人能击杀的猎物数量。

思路

技能和弱点的二进制掩码表示: 每个猎人的技能和每个猎物的弱点都可以用16位二进制数表示。将技能或弱点中的每个十六进制字符映射为相应的二进制位。例如，0代表第1位，F代表第16位。这样，猎人8个技能的组合和猎物的弱点都可以转换为二进制掩码。$\\$ 条件检查:$\\$ 覆盖弱点：猎人技能必须覆盖猎物的所有弱点。可以通过skills_mask & weakness_mask == weakness_mask来判断。 包含A或F的技能：通过skills_mask & AF_mask来检查猎人的技能中是否包含A或F。 最后一个技能命中弱点：通过last_skill & weakness_mask != 0来判断猎人的最后一个技能是否能命中猎物的任意一个弱点。$\\$ 实现步骤:$\\$ 1.首先，将猎人的技能和猎物的弱点转换为二进制掩码。$\\$ 2.对每个猎人，遍历所有猎物，依次检查猎人是否满足所有条件，并记录每个猎人能够击杀的猎物数量。 3.最终输出每个猎人可击杀的猎物种类数。 $\\$ 复杂度分析:每个猎人的技能固定为8个，不会重复，因此子集枚举的复杂度为 2^8，总时间复杂度0(2^8×n+m*60)

关键条件

为了成功击杀猎物，猎人需要满足以下条件：

1. 技能覆盖：猎人的技能必须覆盖猎物的所有弱点。通过二进制位运算，可以判断猎人的技能掩码是否包含猎物的弱点掩码。
2. 包含特定技能：猎人的技能中至少要有一个技能在[A, F]范围内，确保猎人具备一定的强力技能。
3. 最后技能命中：猎人最后选择的技能必须能够命中猎物的至少一个弱点，确保猎人的攻击有效。

实现步骤

1. 掩码表示：利用二进制掩码来表示技能和弱点。将每个十六进制字符映射到二进制位上，0代表第一位，F代表第16位。
2. 遍历猎物弱点：构建一个数组 preyWeaknessCount 来记录每种弱点组合的猎物数量。每读取一个猎物的弱点，更新对应的掩码。
3. 处理猎人技能：对于每个猎人：
   • 将猎人的技能转换为掩码。
   • 检查猎人的技能是否包含[A, F]的技能。
   • 计算猎人能击杀的猎物数量：
     • 通过遍历所有可能的技能组合（子集）来检查猎人技能是否覆盖猎物的弱点，并且最后技能能否命中。
4. 输出结果：最终输出每个猎人可击杀的猎物数量。

复杂度分析

• 每位猎人有8种技能，因此其子集的总数为 (2^8 = 256)。
• 对于每种猎物，其弱点数量范围为1到60，因此总的时间复杂度为 (O(2^8 \times n + m \times 60))，其中n为猎人数量，m为猎物数量。这种复杂度在给定的限制下是可接受的。

代码如下

cpp

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    int hunters, preys;  // 猎人数量和猎物数量
    cin >> hunters >> preys;

    // 读取每个猎人的技能，存储在一个字符串向量中
    vector<string> hunterSkills(hunters);
    for (int i = 0; i < hunters; i++) {
        cin >> hunterSkills[i];  // 读取每个猎人的8个技能
    }

    // 用来记录每种弱点组合的猎物数量，最大可能的弱点掩码为65536
    vector<int> preyWeaknessCount(65536, 0);

    // 处理每个猎物的弱点
    while (preys-- > 0) {
        string weakness;  // 存储当前猎物的弱点
        cin >> weakness;
        int weaknessMask = 0;  // 用来记录猎物弱点的掩码
        for (char w : weakness) {
            // 将每个弱点字符转换成十六进制表示的位掩码
            int v = isdigit(w) ? w - '0' : w - 'A' + 10;  // 计算弱点的位
            weaknessMask |= (1 << v);  // 设置对应位为1
        }
        preyWeaknessCount[weaknessMask]++;  // 记录该弱点组合的猎物数量
    }

    // 用来存储每个猎人能击杀的猎物数量
    vector<int> killCount;

    // 处理每个猎人的技能
    for (const string& skills : hunterSkills) {
        bool ok = false;  // 用于检测是否拥有 [A-F] 的技能
        int skillMask = 0;  // 用来记录猎人的技能掩码
        
        // 如果猎人最后一个技能不是数字，直接标记 ok 为 true
        if (!isdigit(skills.back())) {
            ok = true;
        }

        // 检查猎人的技能，并将技能转换成位掩码
        for (int i = 0; i + 1 < skills.length(); i++) {
            char skill = skills[i];
            if (isdigit(skill)) {
                skillMask |= (1 << (skill - '0'));  // 数字技能
            } else {
                skillMask |= (1 << (skill - 'A' + 10));  // [A-F] 技能
                ok = true;  // 拥有 [A-F] 技能
            }
        }

        // 猎人最后一个技能对应的掩码
        int lastSkill = isdigit(skills.back()) ? skills.back() - '0' : skills.back() - 'A' + 10;
        int lastSkillMask = (1 << lastSkill);  // 计算最后一个技能的位掩码

        int preyCanKill = 0;  // 当前猎人可以击杀的猎物数量

        // 如果猎人有 [A-F] 的技能，遍历子集枚举
        if (ok) {
            for (int mask = skillMask; ; mask = (mask - 1) & skillMask) {
                // 判断当前猎物是否可以被击杀，检查技能是否覆盖弱点
                preyCanKill += preyWeaknessCount[mask | lastSkillMask];
                if (mask == 0) break;  // 完成所有子集枚举
            }
        }

        // 记录每个猎人可以击杀的猎物数量
        killCount.push_back(preyCanKill);
    }

    // 输出每个猎人可以击杀的猎物数量
    for (int count : killCount) {
        cout << count << " ";  // 输出每位猎人可击杀的猎物数量
    }
    cout << endl;

    return 0;
}

java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取n和m
        int hunters = sc.nextInt();
        int preys = sc.nextInt();
        sc.nextLine(); // 读取剩余的换行符

        // 读取n个猎人的技能
        String[] hunterSkills = sc.nextLine().split(" ");

        // 用来记录每种弱点组合的猎物数量
        int[] preyWeaknessCount = new int[65536];

        // 读取m个猎物的弱点
        String[] preyWeaknesses = sc.nextLine().split(" ");

        // 处理每个猎物的弱点
        for (String weakness : preyWeaknesses) {
            int weaknessMask = 0;  // 用来记录弱点的掩码
            for (char w : weakness.toCharArray()) {
                // 将每个弱点字符转换成十六进制表示的位掩码
                int v = Character.isDigit(w) ? w - '0' : w - 'A' + 10;
                weaknessMask |= (1 << v);
            }
            preyWeaknessCount[weaknessMask]++;  // 记录该弱点组合的猎物数量
        }

        // 用来存储每个猎人能击杀的猎物数量
        List<Integer> killCount = new ArrayList<>();

        // 处理每个猎人的技能
        for (String skills : hunterSkills) {
            boolean ok = false;  // 用于检测是否拥有 [A-F] 的技能
            int skillMask = 0;  // 用来记录猎人的技能掩码

            // 如果猎人最后一个技能不是数字，直接标记 ok 为 true
            if (!Character.isDigit(skills.charAt(7))) {
                ok = true;
            }

            // 检查猎人的技能，并将技能转换成位掩码
            for (int i = 0; i + 1 < skills.length(); i++) {
                char skill = skills.charAt(i);
                if (Character.isDigit(skill)) {
                    skillMask |= (1 << (skill - '0'));  // 数字技能
                } else {
                    skillMask |= (1 << (skill - 'A' + 10));  // [A-F] 技能
                    ok = true;  // 拥有 [A-F] 技能
                }
            }

            // 猎人最后一个技能对应的掩码
            int lastSkill = Character.isDigit(skills.charAt(7)) ? skills.charAt(7) - '0' : skills.charAt(7) - 'A' + 10;
            int lastSkillMask = (1 << lastSkill);

            int preyCanKill = 0;  // 当前猎人可以击杀的猎物数量

            // 如果猎人有 [A-F] 的技能，遍历子集枚举
            if (ok) {
                for (int mask = skillMask; ; mask = (mask - 1) & skillMask) {
                    preyCanKill += preyWeaknessCount[mask | lastSkillMask];  // 判断当前猎物是否可以击杀
                    if (mask == 0) break;  // 完成所有子集枚举
                }
            }

            // 记录每个猎人可以击杀的猎物数量
            killCount.add(preyCanKill);
        }

        // 输出每个猎人可以击杀的猎物数量
        for (int count : killCount) {
            System.out.print(count + " ");
        }
        System.out.println();
    }
}

python

def main():
    # 读取 n 和 m
    n, m = map(int, input().split())

    # 读取 n 个猎人的技能
    hunter_skills = input().split()

    # 用来记录每种弱点组合的猎物数量
    prey_weakness_count = [0] * 65536

    # 读取 m 个猎物的弱点
    prey_weaknesses = input().split()

    # 处理每个猎物的弱点
    for weakness in prey_weaknesses:
        weakness_mask = 0  # 用来记录弱点的掩码
        for w in weakness:
            # 将每个弱点字符转换成十六进制表示的位掩码
            v = int(w, 16)
            weakness_mask |= (1 << v)
        prey_weakness_count[weakness_mask] += 1  # 记录该弱点组合的猎物数量

    # 用来存储每个猎人能击杀的猎物数量
    kill_count = []

    # 处理每个猎人的技能
    for skills in hunter_skills:
        ok = False  # 用于检测是否拥有 [A-F] 的技能
        skill_mask = 0  # 用来记录猎人的技能掩码

        # 如果猎人最后一个技能不是数字，直接标记 ok 为 true
        if not skills[-1].isdigit():
            ok = True

        # 检查猎人的技能，并将技能转换成位掩码
        for i in range(7):
            skill = skills[i]
            if skill.isdigit():
                skill_mask |= (1 << (ord(skill) - ord('0')))  # 数字技能
            else:
                skill_mask |= (1 << (ord(skill) - ord('A') + 10))  # [A-F] 技能
                ok = True  # 拥有 [A-F] 技能

        # 猎人最后一个技能对应的掩码
        last_skill = int(skills[-1], 16)
        last_skill_mask = (1 << last_skill)

        prey_can_kill = 0  # 当前猎人可以击杀的猎物数量

        # 如果猎人有 [A-F] 的技能，遍历子集枚举
        if ok:
            mask = skill_mask
            while True:
                prey_can_kill += prey_weakness_count[mask | last_skill_mask]  # 判断当前猎物是否可以击杀
                if mask == 0:
                    break
                mask = (mask - 1) & skill_mask  # 完成所有子集枚举

        # 记录每个猎人可以击杀的猎物数量
        kill_count.append(prey_can_kill)

    # 输出每个猎人可以击杀的猎物数量
    print(" ".join(map(str, kill_count)))


if __name__ == "__main__":
    main()

题目内容

有若干名猎人来到草原狩猎，每名猎人在狩猎开始前需要灵活搭配技能用于击杀猎物，每个技能由十六进制数[$0,F$]中的某个数来表达，每个猎人都必须选择$8$种不重复的技能。草原上有各种各样的猎物，并且具备一些弱点，弱点也由十六进制数[$0,F$]中的某个数字表达。猎人能击杀某种猎物的前提是同时满足:

1.猎人的技能可以覆盖猎物的所有弱点。

2.猎人的技能至少包含[$A,F$]中的其中一个技能。

3.猎人最后一个技能需要至少命中猎物的任意一个弱点。

每种猎物的数量可以认为是无限的，但是每种猎物只能被同一名猎人击杀一次，请帮忙计算每个猎人可击杀的猎物种类数量，击杀猎物总数最多的猎人将获得赏金猎人的称号

输入描述

$1$.第一行为猎人和猎物种类的数量，依次用空格隔开，第二行为每名猎人选择的技能，不同猎人的技能之间用空格隔开，第三行为所有的猎物，不同猎物之间的弱点用空格隔开。

$2$.输入的猎人数量在[$1,1000$]。

$3$.输入的猎物数量在[$1,200000$]。

$4$.每个猎人的技能数量固定为$8$，并且不包含重复技能。

$5$.每种猎物的弱点数量范围在[$1,60$]，可能包含重复的弱点。

6.十六进制数[$0,F$]中的字母均为大写。

输出描述

给定一个已完成技能搭配的猎人数组和猎物数组，请返回一个数组，数组中的每个元素是对应猎人最多可击杀的猎物数量。

样例1

输入

3 5
028F415A 2340789E 043BCD12
0222F44A 44C 8848A 002B2 F4415CA

输出

2 0 1

说明

第$1$名猎人具备的技能为$028F415A$，最后$1$个技能可以命中第$1、3、5$种猎物，但是不具备命中第$5$种猎物的$C$弱点，只能击杀第$1$和第$3$种猎物，因此可击杀的猎物数量为$2$。

第$2$名猎人具备的技能为$2340789E$，没有任何猎物包含$E$这个弱点，因此可击杀的猎物数量为$0$。

第$3$名英雄具备的技能为$043BCD12$，虽然这些技能可以覆盖第$2、4$种猎物，但是最后$1$个技能无法命中第$2$种猎物的弱点，只能击杀第$4$种猎物，因此可击杀的猎物数量为$1$。

样例2

输入

2 3 
7519FCB0 01234567
25351727 A0 19C00

输出

1 0

说明

第$1$名猎人可以击杀第$2$种猎物。

第$2$名猎人虽然技能可以覆盖第$1$种猎物，并且最后一个技能$7$可以命中猎物的弱点，但是不包含[$A,F$]中的任一技能，因此不能击杀猎物，可击杀的猎物数量为$0$。

样例3

输入

3 3 
027BAB5C 12307ABC 043BCD1A
ABC0 0ABC 4ABC0

输出

2 2 3

说明

第$1$名猎人可以击杀第$1$种和第$2$种猎物，因此可击杀的猎物数量为$2$。

第$2$名猎人可以击杀第$1$种和第$2$种猎物，因此可击杀的猎物数量为$2$。

第$3$名猎人可以击杀$3$种猎物，因此可击杀的猎物数量为$3$