[MtOI2019]灵梦的计算器 解题报告
disangan233
2019-08-24 14:42:13
## 题意
有 $3$ 个实数 $n$,$a$,$b$ ( $4\le n\le 5,5 \le a,b \le 10$ ) ,你求到了一个函数 $f(n)=n^a+n^b$的值。
求满足 $\lfloor f(n) \rfloor = \lfloor f(n') \rfloor$ 的 $n'$ 的变化范围,即 $\max (n')-\min (n')$ 。
## Solutions
### Sol 1
直接枚举,时间复杂度 $O\left(\frac{T\times \max (ans)}{eps}\right)$,期望得分:$?~pts$。
### Sol 2
考虑优化枚举。发现可以利用二分的思想,让精度不断提高。
时间复杂度 $O\left(T\log {10^{bit}} \right)$,单次精度为 $10^{\lfloor \log_{10} ans\rfloor-bit}$,期望得分:$65~pts$。
可以对 $10$,$12$,$19$ 号数据点打表,总得分 $80~pts$。
### Sol 3
这是来自 $\mathsf o \color{red} \mathsf{uuan}$ 的面向数据和SPJ的骗分方法。
考虑SPJ比较的是绝对误差,并且本题单次询问答案很小,随便试试就可以了,配合 **Sol 2** 可以得到更高的分数。
期望得分:$65-100~pts$,~~本来分数会更低,但是因为这个题太简单导致出题人不想卡。~~
$65~pts$ Code如下:
```cpp
int main()
{
long long t, seed, op;
cin >> t >> seed >> op;
if (op) cout << t * 0.00003058;
else cout << t * 0.00001028;
return 0;
}
```
### Sol 4
这是来自 $\mathsf N \color{red} \mathsf{aCly~Fish}$ 的方法。
要求出:使 $n^a+n^b$ 向下取整后相等的 $n$ 的差值,考虑牛顿迭代。
设 $y=\lfloor n^a+n^b\rfloor$,$f(x)=x^a+x^b$。
只要求出 $f(x)=y$ 和 $f(x)=y+1$ 两个方程的解,做差即可。
时间复杂度 $O(T\log y)$,期望得分:$80-100~pts$ 。
### Sol 5
单独考虑 $a=b$ 时的答案,设 $y=\lfloor n^a+n^b\rfloor=\lfloor 2n^a\rfloor$,$f(x)=2x^a$。
做法同**Sol 4**,但是因为$f(x)$可以构造出反函数 $arcf(x)=\sqrt[a] \frac{x}{2}$,可以单次 $O(1)$ 询问。
时间复杂度 $O(T)$,期望得分 $30~pts$,结合 **Sol 4** 可以得到 $90~pts$。
### Sol 6
发现在 $a \not = b$ 时无法轻松构造 $arcf(x)$,所以 **Sol 5** 无法继续扩展,考虑换一种 $O(1)$ 的反函数求法。
可以通过计算和画图发现 $f(x)$ 在区间 $[0,+\infty)$ 单调递增,考虑用 $g(x)=bx^k$ 去逼近 $f(x)$,可以发现当 $\Delta y=1$ 时,$|\Delta x|$ 是很小的。~~(其实也可以目力测量或者目力看样例)~~
因为 $|\Delta x|$ 很小,考虑用微分计算近似值来替换 $arcf(x)$
$$
\Delta y \approx \mathrm dy=f'(x) \Delta x
$$
所以可得 $\Delta x$ 的快速计算式
$$
\Delta x \approx \frac{\mathrm dy}{f'(x)}
$$
所以可推导出 $\Delta n'$ 的答案
$$
\Delta n' \approx \frac{1}{an^{a-1}+bn^{b-1}}
$$
对于本题极限数据来说,单次绝对误差 $\delta n'\approx \left|\sqrt[10] \frac{{2\times 5^{10}+1}}{2}-5-\frac{1}{20\times 5^{10}}\right| < 2\times 10^{-8} $。
由于本题数据随机生成,发现最大数据绝对误差不超过 $10^{-3}$,可通过本题。
时间复杂度 $O(T)$,期望得分:$100~pts$。