题解：洛谷 B4050 [GESP202409 五级] 挑战怪物

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：B4050 [GESP202409 五级] 挑战怪物 - 洛谷

【题目描述】

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

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

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

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

【输入】

第一行包含一个正整数t tt，代表测试用例组数。

接下来是t tt组测试用例。对于每组测试用例，第一行包含一个正整数h hh，代表怪物血量。

【输出】

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

【输入样例】

3 6 188 9999

【输出样例】

2 4 -1

【核心思想】

1. 问题分析：怪物血量为h hh，小杨有物理攻击（第i ii次伤害为2 i − 1 2^{i-1}2i−1）和至多一次魔法攻击（选择质数x ≤ x \leqx≤当前血量造成x xx点伤害）。求最少攻击次数使血量恰好为0 00，或判断无法击败。这是一个贪心策略 + 质数判定问题，核心在于分析物理攻击的累积效果与魔法攻击的最佳使用时机。

2. 算法选择：

   • 贪心物理攻击：优先使用物理攻击，因为物理攻击伤害递增，尽早使用低伤害攻击保留灵活性
   • 埃氏筛预处理：预先生成10 5 10^5105以内的质数表，O ( 1 ) O(1)O(1)判定质数
   • 魔法攻击的最优使用：在血量恰好为质数时使用魔法攻击一击必杀，或在物理攻击后血量变为质数时使用

3. 关键步骤：

   • 预处理：埃氏筛生成质数表i s _ p r i m e [ 1..100000 ] is\_prime[1..100000]is_prime[1..100000]
   • 处理每组测试用例：
     • t m p ← 1 tmp \leftarrow 1tmp←1（当前物理攻击伤害），a n s ← 0 ans \leftarrow 0ans←0
     • 循环攻击：
       • 若当前血量x xx为质数：a n s ← a n s + 1 ans \leftarrow ans + 1ans←ans+1，b r e a k breakbreak（魔法攻击一击必杀）
       • 否则：x ← x − t m p x \leftarrow x - tmpx←x−tmp（物理攻击），a n s ← a n s + 1 ans \leftarrow ans + 1ans←ans+1
       • 若x ≤ 0 x \leq 0x≤0：若x < 0 x < 0x<0则a n s ← − 1 ans \leftarrow -1ans←−1，b r e a k breakbreak
       • t m p ← t m p × 2 tmp \leftarrow tmp \times 2tmp←tmp×2
   • 输出结果：a n s ansans

4. 时间/空间复杂度：

   • 时间复杂度：O ( M A X log ⁡ log ⁡ M A X + t ⋅ log ⁡ h ) O(MAX \log \log MAX + t \cdot \log h)O(MAXloglogMAX+t⋅logh)，埃氏筛O ( M A X log ⁡ log ⁡ M A X ) O(MAX \log \log MAX)O(MAXloglogMAX)，每组测试用例物理攻击次数为O ( log ⁡ h ) O(\log h)O(logh)
   • 空间复杂度：O ( M A X ) O(MAX)O(MAX)，质数标记数组

5. 贪心策略与质数判定的核心思想：

   • 物理攻击的累积性：第i ii次物理攻击伤害为2 i − 1 2^{i-1}2i−1，前k kk次物理攻击总伤害为2 k − 1 2^k - 12k−1。物理攻击伤害指数增长，因此攻击次数很少即可造成大量伤害
   • 魔法攻击的最优时机：魔法攻击只能使用一次且必须选择质数。最优策略是在血量恰好为质数时使用，一击清零。若当前血量非质数，先用物理攻击降低血量，再判断是否为质数
   • 贪心正确性：优先使用低伤害物理攻击（1 , 2 , 4 , 8 , … 1, 2, 4, 8, \ldots1,2,4,8,…），保留高伤害物理攻击的灵活性，使得血量更快接近质数或0 00
   • 无法击败的判定：若物理攻击后血量< 0 < 0<0且从未遇到质数血量，则无法恰好清零，输出− 1 -1−1
   • 适用于组合攻击策略优化、质数判定与贪心选择类问题

【算法标签】

#普及 #质数

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;vector<int>prime;// 用于存储所有素数boolis_prime[100010];// 标记数组，用于判断一个数是否为素数// 埃氏筛法，生成从2到n的所有素数voidEratosthenes(intn){memset(is_prime,true,sizeof(is_prime));// 初始化标记数组，全设为true（假定全是素数）is_prime[0]=is_prime[1]=false;// 0和1不是素数for(inti=2;i<=n;i++){if(is_prime[i]){// 如果当前数字是素数prime.push_back(i);// 将其加入素数列表for(intj=2*i;j<=n;j+=i)// 将该素数的倍数全部标记为非素数is_prime[j]=false;}}}intmain(){Eratosthenes(100000);// 生成最多到100000的所有素数intt;// 测试用例数量cin>>t;while(t--){inttmp=1;// 初始攻击力intx;// 怪物的血量cin>>x;intans=0;// 攻击次数while(true){if(is_prime[x]){// 如果当前血量是素数ans++;// 增加一次攻击break;// 结束循环}x-=tmp;// 使用物理攻击，减少血量ans++;// 增加一次攻击次数if(x<=0){// 如果血量小于等于0if(x<0)ans=-1;// 如果血量小于0，设置结果为-1表示失败break;// 结束循环}tmp*=2;// 每次攻击后，攻击力翻倍}cout<<ans<<endl;// 输出结果}return0;}

【运行结果】

3 6 2 188 4 9999 -1