「Daniel13265 的公开赛」题解【替换】

Daniel13265 · 2020-03-21 22:27:17 · 个人记录

这是「Daniel13265 的公开赛」的官方题解。

子任务 1

直接枚举子串并暴力判断然后使用浮点数判断大小即可。

子任务 2,3,4

由于 \left(10^9\right)^{100}=10^{900} 超出了浮点数上界，需要对每个数取对数改为判断和的大小，这也是此题需要的唯一技巧。

寻找子串可以枚中心与长度，这样时间复杂度是 \mathcal O\left(n^2\right) 的，k 次替换的限制也可以在枚举长度时顺便判断。

子任务 5

由于 k=0，所以实际上就是找回文串，因此可以使用 Manacher 算法。