自动搬运

查看原文

来自洛谷，原作者为

	ty_mxzhn 打破天生的劣等感 || 写作悔恨的未来

搬运于2025-08-24 23:05:46，当前版本为作者最后更新于2024-12-23 14:42:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

给你一个大小为 $n\times m$ 的整点坐标系，上面有 $k$ 个关键点。求标记完 $k$ 个以这些点为圆心的半径为 $r$ 的圆上的整点后有多少个没标记的点。

$k\le 10^6,n,m,r\le 10^3$。

题解

考虑预处理出一个点正上方和正下方最近的关键点。这个是好处理的。

对于每个点，根据刚才的距离可以用差分标记周围的点。

也即：我们把一个列圆心上所有的横向拓展距离一起算出，然后再用差分总体标记。

后记

像梦一般地去爱

像爱一般地去梦

你曾经说过 即使是空想

只要相信

总有一天会实现的