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 ),处理完所有有效拳后求每一行的前缀和即可。 (注意处理边界问题,数组下标不要取越界了)

    資訊

    ID
    907
    時間
    1000ms
    記憶體
    256MiB
    難度
    9
    标签
    遞交數
    97
    已通過
    4
    上傳者