挑战怪物 题解

题目分析

小杨需要将怪物的血量恰好变为 $0$。他可以执行两种操作：

• 物理攻击：第 $i$ 次使用物理攻击时，造成 $2^{i-1}$ 点伤害。第 $1$ 次物理攻击伤害为 $1$，第 $2$ 次为 $2$，第 $3$ 次为 $4$，以此类推。
• 魔法攻击：至多使用一次，选择一个质数 $x$（不能超过怪物当前血量），造成 $x$ 点伤害。

攻击的先后顺序可以任意安排，我们的目标是最小化总攻击次数，若无法恰好击败则输出 $-1$。

解题思路

1. 总伤害的结构

设小杨一共使用了 $k$ 次物理攻击（$k \ge 0$），第 $1$ 到第 $k$ 次物理攻击的伤害固定为：

如果不使用魔法，则怪物的血量 $h$ 必须正好等于 $2^k - 1$，攻击次数为 $k$。

如果使用一次魔法，造成的伤害为某个质数 $x$，则怪物血量需要满足：

此时总攻击次数为 $k + 1$。

2. 魔法攻击的时机

有人可能担心魔法攻击放在不同的位置会影响可行性。实际上，我们总可以把魔法攻击放在所有物理攻击之后。

因为若剩余血量为 $x$（质数），先使用物理攻击消耗掉前面的 $2^k - 1$ 点血量，怪物当前血量恰好变为 $x$，此时使用魔法攻击 $x$，满足“不超过怪物当前血量”的条件。因此魔法放在最后不会丢失任何可能性。

于是问题简化为：找到一个最小的非负整数 $k$，使得 $x = h - (2^k - 1)$ 等于 $0$ 或一个质数。

• 若 $x = 0$，答案为 $k$（纯物理）；
• 若 $x$ 为质数，答案为 $k + 1$（物理 $k$ 次 + 魔法 $1$ 次）；
• 若无论怎么试都让 $x<0$，则输出 $-1$。

3. 贪心枚举 $k$

从小到大枚举物理攻击次数 $k$（即依次尝试使用 $0,1,2,\dots$ 次物理攻击），一旦找到满足条件的 $x$ 就停止。这是因为：

• 不使用魔法时，总攻击次数为 $k$，随 $k$ 增大而增加；
• 使用魔法时，总攻击次数为 $k+1$，同样随 $k$ 增大而增加。

因此第一次找到的可行方案就是攻击次数最少的方案。

由于 $h \le 10^5$，$2k$ 增长很快，最多只需要尝试 $k \le 17$ 次，非常高效。

算法实现

1. 预处理质数
   使用埃氏筛或线性筛预处理 $1 \sim 100000$ 内的所有质数，便于 $O(1)$ 判断一个数是否为质数。

2. 对每组数据模拟

   • 初始化物理攻击伤害 tmp = 1，攻击次数 ans = 0。
   • 循环：
     • 如果当前剩余血量 x 是质数，则可以用一次魔法击败，答案为 ans + 1，结束。
     • 否则使用一次物理攻击：x -= tmp，攻击次数 ans++。
     • 如果 x == 0，纯物理击败，答案为 ans。
     • 如果 x < 0，无法恰好击败，答案为 -1。
     • 准备下一次物理攻击：tmp *= 2。
   • 输出答案。

这种写法等价于从小到大枚举 $k$，每次先检查当前血量是否为质数（对应魔法收尾），若不是则使用一次物理攻击并继续。

为什么先检查质数再减？
因为我们检查的是“使用 $k$ 次物理攻击后，剩余血量能否用魔法一次性收尾”。而减去物理攻击相当于尝试增加一次物理攻击（$k$ 自增），寻找下一种可能性。

时间复杂度

• 预处理质数：$O(N \log \log N)$，其中 $N = 100000$。
• 每组测试数据：循环次数不超过 $\log_2 h \approx 17$，判断质数 $O(1)$。
• 总体复杂度：$O(N \log \log N + t \log h)$，在题目数据范围下运行极快。

参考代码

cpp
复制
1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 100000;
5vector<int> prime;
6bool is_prime[MAXN + 10];
7
8// 埃氏筛预处理质数
9void Eratosthenes(int n) {
10    is_prime[0] = is_prime[1] = false;
11    for (int i = 2; i <= n; ++i) is_prime[i] = true;
12    for (int i = 2; i <= n; ++i) {
13        if (is_prime[i]) {
14            prime.push_back(i);
15            if ((long long)i * i > n) continue;
16            for (int j = i * i; j <= n; j += i)
17                is_prime[j] = false;
18        }
19    }
20}
21
22int main() {
23    Eratosthenes(MAXN);
24    int t;
25    cin >> t;
26    while (t--) {
27        int x;
28        cin >> x;
29        int tmp = 1;    // 下一次物理攻击的伤害
30        int ans = 0;    // 已使用的物理攻击次数
31        while (true) {
32            // 若剩余血量为质数，使用魔法直接击败
33            if (is_prime[x]) {
34                ans++;      // 加上魔法攻击
35                break;
36            }
37            // 否则使用一次物理攻击
38            x -= tmp;
39            ans++;
40            if (x == 0) {
41                // 纯物理恰好击败
42                break;
43            }
44            if (x < 0) {
45                // 无法恰好击败
46                ans = -1;
47                break;
48            }
49            tmp *= 2;   // 下一次物理伤害翻倍
50        }
51        cout << ans << "\n";
52    }
53    return 0;
54}

代码说明

• is_prime 数组记录每个数是否为质数，由埃氏筛预处理完成。
• 对于每个血量 x，我们模拟不断施加物理攻击的过程。变量 tmp 表示当前轮次物理攻击的伤害值（$1,2,4,\dots$）。
• 每次循环首先判断 x 是否可以直接用一次魔法击败（因为魔法只能用一次，且放在最后一定合法）。如果可以，答案就是当前物理次数 +1。
• 如果不可以，则用一次物理攻击扣除 tmp，物理次数 +1，并更新剩余血量。若剩余血量变为 $0$，则物理攻击恰好击败；若变为负数，说明无法恰好击败，输出 -1。
• 因为数据范围很小，直接模拟完全可行，代码也非常简洁。