2022 年牛客多校第十场 B 题题解

B Fall Guys-Perfect Match

题意：给定 $n\times nn\; \backslash times\; n$ 的棋盘，每个格子有一个颜色 $a_{i,j}a\_\{i,j\}$，保证每种颜色出现次数不超过 $2020$ 次。问站在哪个格子，到达任意一个格子的曼哈顿距离的最大值最小。$n\le 1\times 10^{3}n\; \backslash leq\; 1\backslash times\; 10^3$，颜色数目 $m\le n^{2}m\; \backslash leq\; n^2$。

解法：最大值最小，考虑二分答案。首先将曼哈顿距离 $\mathrm{\mid }x\mathrm{\mid }+\mathrm{\mid }y\mathrm{\mid }|x|+|y|$ 转化为切比雪夫距离 $\max (\mathrm{\mid }x\mathrm{\mid },\mathrm{\mid }y\mathrm{\mid })\backslash max(|x|,|y|)$，则二分一个切比雪夫距离 $dd$，考虑对首先枚举颜色，对于该颜色的全部格点向外侧扩张 $dd$ 得到若干个矩形，对这些矩形取并集，那么二分所需要检查的条件为，每种颜色的矩形面积并的交（单个颜色内部并，之后再对每个颜色的面积并取交集）是否非空。

对于少量的矩形面积并（例如本题的 $2020$ 个），可以直接对矩形的边进行离散化，然后暴力的染色填格子（只有 $20\times 2020\backslash times\; 20$ 个格子），然后再恢复回来即可，只需要用差分在总的方格上 $\mathcal{O}(k)\backslash mathcal\; O(k)$ 的修改即可计算出当前的矩形面积并。最后检查是否有格子被覆盖了 $mm$ 次即可。总时间复杂度 $\mathcal{O}(n^2{k}^2\log n)\backslash mathcal\; O(n^2k^2\backslash log\; n)$。

具体代码实现可以参看 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=53486593