【GESP五级真题】挑战怪物（洛谷B4050）题解：质数筛法+动态规划优化，高效攻克魔法攻击策略

一、题目解读

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;
}

五、总结

本题巧妙结合质数特性和动态规划思维，通过预处理质数表规避重复计算，大幅降低时间复杂度。代码中“纯物理攻击判定”利用二进制特性简化判断，而“魔法攻击枚举”则通过质数筛选优化搜索空间。此类算法设计需平衡数学逻辑与编程实现，对竞赛选手的优化意识与代码效率要求较高。掌握埃拉托斯特尼筛法及动态规划思想，可为同类问题提供通用解法。