题解：P10320 勇气（Courage）

· · 题解

update on 2024/12/22：重新排版了一下 LaTeX，然后更新了一下码风。

题目分析

其实这道题就是个纯数学题，先要找到规律，然后再对解这道题的公式进行推导，把公式推出来以后，再考虑一下一些特殊情况，然后这道题基本就解决了。此题编程不难，但就是推导过程比较麻烦（其实也不算特别麻烦），需要用到高一上学期的数学内容，主要是指数和对数部分。

可以先列举前面几种情况，找一下规律。

设攻击力的初始值为 x。

经过第一次变换，攻击力变为 x^2，其实可以看成是 \frac{x^2}{1}，也就是\frac{x^2}{2^0}；经过第二次变换，攻击力变为 (\frac{x^2}{2})^2，也就是 \frac{x^4}{2^2}；经过第三次变换后，攻击力变为 (\frac{x^4}{8})^2，也就是 \frac{x^8}{2^6}；经过第四次变换，攻击力变为 (\frac{x^8}{128})^2，也就是 \frac{x^{16}}{2^{14}}。

看到这里以后，其实已经不难发现，经过 i(i\in \mathbb N^*) 次强化以后，攻击力的分子值变为 x^{2^i}，分母的值变为 2^{2^i-2}，整个式子变为 \frac{x^{2^i}}{2^{i-2}}，并且要满足 \frac{x^{2^i}}{2^{i-2}} \ge 2^n。

把分母乘到不等号右边并化简，得

x^{2^i} \ge 2^{n-2+2^i}

可以把 2^i 看成一个整体，作 x 的指数，然后进行对数运算并化简，得 （后面的为了方便计算，我就把不等号变成等号了，最后记得向上取整）

2^i = (n-2+2^i)\log_x2

把 \log_x2 移到等号左边，得

2^i·\log_2x = n-2+2^i

再进行移项、合并同类项，得

2^i(\log_2x-1) = n-2

把 \log_2x-1 移到等号右边，得

2^i=\frac{n-2}{\log_2x-1}

再对 i 取对数并向上取整，得

i=\lceil\log_2{\frac{n-2}{\log_2x-1}}\rceil

其实这就已经出来了，直接编程，算出来 \log_2{\frac{n-2}{\log_2x-1}} 的值，并对其进行向上取整就解得 i 的值，然后再输出答案即可。

不过这道题当中有一些特殊情况需要判断：

而且请注意：先判断特殊情况，而且一定要按照上面这三个特殊情况的顺序编程，即先判断输出 inf，再判断输出 0，最后再判断输出 1，否则会导致有几个测试点过不去。（我最开始特判顺序就搞错了，就导致一直有3个测试点过不去）

好了，分析完了，上代码。

Code

#include<bits/stdc++.h> 
using namespace std;
int x, n;
int main()
{
    cin >> x >> n;
    if(x == 2 && n > 2){ //特判输出inf的情况
        cout << "inf";
        return 0;
    }
    if(log2(x) >= n){ //特判输出0的情况
        cout << "0";
        return 0;
    }
    if(2 * log2(x) >= n){ //特判输出1的情况
        cout << "1";
        return 0;
    } 
    double a1, a2; //a1是等号右边对数的真数中的分母，a2是等号右边整个对数的值，记得开double
    int ans; //存储答案
    a1 = log2(x) - 1;   
    a2 = log2((n - 2) * 1.0 / a1);
    ans = ceil(a2); //记得答案要向上取整
    cout << ans;
    return 0;
}