acgo题库
  • 首页
  • 题库
  • 学习
  • 天梯
  • 备赛

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
  • 竞赛
  • 讨论
  • 团队
  • 商城
登录
注册
题目详情提交记录(0)
  • # 官方题解|欢乐赛#38 T6

    T6 看似比较麻烦,我们不妨转化一下思路:在某一个时间段 ttt 上看到的所有仙女棒是前面第 t−m∼tt-m \sim tt−m∼t 时间段上释放的所有仙女棒。那么问题就转化成了:找一个时间段,长为 m+1m+1m+1,使得这个时间段上释放的仙女棒最多。 如果我们要让一个仙女棒在一个时间段上释放的次数最多,根据贪心的思想,显然区间左端点应该在这个仙女棒刚刚释放的时候,假设这个仙女棒释放间隔是 aaa,那么这个时间段上仙女棒会释放 ⌊ma⌋+1\left\lfloor \frac{m}{a} \right\rfloor + 1⌊am ⌋+1 次。 同理,两个仙女棒也是如此。我们希望区间左端点选在两个仙女棒同时释放的时刻。问题在于这两个仙女棒在同同时释放的情况下吗?如果两个仙女棒是倍数关系,那么必然存在;如果不是倍数关系,那么两个数的最小公倍数对应的次数时刻是两个仙女棒同时释放的时刻。因此两个仙女棒一定存在同时释放的情况。 因此两个仙女棒总的释放次数就是 ⌊ma⌋+⌊mb⌋+2\left\lfloor \frac{m}{a} \right\rfloor + \left\lfloor \frac{m}{b} \right\rfloor + 2⌊am ⌋+⌊bm ⌋+2。

    userId_undefined
    桌子乱的反义词
    49阅读
    0回复
    0点赞
暂无数据

提交答案之后,这里将显示提交结果~

首页