1 条题解

  • 0
    @ 2024-6-4 15:59:27

    x,yx,y 足够大的时候显然有个合理的贪心:当 x,yx,y 都大的时候 - -- -。当 xx 不太大但 yy 较大的时候 - -+ -。这样很对,因为 max(x,y)\max(x,y) 每两次减小 33。从这你也能看出范围是哪里来的了。

    发现 x,yx,y 都很小的时候 bfs 一下就做完了。打个表发现可以做到 ct+3c\le t+3

    最后不写 bfs,写一些 44 次跳两格的方法可以减少代码量,但是操作次数 2y+eps2y+eps 大约是 3t3t,但是看上去给了好多分。比赛描述中“正序写题不一定好”就因为这题虽然简单但谁愿意在 B 写个 bfs。你猜为什么 B 奖金大于 C。

    可以发现如果想得到完全最优解,在足够大的地方开始 bfs 就可以了,具体地,后面留下充足调整空间即可。足够大开到 100100 足矣。

    信息

    ID
    945
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    (无)
    递交数
    2
    已通过
    0
    上传者