Processing math: 100%

2018-2019 ICPC NEERC Southern Subregional Contest

7/13
总结:只会做水题


题目链接

A

  • 建图bfs,把 (sum,mod) 看成每个点的状态。
  • 可以发现的是长度可以很长,但对于同一个 sum 余数只有 [0,9] 这十种,故状态数最多 d·s 种。

B

题意

题解


C

  • 显然是线段树的题,赛时想了没想出怎么保证复杂度。
  • 实际上,设置区间的 max,min,lazy
  • 一开始建树将所有点赋值为 k, 若一个区间 max 更新的数量,直接对这个区间进行 lazy标记。反之,则递归更新直接更新到底,虽然这样看起来很费时,实际上更新到底的节点(天)以后都不用再更新了,因为需要的量已经够了。
  • 实际上就是一个线段树区间 max,min,lazy 组合题。

D

模拟即可


E

  • 一个直观的感觉是, d 太大会使得很多任务都要做,这样可能不是最优,因为耽误了可能 d 更小的没做,不是最优解。d 太小的话会使很多任务不能做,导致时间用不完,不是最优解。
  • 故可先二分一个最大 d 使得完成所有能完成的任务在 t 时间内,但这可能不是最优的,因为可能 d 稍微大一点,虽然不能完成所有能完成的任务在 d 时间内,但多完成了一些在 d 较小的时候没有完成的,最优解只可能在这两者之间。
  • 故二分最大 d, 最优再判一下 d+1d 谁最优。

F

贪心即可


G

题意

题解


H

模拟即可


I

题意

题解


J

题意

题解


K

模拟即可


L

题意

题解


M

题意

题解