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

disangan233

2019-08-24 14:42:13

Solution

## 题意 有 $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$。