[MtOI2019]灵梦的计算器 解题报告

题意

有 $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如下：

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}$​−5−20×5101​∣∣∣∣​<2×10−8 。

由于本题数据随机生成，发现最大数据绝对误差不超过 $10^{-3}$ ，可通过本题。

时间复杂度 $O(T)$ ，期望得分： $100~pts$ 。

Sol 7

这种做法出题人在考试前一天晚上想了出来，发现还真的有人用这种做法过了此题

考虑如何构造 $a\not = b$ 时的 $arcf(x)$ ，发现 $a^b =\exp (b \ln a)$ ，所以直接做就好。

时间复杂度 $O(T)$ ，期望得分： $100~pts$ ，
不如Sol6优秀。