本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷B4050 [GESP202409 五级] 挑战怪物 - 洛谷【题目描述】小杨正在和一个怪物战斗怪物的血量为h hh只有当怪物的血量恰好为0 00时小杨才能够成功击败怪物。小杨有两种攻击怪物的方式物理攻击。假设当前为小杨第i ii次使用物理攻击则会对怪物造成2 i − 1 2^{i-1}2i−1点伤害。魔法攻击。小杨选择任意一个质数x xxx xx不能超过怪物当前血量对怪物造成x xx点伤害。由于小杨并不擅长魔法他只能使用至多一次魔法攻击。小杨想知道自己能否击败怪物如果能小杨想知道自己最少需要多少次攻击。【输入】第一行包含一个正整数t tt代表测试用例组数。接下来是t tt组测试用例。对于每组测试用例第一行包含一个正整数h hh代表怪物血量。【输出】对于每组测试用例如果小杨能够击败怪物输出一个整数代表小杨需要的最少攻击次数如果不能击败怪物输出− 1 -1−1。【输入样例】3 6 188 9999【输出样例】2 4 -1【核心思想】问题分析怪物血量为h hh小杨有物理攻击第i ii次伤害为2 i − 1 2^{i-1}2i−1和至多一次魔法攻击选择质数x ≤ x \leqx≤当前血量造成x xx点伤害。求最少攻击次数使血量恰好为0 00或判断无法击败。这是一个贪心策略 质数判定问题核心在于分析物理攻击的累积效果与魔法攻击的最佳使用时机。算法选择贪心物理攻击优先使用物理攻击因为物理攻击伤害递增尽早使用低伤害攻击保留灵活性埃氏筛预处理预先生成10 5 10^5105以内的质数表O ( 1 ) O(1)O(1)判定质数魔法攻击的最优使用在血量恰好为质数时使用魔法攻击一击必杀或在物理攻击后血量变为质数时使用关键步骤预处理埃氏筛生成质数表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←ans1b 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←ans1若x ≤ 0 x \leq 0x≤0若x 0 x 0x0则a n s ← − 1 ans \leftarrow -1ans←−1b r e a k breakbreakt m p ← t m p × 2 tmp \leftarrow tmp \times 2tmp←tmp×2输出结果a n s ansans时间/空间复杂度时间复杂度O ( M A X log ⁡ log ⁡ M A X t ⋅ log ⁡ h ) O(MAX \log \log MAX t \cdot \log h)O(MAXloglogMAXt⋅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)质数标记数组贪心策略与质数判定的核心思想物理攻击的累积性第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 00且从未遇到质数血量则无法恰好清零输出− 1 -1−1适用于组合攻击策略优化、质数判定与贪心选择类问题【算法标签】#普及 #质数【代码详解】#includebits/stdc.husingnamespacestd;vectorintprime;// 用于存储所有素数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(inti2;in;i){if(is_prime[i]){// 如果当前数字是素数prime.push_back(i);// 将其加入素数列表for(intj2*i;jn;ji)// 将该素数的倍数全部标记为非素数is_prime[j]false;}}}intmain(){Eratosthenes(100000);// 生成最多到100000的所有素数intt;// 测试用例数量cint;while(t--){inttmp1;// 初始攻击力intx;// 怪物的血量cinx;intans0;// 攻击次数while(true){if(is_prime[x]){// 如果当前血量是素数ans;// 增加一次攻击break;// 结束循环}x-tmp;// 使用物理攻击减少血量ans;// 增加一次攻击次数if(x0){// 如果血量小于等于0if(x0)ans-1;// 如果血量小于0设置结果为-1表示失败break;// 结束循环}tmp*2;// 每次攻击后攻击力翻倍}coutansendl;// 输出结果}return0;}【运行结果】3 6 2 188 4 9999 -1