P8938 [DTOI 2023] 小狗哥哥 题解报告

pikiuk · 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 分。