Maximize the Largest Component (Hard Version)
- 题意:
给定一个 \(n\times m\) 的网格,由“.”和“#”字符组成。
如果从该组中的任何单元格开始,通过仅移动到该组中共享一个共同边的另一个单元格,就可以到达该组中的任何其他单元格,则一组“#”单元格形成一个连通分量。其大小为该组中的单元格数量。
在一次操作中,选择任意一行 \(r\) 和任意一列 \(c\),然后将行 \(r\)和列 \(c\) 中的每个单元格设置为 "#"。
问在最多执行一次操作后,可以实现的“#”个单元格的最大连通分量的最大可能大小。
ps:保证所有测试用例中的 $ n \cdot m $ 的总和不超过 $ 10^6 $。
- 思路:
我们考虑到执行操作不会使答案更劣,所以我们一定会执行这次操作。
考虑到 \(n\times m\leq 10^6\),那么我们可以暴力枚举选择哪行哪列。
考虑到如果在枚举内部统计答案不好做,哥们考虑预处理答案,那么可以单点算贡献。
我们看下一个点会在选哪行哪列时产生贡献。
显然如果该点在原本的图上最左边可到达 \(l1\),最右可到达 \(r1\),最上可到达 \(l2\),最下 \(r2\) 的话,那么哥们会发现,只要我们选的行在 \([l2-1,r2+1]\) 的区间内或所选的列在 \([l1-1,r1+1]\) 的区间内,都可以产生贡献。
那么我们将我们的选择也抽象成一个矩阵,第 \(i\) 行 \(j\) 列记录的就是我们选第 \(i\) 行第 \(j\) 列的答案。
然后就变成一个套路的矩阵中一块的加减法,直接弄一个矩阵差分即可转为 \(O(1)\) 处理,最后再转回来即可,记得特殊处理你选的那行和那列的答案。
时间复杂度 \(O(nm)\)。
标签:题目,该组,单元格,矩阵,国庆,答案,到达,我们 From: https://www.cnblogs.com/Nefertariqwq/p/18447149