正睿AB班大讨论

Day1

T1

题意：给一个 \(01\) 二维数组，定义一个 \(1\) 的权值为它到最近的 \(1\) 的欧几里得距离，问整个数组中 \(1\) 的权值之和。 \(n,m\le 3\times 10^3\) 。

\(sol\) ：枚举每个 \(1\) 点，然后考虑左上角的答案（其他方向是相同的）。我们从上往下从左往右枚举，对于同一行左边的每个位置，处理出目前最靠下的 \(1\) 设为 \(low[j]\)，然后对每个点只需要考虑同一行上一个询问点和上一个询问点到这个点之间的每个 \(low[j]\) （因为上一个询问点之前的点显然不如上一个询问点优秀）。

\(code\) ：https://www.luogu.com.cn/paste/24tswiq9

T2

题意：给一个有 \(n\) 个网格的四连通网格块，然后如果有四个块形成的正方形（一个田字形）中有三个点是黑色，那么就把另一个点染成黑色。问你一开始最少把多少个点染成黑色，使得整个图形最终会被染成黑色。 \(n\le 10^5\) 。

\(sol\) ：一个贪心策略是贴着两个相邻边的边界染色，然后好像只需要考虑左上，我好像不能理解，所以把左上，左下，右上，右下都试一试就好了。因为用 \(map\) 来存图所以带个 \(\log\) 。

\(code\) ：https://www.luogu.com.cn/paste/icevjw5x

T3

题意