1 条题解

  • 0
    @ 2023-11-2 13:43:34

    遍历每一个会造成伤害的拳头(xn,ym)(x ≤ n, y ≤ m),差分标记其所有伤害到的范围,最后对每一行求一下前缀和,其中有数字的是被损伤的部分。 对于某一拳(x,y)(x, y),损伤半径rr,我们可以遍历他所能覆盖到的所有行,即max(1,xr)max(1, x - r)min(n,x+r)min(n, x + r),对这行所能伤害到范围的左边界到右边界+1的差分数组标记(这里可以用勾股定理求出,已知一直角边 ll 和斜边 rr ),处理完所有有效拳后求每一行的前缀和即可。 (注意处理边界问题,数组下标不要取越界了)

    • 1

    信息

    ID
    907
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    85
    已通过
    3
    上传者