GESP 2024年9月 挑战怪物 题解｜枚举详细讲解

这是 GESP 2024年9月 的一道枚举题。题目本身不难，但有几个地方特别容易出错，我把踩过的坑都写出来，希望能帮刚学到这里的朋友少走弯路。

题目来源：ACGO A75460 ｜ 2024年9月 五级赛事场次：2024年9月 五级

一、题目信息

题目名称：挑战怪物

赛事场次：2024年9月 五级

难度定位：五级

涉及知识点：贪心 数论 枚举

题目链接：https://www.acgo.cn/problemset/info/75460

坑点（无数人 WA 的核心）

• 枚举范围的确定；如何用循环穷举全部可能。

题意简述

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

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

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

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

前置知识

这道题用到的前置知识不多，我们先把它补齐，即使你刚学到这里也能看懂。

枚举的思路：把所有可能的情况逐个试一遍，在数据范围允许的前提下，这是最稳妥的做法。关键是确定枚举的范围和顺序，避免重复或漏解。

二、思路分析

先看清楚题目要我们做什么

把题目读两遍，我们提取出关键信息：输入是什么、要输出什么、有哪些约束条件。这道题考查的是枚举，属于这类题里比较基础的一道，把题目要求一步步翻译成代码逻辑就能解决。

我的思考过程

读完题之后，我的第一反应是这样的：挑战怪物：物理攻击第 i 次造成 2ⁱ-1 伤害，魔法至多一次造成任意质数伤害。观察到 2ⁱ-1 的二进制全为 1，用若干次物理攻击可凑出任意「连续低位 1」的数，剩余部分需用一次质数魔法补足，故枚举物理攻击次数并判断剩余是否为质数。

需要说明的是，上面这个思路是把题目要求直译成代码得到的，没有用到什么高级技巧。对于这类基础题，读准题意加写对边界比追求巧妙解法更重要，因为考试里这种题是必须拿满分的。

三、完整代码 + 逐行注释

#include <bits/stdc++.h>
using namespace std;
vector<int> prime;
bool is_prime[100010];
void Eratosthenes(int n) {
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= n; ++i) is_prime[i] = true; // 遍历
for (int i = 2; i <= n; ++i) { // 遍历
if (is_prime[i]) { // 判断
prime.push_back(i);
if ((long long)i * i > n) continue; // 判断
for (int j = i * i; j <= n; j += i) // 遍历
is_prime[j] = false;
}
}
}
int main() {
Eratosthenes(100000);
int t;
cin>>t; // 读入
while(t–){
int tmp=1;
int x;
cin>>x; // 读入
int ans=0; // 初始化
while(1){
if(is_prime[x]){ // 判断
ans++;
break;
}
x-=tmp;
ans++;
if(x<=0){ // 判断
if(x<0)ans=-1; // 判断
break;
}
tmp*=2;
}
cout<<ans<<"\\n"; // 输出
}
}

四、代码分段拆解

为了看得更清楚，我们把代码按功能分成几段解释。

第一步：引入头文件

#include <bits/stdc++.h>
using namespace std;

#include <iostream> 提供输入输出功能，using namespace std; 让我们能直接写 cin、cout 而不用加前缀。这两行是几乎所有 C++ 程序的开头，照写即可。

第二步：读入数据

cin>>t;
cin>>x;

注意变量的类型要能装下题目的数据。数据可能超过 21 亿时要改用 long long。

第三步：核心处理逻辑

for (int i = 2; i <= n; ++i) is_prime[i] = true;
for (int i = 2; i <= n; ++i) {
for (int j = i * i; j <= n; j += i)
while(t–){

这一段是整道题的关键，也是枚举的体现。看循环的三个要素：从哪里开始、什么时候结束、每次怎么变化。这三个要素任何一个写错，结果都会不对。

第四步：按要求输出

cout<<ans<<"\\n";

输出格式必须和题目要求的完全一致。很多同学算法完全正确却因为少了一个换行或者空格多寡不对而 WA，这种分丢得最可惜。

五、实例模拟

光看代码可能还不够直观，我们用题目的样例实际跑一遍，看看程序是怎么走的。

以题目的第一组样例为例：

样例输入

3
6
188
9999

样例输出

2
4
-1

把这份输入代进代码，程序会先把数据依次读入，然后进入循环逐个判断，把满足条件的值累积起来，最后按格式输出。建议你对照着代码在纸上走一遍前两次循环，确认自己对每一步的理解都和程序一致。

六、踩坑总结

下面是做这道题时最容易出错的地方，对照自己的代码检查一下：

七、知识点拓展

最后总结一下这道题带给我们的通用经验：

• 本题考查枚举的基本写法，这类题在考试中属于必得分项，要练到能默写。
• 写完代码后建议自己造几组边界数据测试，特别是最小值和最大值。
• 同一知识点在不同场次反复出现，把这道题的写法吃透，后面遇到同类题可以直接套用。

八、适用人群

如果你已经掌握枚举的基本写法，这道题可以用来巩固手感。

如果这篇题解对你有帮助，欢迎点赞收藏。后续我会继续按场次整理 2024年9月 五级 的真题，关注我可以第一时间看到更新。有更好的写法也欢迎在评论区交流。