2024年GESP五级真题解析：挑战怪物的最优攻击策略

3天前比赛题解47

一、问题背景分析

题目要求计算击败怪物需要的最少攻击次数，规则如下：

物理攻击：第n次攻击造成2^(n-1)点伤害
魔法攻击：消耗1次攻击造成质数点伤害
可以任意组合两种攻击方式

二、算法设计思路

预处理阶段：使用埃拉托斯特尼筛法生成质数表
纯物理检查：验证能否仅用物理攻击击败怪物
混合攻击计算：尝试所有"1次魔法+N次物理"的可能组合

三、完整代码解析（带详细注释）

#include <iostream>
#include <vector>
#include <cmath>
using namespACe std;

vector<int> primes; // 存储预处理好的质数

// 筛法预处理质数表（时间复杂度O(n log log n)）
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]) {
            primes.push_back(i);
            // 标记所有i的倍数为非质数
            for (int j = i * 2; j <= max_h; j += i) {
                is_prime[j] = false;
            }
        }
    }
}

// 检查纯物理攻击的可能性（利用位运算优化）
int check_physical(int h) {
    int sum = 0, cnt = 0;
    // 物理攻击伤害呈2的幂次增长：1,2,4,8...
    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;
        // 检查剩余血量能否用物理攻击解决
        int physical_attacks = check_physical(remaining);
        if (physical_attacks != -1) {
            // 总攻击次数 = 1次魔法 + 物理攻击次数
            int total = 1 + physical_attacks;
            // 更新最小值
            if (min_attacks == -1 || total < min_attacks) {
                min_attacks = total;
            }
        }
    }
    return min_attacks;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); // 优化输入输出
    
    int t, max_h = 0;
    cin >> t;
    vector<int> test_cases(t);
    
    // 读取输入并找出最大血量
    for (int i = 0; i < t; ++i) {
        cin >> test_cases[i];
        max_h = max(max_h, test_cases[i]);
    }
    
    sieve(max_h); // 预处理质数表
    
    for (int h : test_cases) {
        cout << solve(h) << "\n";
    }
    
    return 0;
}