自动搬运

查看原文

来自洛谷，原作者为

	___w **

搬运于2025-08-24 22:48:09，当前版本为作者最后更新于2023-06-12 13:34:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P9413 「NnOI R1-T2」风屿

题外话

这一题定义得花里胡哨的。

题意简述

构造一个 $n\times m$ 的矩阵 $g_{i,j}=a_i+b_j$，求 $g$ 的最大连通块的数量及其个数。

题目分析

首先考虑搜索，可以用 dfs 或 bfs 求一个连通块的大小，再统计答案，时间复杂度为 $\mathcal{O}(Tnm)$。但是 $1\le n,m\le 10^5$ 时间和空间上都难以忍受，所以 pass 掉，代码就省略了。

观察样例我们注意到，因为 $g_{i,j}=a_i+b_j$，所以联通块都是个矩形。而这个矩形的长宽分别为 $a,b$ 连续相同的区间的长度，所以大小就为两个连续相同的区间长度的乘积。由于乘法原理，最大矩形的个数就为 $a,b$ 最长连续相同的区间的个数的乘积，时间复杂度为 $\mathcal{O}(T(n+m))$。

所以这题的做法是就 $a,b$ 两个数组的最长连续相同的区间的长度 $l_1,l_2$ 及其个数 $c_1,c_2$，最大块的的大小就为 $l_1l_2$，最大块个数为 $c_1c_2$，代码如下。

代码

由于有相乘，所以可能会爆 int，要开 long long。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5;
int t, n, m, ans1, ans2, a[N], b[N];
signed main() {
	cin >> t;
	while (t--) {
		cin >> n >> m;
		int c = 1, l = 1, len = 1;
		for (int i = 1; i <= n; ++i) {
			cin >> a[i];
			if (i == 1) continue;
			if (a[i] == a[i-1]) ++len;
			else len = 1;
			if (len > l) l = len, c = 1;
			else if (len == l) ++c;
		}
		ans1 = l, ans2 = c;
		c = 1, l = 1, len = 1;
		for (int i = 1; i <= m; ++i) {
			cin >> a[i];
			if (i == 1) continue;
			if (a[i] == a[i-1]) ++len;
			else len = 1;
			if (len > l) l = len, c = 1;
			else if (len == l) ++c;
		}
		ans1 *= l, ans2 *= c;
		cout << ans1 << ' ' << ans2 << '\n';
	}
	return 0;
}