【GESP五级真题】挑战怪物（洛谷B4050）题解：质数筛法+动态规划优化，高效攻克魔法攻击策略
2天前
一、题目解读
2024年GESP五级题“挑战怪物（洛谷B4050）”要求玩家计算击败怪物所需的最小攻击次数。怪物血量H可被分解为魔法攻击（消耗质数血量）与物理攻击（每次固定伤害）的组合。题目难点在于如何高效枚举质数与物理攻击的搭配，找到最优解。需结合数学逻辑与算法优化，避免暴力枚举导致的超时。
二、解题思路
1. 质数预处理：采用埃拉托斯特尼筛法生成质数表，减少运行时的质数检测开销。
2. 纯物理攻击判定：通过二进制递增加法（1 << cnt）快速检查是否能用纯物理攻击解决（即血量为2的幂次方）。
3. 魔法+物理组合优化：遍历质数表，用当前质数减少怪物血量，递归检查剩余血量是否可纯物理解决。若可行，则记录魔法+物理的总次数，更新最小攻击数。
4. 动态规划思想：通过预处理与递推，避免重复计算，确保时间复杂度可控。
三、解题步骤
1. 输入处理：读取测试用例数量T及每个血量H，记录最大血量max_h用于质数表范围。
2. 质数预处理：调用sieve(max_h)生成primes表，存储所有不超过max_h的质数。
3. 主循环求解：
对每个h，先调用check_physical(h)判断纯物理攻击次数。
若纯物理可行，记录次数；否则遍历质数表，计算h - p的纯物理次数，若存在则更新最小次数。
4. 输出结果：按测试用例顺序输出最小攻击次数。
四、代码与注释
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<int> primes; // 预计算质数表
// 埃拉托斯特尼筛法预处理质数
void sieve(int max_h) {
vector<bool> is_prime(max_h + 1, true);
is_prime[0] = is_prime[1] = false; // 0和1非质数
for (int i = 2; i <= max_h; ++i) {
if (is_prime[i]) { // 若i是质数
primes.push_back(i); // 加入质数表
for (int j = i * 2; j <= max_h; j += i) {
is_prime[j] = false; // 标记i的倍数
}
}
}
}
// 检查是否能用纯物理攻击击败
int check_physical(int h) {
int sum = 0, cnt = 0; // 累计伤害与次数
while (sum < h) {
sum += (1 << cnt); // 每次伤害为2的cnt次方
cnt++;
}
return (sum == h)? cnt : -1; // 若刚好达到血量，返回次数；否则-1
}
// 主处理函数
int solve(int h) {
int min_attacks = check_physical(h); // 优先检查纯物理方案
// 尝试所有可能的魔法攻击组合
for (int p : primes) {
if (p > h) break; // 质数超过血量时终止遍历
int remaining = h - p; // 剩余血量
if (remaining < 0) continue; // 若魔法攻击溢出，跳过
int physical_attacks = check_physical(remaining);
if (physical_attacks!= -1) { // 若剩余血量可纯物理解决
int total = 1 + physical_attacks; // 1次魔法 + 物理次数
if (min_attacks == -1 || total < min_attacks) {
min_attacks = total; // 更新最小次数
}
}
}
return min_attacks;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); // 加快IO速度
int t, max_h = 0;
cin >> t; // 读取测试用例数量
vector<int> test_cases(t);
// 读取所有测试用例并找出最大值
for (int i = 0; i < t; ++i) {
cin >> test_cases[i];
if (test_cases[i] > max_h) {
max_h = test_cases[i];
}
}
sieve(max_h); // 预处理质数表
for (int h : test_cases) {
cout << solve(h) << "\n"; // 输出每个测试用例的结果
}
return 0;
}五、总结
本题巧妙结合质数特性和动态规划思维，通过预处理质数表规避重复计算，大幅降低时间复杂度。代码中“纯物理攻击判定”利用二进制特性简化判断，而“魔法攻击枚举”则通过质数筛选优化搜索空间。此类算法设计需平衡数学逻辑与编程实现，对竞赛选手的优化意识与代码效率要求较高。掌握埃拉托斯特尼筛法及动态规划思想，可为同类问题提供通用解法。
原创内容 转载请注明出处
