c++

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>

using namespace std;

int main() {
    int m, n;
    cin >> m >> n;

    cin.ignore();

    string str;
    getline(cin, str);
    stringstream ss(str);

    vector<string> hunters(m);
    for (int i = 0; i < m; ++i) {
        ss >> hunters[i];
    }

    getline(cin, str);
    stringstream ss2(str);

    vector<int> animals(65536, 0);
    for (int i = 0; i < n; ++i) {
        string temp;
        ss2 >> temp;
        int index = 0;
        for (char c: temp) {
            int num;
            if (c >= '0' && c <= '9') {
                num = c - '0';
            } else {
                num = c - 'A' + 10;
            }

            index |= (1 << num);
        }
        animals[index] ++;
    }

    vector<int> res;

    for (int i = 0; i < m; ++i) {
        string hunterStr = hunters[i];
        sort(hunterStr.begin(), hunterStr.end());
        if (hunterStr.size() == 8 && hunterStr[7] >= 'A' && hunterStr[7] <= 'F' ) {
            hunterStr = hunters[i];
            int num = 0;
            if (hunterStr[7] <= '9' && hunterStr[7] >= '0') {
                num = hunterStr[7] - '0';
            } else {
                num = hunterStr[7] - 'A' + 10;
            }
            int lastSkill = (1 << num);
            int skill = 0;

            for (char c: hunterStr) {
                if (c <= '9' && c >= '0') {
                    num = c - '0';
                } else {
                    num = c - 'A' + 10;
                }
                skill |= (1 << num);
            }

            num = 0;

            int mask = skill;
            while(mask != 0) {
                if ((mask & lastSkill) != 0) {
                    num += animals[mask];
                }
                mask = (mask - 1) & skill;
            }

            res.push_back(num);

        } else {
            res.push_back(0);
        }
    }

    for (int i: res) {
        cout << i << " ";
    }

    return 0;


}

前置知识:

二进制枚举操作: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()