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

LPR_318 · 2024-11-09 08:43:44 · 题解

一道更水的黄题。\ 同机房的大佬 Hootime 如此说道。\ 那么话不多说，上思路。\ 对于每一个怪物，我们假设小杨会先使用物理攻击，再使用魔法攻击。

Q：为什么呢？\ A：为什么？难道先用魔法攻击再用物理攻击造成的伤害不是一样的吗？

因为要求最小的攻击次数，所以我们选择的质数应该尽量的大。\ 当物理攻击到 i 次的时候，剩下的血量是一个质数，那就可以直接结束游戏了。\ 因为越早的物理攻击伤害越低，那么剩下的质数就应该是最大的了。\ 那么，上代码：

#include <bits/stdc++.h>
using namespace std;
int t,h;//样例数 
bool prime(int x){
    //判断质数的函数
    //有一个小优化(蒟蒻没学到数学必修一,不会证)
    //所有的大于5的质数都可以写成(6n+1)和(6n-1)的形式
    //写正常的判断质数的函数就可以了
    int fx[2] = {2,4};
    if(x == 1 || x == 4){
        return 0;
    }
    if(x == 2 || x == 3){
        return 1;
    }
    if(x % 2 == 0){
        return 0;
    }
    if(x % 3 == 0){
        return 0;
    }
    for(int i = 5,p = 0;i * i <= x;i+=fx[p],p=!p){
        if(x % i == 0) return 0;
    }
    return 1;
}
int main(){
    cin.tie(0);//cin加速 
    cin >> t;
    while(t--){
        int l = 1,i = 0;//这次物理攻击的伤害,轮数 
        cin >> h;
        while(h > 0){
            if(prime(h)){//如果剩下的血量是质数 
                cout << i+1 << endl;//+1是因为要再攻击一次 
                break;
            }
            h -= l;//减少血量 
            i++;//增加轮数 
            l *= 2;//增加伤害 
        }
        if(prime(h)){//如果剩下的血量是质数(刚刚输出过了)
            continue;
        }
        else if(h < 0){//小于0,说明不能击败怪物(能击败早就击败了)
            cout << -1 << endl;
        }
        else{//特判只用物理攻击就可以的情况 
            cout << i << endl;
        }
    }
    return 0;
}