自动搬运

查看原文

来自洛谷，原作者为

	pikiuk “Back like I never left!”

搬运于2025-08-24 22:43:56，当前版本为作者最后更新于2023-01-19 20:05:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

命题思路：

• 审题人说要有一个签到题。
• 最开始准备的签到涉及了位运算，被毙掉了。
• 考虑不要太毒瘤，决定出一个模拟题。
• idea 来源 hollow knight，非常优秀的游戏。
• 每次强化完骨钉原来三刀的小怪还是三刀。
• 本来放这个题想让大家都开心开心，但是看结果好像大家都不开心。
• 应该是给足了部分分，大样例的强度也不会很低。
• 模拟 / 小学数学。

题解报告：

算法 0

• 我不会这题！

• 期望得分 $0$ 分。

算法 0.5

• 我不会这题！但我会观察！

• 注意到随机数据下给出的数据大概率不合法！

• 输出 $0$，期望得分 $45$ 分。

• 时间复杂度 $\mathcal{O}(1)$。

算法 1

• 我会枚举！
• 枚举 $p$，并代回矩阵模拟，统计合法 $p$ 的个数。
• 注意到 $p$ 的大小不超过 $\max\{a_i\}$。
• 综合时间复杂度 $\mathcal{O}(\max\{a_i\}\times n\times k)$。
• 期望得分 $70$ 分，结合之前的部分分期望得分 $60$ 分。

算法 2

• 我会观察性质！
• 不难发现并证明，合法的 $p$ 的取值是一个区间。
• 因此我们由序列逆推得出合法的区间。
• 首先由不等式 $(a_i-1)\times i\times p < m\le a_i\times i\times p$ 可以得出 $p$ 的一个取值范围。
• 注意到这里有个 corner case，要解 $p$ 肯定要移向，$a_i=1$ 要略过，还有就是上取整和下取整要弄清楚，以及有一段点是 $<$ 而不是 $\leq$，出题人为此拍了 $3000$ 组数据，应该卡全了。
• 然后取 $n$ 个区间的交即可。
• 综合时间复杂度 $\mathcal{O}(n)$。
• 期望得分 $100$ 分。