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+1 和 d 谁最优。
F
贪心即可
G
题意
题解
H
模拟即可
I
题意
题解
J
题意
题解
K
模拟即可