题解：CF1921G Mischievous Shooter

· · 题解

Statement

给定一个 n \times m 的矩形，包含 nm 个方格，给定一个正整数 k。

有一部分格子包含目标。

现在需要选择一个位置 (x,y)，以及一个方向（可选范围：右下，右上，左上，左下）。选中之后，选中方向内所有与 (x,y) 曼哈顿距离不超过 k 的格子内的目标均被击中。

提示：k=3 可能击中的区域的形态如下：

首先 4 种方向如果分类讨论难度会上天。

此时注意到，任意一种合法的操作，均可以通过旋转矩形，对应到另一个方向的某个合法操作。

同时旋转矩形后执行的任意合法操作，总是等价于旋转前的某一个合法操作。

所以，可以仅保留一种选择方向，对矩形的 4 种旋转方式分别计算答案取最大值就可以了。

此处选择什么方向无所谓，我在此以右上方向（即第一张图片）为例。

由于选择区域的形状比较特别，目标总数量难以直接通过前缀和等方式快速得到，所以考虑递推。

令 w(i,j) 表示以 (i,j) 为左下角的区域的目标总数。

考虑其和 w(i-1,j) 的关系。

对于 k=3 大概是下面的样子：

红色加号代表新增区域，蓝色减号代表减少的区域。

可以发现增加的红色区域是第 i 行的 j \sim j+k 列。

减少的蓝色区域是 (i-1,j+k) 为结尾，(i-k-1,1) 为开始的对角线。

那么对每一行预处理从左到右的前缀和，以及预处理左上到右下的对角线前缀和，就可以 O(1) 从 w(i-1,j) 转化到 w(i,j) 了。