P9413 风屿

___w · 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;
}