4 solutions

  • 0
    @ 2024-11-12 18:17:50 
    #include <iostream>
#include <vector>
#include <string>

using namespace std;
const int MAXN = 1e3 + 1, MAXM = 2e5 + 1;
string hunter[MAXN], prey[MAXM];
int n, m;

vector<int> preymap[16];

int toint(char c) {
    if(c >= '0' && c <= '9')  return c - '0';
    else return c - 'A' + 10;
}

int tobits(string s) {
    int b = 0;
    for(int i = 0; i < s.length(); i++) {
        b |= 1 << toint(s[i]);
    }
    return b;
}

int main() {
    cin >> n >> m;
    for(int i = 0; i < n; i++) { cin >> hunter[i];}
    for(int i = 0; i < m; i++) { cin >> prey[i]; }

    for(int i = 0; i < m; i++) {
        int p = tobits(prey[i]);
        for(int j = 0; j < 16; j++) {
            if(1 &(p >> j)) preymap[j].push_back(p);
        }
    }

    vector<int> ans;
    for(int i = 0 ;i < n;i ++) {
        string hs = hunter[i]; int h = tobits(hs), n = hs.length();
        if(!(h >> 10) || preymap[toint(hs[n- 1])].empty()) {ans.push_back(0); continue;}

        int cnt = 0;
        for(int p: preymap[toint(hs[n - 1])]) {
            if(!(p ^ (p & h))) cnt++;
        }
        ans.push_back(cnt);
    }

    for(int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
    cout <<endl;
    return 0;
}
    • 0
      @ 2024-10-17 16:47:18 
      #pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define pb push_back
#define PII pair<int, int>
#define PDI pair<double, int>
#define all(x) x.begin(), x.end()
#define quickcin() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
const int N = 1e4 + 10, M = 2e5 + 10, MINRAND = 0, MAXRAND = 1e9;

mt19937 rnd1(time(0));
mt19937_64 rnd2(time(0));
uniform_int_distribution<> int_mt(MINRAND, MAXRAND);
uniform_real_distribution<> double_mt(MINRAND, MAXRAND);
int n, m;
int ans[N], able[N];
bool st[20];
int hunter[N], monster[M];
int lasts[N];
vector<int> suit[20];
void solve()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        for (auto j : s)
        {
            if (!isdigit(j))
                able[i] = 1, hunter[i] |= 1 << (j - 'A' + 10);
            else
                hunter[i] |= 1 << (j - '0');
        }
        lasts[i] = s[s.size() - 1];
    }
    for (int i = 0; i < m; i++)
    {
        string s;
        cin >> s;
        memset(st, 0, sizeof st);
        for (auto j : s)
        {
            if (!isdigit(j))
            {
                int id = j - 'A' + 10;
                monster[i] |= 1 << id;
                if (!st[id])
                    suit[id].pb(i);
                st[id] = 1;
            }
            else
            {
                int id = j - '0';
                monster[i] |= 1 << id;
                if (!st[id])
                    suit[j - '0'].pb(i);
                st[id] = 1;
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (!able[i])
        {
            cout << 0 << " ";
            continue;
        }
        int res = 0;
        for (auto k : suit[(isdigit(lasts[i]) ? lasts[i] - '0' : lasts[i] - 'A' + 10)])
        {
            if ((monster[k] | hunter[i]) == hunter[i])
                res++;
        }
        cout << res << " ";
    }
}

signed main()
{
    quickcin();
    int _ = 1;
    // cin >> _;
    while (_--)
    {
        solve();
    }
}
      • 0
        @ 2024-10-17 11:50:46 
        #pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("abm,avx,mmx,popcnt,sse,sse2,sse3,ssse3,sse4")
#include <bits/stdc++.h>
#define pb push_back
#define PII pair<int, int>
#define PDI pair<double, int>
#define all(x) x.begin(), x.end()
#define quickcin() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
const int N = 1e4 + 10, M = 2e5 + 10, MINRAND = 0, MAXRAND = 1e9;

mt19937 rnd1(time(0));
mt19937_64 rnd2(time(0));
uniform_int_distribution<> int_mt(MINRAND, MAXRAND);
uniform_real_distribution<> double_mt(MINRAND, MAXRAND);
int n, m;
vector<string> hunter;
char must[N];
int ans[N], able[N];
bool st[10];
unordered_map<string, int> mp, mp2;
void dfs(int u, int sz, string res)
{
    if (sz == -1)
    {
        sort(all(res));
        res.erase(unique(all(res)), res.end());
        if (!mp2[res])
            ans[u] += mp[res];
        mp2[res] = 1;
        return;
    }
    if (sz == hunter[u].size() - 1)
    {
        st[sz] = 1, dfs(u, sz - 1, res + hunter[u][sz]);
        return;
    }
    st[sz] = 1, dfs(u, sz - 1, res + hunter[u][sz]);
    st[sz] = 0, dfs(u, sz - 1, res);
    return;
}
void solve()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        for (auto j : s)
        {
            if (j >= 'A' && j <= 'Z')
            {
                able[i] = 1;
                break;
            }
        }
        must[i] = s[s.size() - 1];
        hunter.pb(s);
    }
    for (int i = 0; i < m; i++)
    {
        string s;
        cin >> s;
        sort(all(s));
        s.erase(unique(all(s)), s.end());
        mp[s]++;
    }
    for (int i = 0; i < n; i++)
    {
        if (!able[i])
        {
            cout << 0 << " ";
            continue;
        }
        mp2.clear();
        dfs(i, hunter[i].size() - 1, "");
        cout << ans[i] << " ";
    }
}

signed main()
{
    quickcin();
    int _ = 1;
    // cin >> _;
    while (_--)
    {
        solve();
    }
}
        • 0
          @ 2024-10-16 20:17:10

          前置知识:

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

          2024.10.16-秋招-第3题-狩猎大比拼

          Information

          ID
          143
          Time
          1000ms
          Memory
          256MiB
          Difficulty
          7
          Tags
          # Submissions
          173
          Accepted
          20
          Uploaded By
          1. About
          2. Contact Us
          3. Privacy
          4. Terms of Service
          5. Copyright Complaint
          6. Language
          7. Legacy mode
          8. Theme
          2. 湘ICP备2023007293号
          3. Worker 0, 26ms
          4. Powered by Hydro v4.14.1 Community