题目描述
有若干名猎人来到草原狩猎，每名猎人在狩猎开始前需要灵活搭配技能用于击杀猎物。每个技能由十六进制数[0, F]中的某个数来表达，每个猎人都必须选择8种不重复的技能。草原上有各种各样的猎物，猎物的弱点也由十六进制数[0, F]中的某个数字表达。猎人能击杀某种猎物的前提是同时满足以下条件：
- 猎人的技能可以覆盖猎物的所有弱点。
- 猎人的技能至少包含
[A, F]中的其中一个技能。 - 猎人最后一个技能需要至少命中猎物的任意一个弱点。
每种猎物的数量可以认为是无限的，但每种猎物只能被同一名猎人击杀一次。请帮忙计算每个猎人可击杀的猎物种类数量，击杀猎物总数最多的猎人将获得“赏金猎人”的称号。
输入描述
- 第一行：两个整数，分别表示猎人数量
n和猎物种类数量m（1 <= n <= 1000，1 <= m <= 200000）。 - 第二行：
n个字符串，每个字符串表示一名猎人的技能组合，技能由十六进制数[0, F]中的字符组成，长度为8，且不重复。 - 第三行：
m个字符串，每个字符串表示一种猎物的弱点，弱点由十六进制数[0, F]中的字符组成，长度范围为[1, 60]，可能包含重复字符。
输出描述
输出一个数组，数组中的每个元素是对应猎人最多可击杀的猎物数量。
用例输入
3 5
028F415A 2340789E 043BCD12
0222F44A 44C 8848A 002B2 F4415CA
2 0 1
- 第1名猎人具备的技能为
028F415A，最后一个技能A可以命中第1、3、5种猎物，但不包含第5种猎物的弱点C，因此只能击杀第1和第3种猎物。 - 第2名猎人具备的技能为
2340789E，没有任何猎物包含弱点E，因此可击杀的猎物数量为0。 - 第3名猎人具备的技能为
043BCD12，虽然这些技能可以覆盖第2、4种猎物，但最后一个技能2无法命中第2种猎物的弱点，因此只能击杀第4种猎物。
2 3
7519FCB0 01234567
25351727 A0 19C00
1 0
- 第1名猎人可以击杀第2种猎物。
- 第2名猎人虽然技能可以覆盖第1种猎物，且最后一个技能
7可以命中猎物的弱点，但不包含[A, F]中的任一技能，因此不能击杀猎物。
解题思路
-
问题建模：
- 该问题可以看作是一个集合覆盖问题，猎人的技能集合需要覆盖猎物的弱点集合。
- 需要满足三个条件：
- 猎人的技能覆盖猎物的所有弱点。
- 猎人的技能中包含至少一个
[A, F]中的技能。 - 猎人的最后一个技能需要命中猎物的弱点。
-
数据结构设计：
- 使用二维数组
lr存储每个猎人的技能集合，lr[i][j]表示猎人i是否拥有技能j。 - 使用二维数组
lw存储每个猎物的弱点集合，lw[i][j]表示猎物i是否包含弱点j。
- 使用二维数组
-
算法实现：
- 遍历每个猎人，检查其技能是否满足条件：
- 检查是否包含
[A, F]中的技能。 - 检查是否覆盖猎物的所有弱点。
- 检查最后一个技能是否命中猎物的弱点。
- 检查是否包含
- 统计每个猎人可击杀的猎物数量。
- 遍历每个猎人，检查其技能是否满足条件：
-
优化：
- 使用位运算或哈希表可以优化技能和弱点的存储和查询。
代码（60%）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
#include<string>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<set>
#include<list>
#include<sstream>
#include<bitset>
#include<stack>
#include<climits>
using namespace std;
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m; // n个猎人，m个猎物cin >> n >> m;vector<vector<int>> lr(n, vector<int>(256, 0)); // 猎人技能vector<string> lr_t(n); // 猎人技能字符串vector<vector<int>> lw(m, vector<int>(256, 0)); // 猎物弱点string temp;// 输入猎人技能for (int i = 0; i < n; i++) {cin >> temp;lr_t[i] = temp;for (int j = 0; j < temp.size(); j++) {lr[i][temp[j]] = 1;}}// 输入猎物弱点for (int i = 0; i < m; i++) {cin >> temp;for (int j = 0; j < temp.size(); j++) {lw[i][temp[j]] = 1;}}// 计算每个猎人可击杀的猎物数量for (int i = 0; i < n; i++) {// 检查是否有[A-F]技能bool flag = false;for (int k = 'A'; k <= 'F'; k++) {if (lr[i][k]) {flag = true;break;}}if (!flag) {cout << 0 << " ";continue;}int res = 0;for (int j = 0; j < m; j++) {// 检查最后一个技能是否命中int t = lr_t[i].back();if (lw[j][t] == 0) continue;// 检查是否覆盖猎物弱点bool ok = true;for (int k = 'A'; k <= 'F'; k++) {if (lw[j][k] == 1 && lr[i][k] == 0) {ok = false;break;}}if (!ok) continue;for (int k = '0'; k <= '9'; k++) {if (lw[j][k] == 1 && lr[i][k] == 0) {ok = false;break;}}if (ok) res++;}cout << res << " ";}return 0;
}
