202409-挑战怪物(luogu-B4050)

GESP C++ 2024年9月五级真题，数论-素数、贪心思想考点，难度⭐⭐⭐☆☆，五级来说难度适中。洛谷难度等级普及/提高−

luogu-P10720 [GESP202406 五级] 小杨的幸运数字

题目要求

题目描述

小杨正在和一个怪物战斗，怪物的血量为 $h$，只有当怪物的血量恰好为 $0$ 时小杨才能够成功击败怪物。

小杨有两种攻击怪物的方式：

• 物理攻击。假设当前为小杨第 $i$ 次使用物理攻击，则会对怪物造成 $2^{i - 1}$ 点伤害。
• 魔法攻击。小杨选择任意一个质数 $x$（ 不能超过怪物当前血量），对怪物造成 $x$ 点伤害。由于小杨并不擅长魔法，他只能使用至多一次魔法攻击。

小杨想知道自己能否击败怪物，如果能，小杨想知道自己最少需要多少次攻击。

输入格式

本题单个测试点内有多组测试数据。第一行包含一个正整数 $t$，代表测试用例组数。

接下来是 $t$ 组测试用例。对于每组测试用例，只有一行一个整数 $h$，代表怪物血量。

输出格式

对于每组测试用例，如果小杨能够击败怪物，输出一个整数，代表小杨需要的最少攻击次数，如果不能击败怪物， 输出 $-1$。

输入输出样例 #1

输入 #1

3
6
188
9999

输出 #1

2
4
-1

说明/提示

样例 1 解释

对于第一组测试用例，一种可能的最优方案为，小杨先对怪物使用魔法攻击，选择质数 $5$ 造成 $5$ 点伤害，之后对怪 物使用第 $1$ 次物理攻击，造成 $2^{1 - 1} = 1$ 点伤害，怪物血量恰好为 $0$，小杨成功击败怪物。

数据规模与约定

对于全部的测试数据，保证 $1 \leq t \leq 10$，$1 \leq h \leq 10^5$。

题目分析

解题思路

1. 问题本质
   小杨的攻击方式只有两种：

   • 纯物理：第 $i$ 次伤害 $2^{i-1}$，累加到 $k$ 次时总伤害为 $2^k-1$。
   • 至多一次魔法：任选质数 $x\le h$，造成 $x$ 点伤害，其余用物理补足。
     目标：判断能否把 $h$ 恰好打成 $0$，并求最少攻击次数。

2. 纯物理判定
   先检查 $h$ 是否等于某个 $2^k-1$。
   由于 $2^{17}-1=131071>10^5$，只需枚举 $k\le 16$ 即可。
   若命中，直接返回 $k$。

3. “魔法+物理”枚举
   若纯物理不行，则尝试“用一次魔法”。
   设魔法伤害为质数 $x$，则剩余血量 $h-x$ 必须能被“纯物理”恰好耗尽。
   为使总攻击次数最少，应：

   • 让 $x$ 尽可能大，这样 $h-x$ 尽可能小，所需物理次数 $k$ 也尽可能小；
   • 从大到小枚举质数 $x$，一旦找到合法的 $(x,k)$ 组合，即可提前退出，此时总次数为 $k+1$ 必为最小。
     枚举范围：$x\in[2,h]$ 中的所有质数。
     单次判断 $h-x$ 是否为 $2^k-1$ 的过程与步骤 2 相同，$O(\log h)$。

4. 质数判断优化
   数据范围 $h\le 10^5$，质数个数不足 1 万，每次用 $\sqrt{x}$ 试除即可。
   若值域再大，可预先用埃氏筛打出质数表，再顺序遍历质数，复杂度可降至“质数个数 × 单次判断耗时”，即 $O(\pi(h)\cdot\log h)$。其中 $\pi(h)$ 表示不超过 $h$ 的质数个数，$\log h$ 来自判断 $h-x$ 是否为 $2^k-1$ 的逐次比较。

5. 输出
   若上述两步均失败，说明无法恰好击败怪物，输出 $-1$；否则输出最小攻击次数。

复杂度与边界

• 时间复杂度：
  外层循环 $t$ 组数据。
  对每组血量 $h$，先 $O(\log h)$ 判断“纯物理”是否可行；
  再枚举所有不超过 $h$ 的质数 $x$（共 $\pi(h)$ 个），对每个质数做一次 $O(\log h)$ 的“剩余血量是否为 $2^k-1$”判定。
  因此单组耗时 $O\!\left(\pi(h)\cdot\log h\right)$，总复杂度
  

  $$O\!\left(t\cdot\pi(h)\cdot\log h\right),$$

  
  其中 $\pi(h)\approx \dfrac{h}{\ln h}$，在 $h\le 10^5$ 时约 9592 个质数，完全可接受。

• 空间复杂度：仅用到若干整型变量与循环计数器，$O(1)$ 辅助空间。

该思路清晰、实现简短，无需高深算法，五级考生易于掌握；若进一步追求极致速度，可预先生成质数表并缓存 $2^k-1$ 集合。

示例代码

#include <cmath>
#include <iostream>

// 判断 target 能否被“纯物理攻击”恰好耗尽
// 物理攻击第 i 次伤害为 2^(i-1)，累加和为 2^i - 1
// 返回所需攻击次数；若无法恰好耗尽则返回 -1
int is_equal_sum(int target) {
    int tmp_sum = 0;
    for (int j = 0; j < 31; j++) {
        tmp_sum += std::pow(2, j);   // 累加 2^0 + 2^1 + ... + 2^j
        if (tmp_sum == target) {
            return j + 1;            // 恰好耗尽，返回攻击次数
        }
        if (tmp_sum > target) {
            return -1;               // 已超过，后续更大，直接失败
        }
    }
    return -1;                       // 31 次内仍无法满足
}

// 朴素判断 n 是否为质数
bool is_prime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int i = 2; i <= std::sqrt(n); i++) {
        if (n % i == 0) {
            return false;            // 出现因子，非质数
        }
    }
    return true;                       // 无因子，质数
}

int main() {
    int t;
    std::cin >> t;                     // 读入测试组数

    for (int i = 0; i < t; i++) {
        int h;
        std::cin >> h;                 // 当前怪物血量

        // 先尝试“纯物理攻击”能否恰好击败
        int count = is_equal_sum(h);

        // 再尝试“使用一次魔法攻击”的情况：枚举魔法伤害质数 x
        // 从大到小枚举，可更快找到最小总次数（贪心思想）
        for (int j = h; j >= 2; j--) {
            if (is_prime(j)) {         // j 是质数，可作为魔法伤害
                int target = h - j;    // 剩余需用物理攻击补足的血量
                if (target == 0) {
                    count = 1;         // 仅一次魔法攻击即可
                    break;
                }
                int tmp_count = is_equal_sum(target);
                if (tmp_count != -1) { // 剩余血量可被物理攻击恰好耗尽
                    int total = tmp_count + 1; // 总次数 = 物理次数 + 1 次魔法
                    if (count == -1 || total < count) {
                        count = total; // 更新最小次数
                    }
                    // 由于从大到小枚举，首次合法即最优，可提前退出
                    break;
                }
            }
        }
        std::cout << count << std::endl;
    }
    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号