AT_abc410_f [ABC410F] Balanced Rectangles 题解

前言

最近几场可以切 A~E 了，所以赛时没切掉 F。而且最最令人开心的是只 WA 了一个点的快感，可惜 Atcoder 不给部分分。

小细节

代码中可能出现的错误就放这里了，作者是用的数组和 vector，所以对使用 map 的家人们可能帮助不大。下文无特殊说明默认通过了样例（如果没过且思路正确可以留言让我帮你调）：

样例 RE 了。
- 可能是数组下标访问到负数了，需要在进行统计时初始值赋值为 $H \times W$ ，因为如果整个矩形都是您定义为 $-1$ 的那个字符，就会炸掉。
- 可能是数组开小了，请分析您数组访问时是否越界。
- 还有可能是其他某些地方您写错了，导致 RE，包括其他地方的数组访问。
WA $\times\ 4$ ，可能是您存储需要还原的下标没有存 $H \times W$ ，您可能觉得之后反正都要将其赋值为 $1$ ，没有必要，但是别忘了这题有多测，下一次访问时不一定还是这个位置。
WA $\times\ 2$ ，可能是您存储需要还原的下标有问题，比如一开始加进容器的是 $H$ 而不是 $H \times W$ 。
WA $\times\ 1$ ，可能是您跟我一样在最后将统计数组清空时是用 int k = v.size() - 1，然后进行操作再 pop_back()，再将变量的值减一，并且判的是 while (k)，那么改成 while (k + 1) 即可。

如果都没有问题，那么只有您自己调试了。

解题思路

由于题目要求选出一个矩形，使得里面包含 . 的数量等于 # 的数量，所以我们可以将 . 视为

1

，# 视为

-1

，问题就转化为了求内部所有元素之和为

0

的矩形数量。

求解的话需要枚举矩形左上角和右下角再进行求和，于是一个

\mathcal{O}(H^3W^3)

的超朴素算法就出来了。再使用前缀和优化一下可以做到

\mathcal{O}(H^2W^3)

。

但是注意到数据范围

HW \leq 3 \times 10^5

，显然 T 到下辈子，因此可以分讨一下。

$H \leq W$ ，那我们可以预处理每一行的前缀和，枚举的时候只需要枚举 $H$ ，相较于枚举 $W$ 减少了一点时间复杂度，为 $\mathcal{O}(H^3W^2)$ 。
$H > W$ ，那我们可以预处理每一列的前缀和，同理，时间复杂度为 $\mathcal{O}(H^2W^3)$ 。

看这样子应该不可以优化了，但是给我们提供了一种思路，如果可以做到

O(HW \times \min(H,W))

的话是可以通过的。先考虑

H = 1, W = 3\times 10^5

的情况，复杂度为

\mathcal{O}(H^2W)

，显然不会超时，只有当

H = \sqrt{3\times 10^5}, W = \sqrt{3\times 10^5}

才会变成

\mathcal{O}(n \sqrt{n})

的时间复杂度（

n = 3\times 10^5

），但是也不会超时，因此我们有了一个大概的方向。

这里才是这道题目最不容易想到的地方吧。注意我说的是“吧”。我们还是跟上面一样进行分讨。

$H \leq W$ ，那么我们就枚举 $u, d$ 表示矩形的第一行位于网格的第 $u$ 行，最后一行位于网格的第 $d$ 行。然后前缀和出每一列中 $u\sim d$ 行的和。

接着就到了重点，首先我们知道对于前缀和数组 $sum$ ，想要算第 $l$ 项到第 $r$ 项的和，只需要计算 $sum_r - sum_{l - 1}$ 即可，那么我们只需要保证 $sum_r - sum_{l - 1} = 0$ 就能满足题意（即第 $u$ 行到第 $d$ 行中第 $l$ 列到第 $r$ 列的和为 $0$ ），移项可得 $sum_r = sum_{l - 1}$ ，由于我们不关心 $l - 1$ 的值是多少，因此只需要前面存在 $sum_k = sum_r$ 即可，因此我们只需要再枚举一个 $j$ ，表示第 $j$ 列，如果 $res$ 出现过，就将答案增加出现次数个 $1$ ，再 $res \to res + sum_j$ ，注意第一次出现 $res = 0$ 时你的答案没有增加，所以需要特殊处理。
$H > W$ ，同理，是需要将上一种情况的行变成列，列变成行即可。

最坏时间复杂度约为

\mathcal{O}(HW\sqrt{HW})

。别忘了多测要清空还有

res

可能为负数导致数组越界哦。

都看这么久了，别忘了三连哦！

CODE：

CPP

#include <bits/stdc++.h>
using namespace std;
#define int long long
string s[300010];
int sum[300010], cnt[600010];
vector<int> v;
signed main() {
	ios::sync_with_stdio(false);
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int n, m;
		cin >> n >> m;
		for (int i = 1; i <= n; i++) {
			cin >> s[i];
			s[i] = " " + s[i];
		}
		int ans = 0;
		if (n <= m) {
			for (int u = 1; u <= n; u++) {
				for (int j = 1; j <= m; j++) {
					sum[j] = 0;
				}
				for (int d = u; d <= n; d++) {
					for (int j = 1; j <= m; j++) {
						sum[j] += (s[d][j] == '.' ? 1 : -1);
					}
					cnt[n * m] = 1;
					v.push_back(n * m);
					int res = n * m;
					for (int j = 1; j <= m; j++) {
						res += sum[j];
						if (cnt[res]) {
							ans += cnt[res];
						}
						cnt[res]++;
						v.push_back(res);
					}
					for (int u : v) {
						cnt[u] = 0;
					}
					v.clear();
				}
			}
		} else {
			for (int l = 1; l <= m; l++) {
				for (int i = 1; i <= n; i++) {
					sum[i] = 0;
				}
				for (int r = l; r <= m; r++) {
					for (int i = 1; i <= n; i++) {
						sum[i] += (s[i][r] == '.' ? 1 : -1);
					}
					cnt[n * m] = 1;
					v.push_back(n * m);
					int res = n * m;
					for (int i = 1; i <= n; i++) {
						res += sum[i];
						if (cnt[res]) {
							ans += cnt[res];
						}
						cnt[res]++;
						v.push_back(res);
					}
					for (int u : v) {
						cnt[u] = 0;
					}
					v.clear();
				}
			}
		}
		cout << ans << "\n";
	}
	return 0;
}

AT_abc410_f [ABC410F] Balanced Rectangles 题解

文章操作

前言

小细节

解题思路

相关推荐

评论

AT_abc410_f [ABC410F] Balanced Rectangles 题解