题解：CF1731D Valiant's New Map

FiraCode · 2024-08-17 08:01:18 · 题解

显然的，答案有单调性，可以二分。

然后对于二分的值 l，我们把原矩阵所以值 a_{i,j} 变为 \min(a_{i,j},l)。

然后就是枚举周长为 l 的正方形的右下角，然后看区间和是不是 l^3 即可。

#include <bits/stdc++.h>

using namespace std;

int T;
int n, m;
vector<vector<int>> a, s;

bool check(int l) {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + min(l, a[i][j]);
        }
    }

    for (int i = l; i <= n; ++i) {
        for (int j = l; j <= m; ++j) {
            if (s[i][j] - s[i - l][j] - s[i][j - l] + s[i - l][j - l] >= l * l * l) return true;
        }
    }

    return false;
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        a.resize(n + 1);
        s.resize(n + 1);
        for (int i = 0; i <= n; ++i) a[i].resize(m + 1), s[i].resize(m + 1);

        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                scanf("%d", &a[i][j]);

        int l = 1, r = min(n, m);
        while (l < r) {
            int mid = (l + r + 1) >> 1;

            if (check(mid)) l = mid;
            else r = mid - 1;
        }

        printf("%d\n", l);
    }

    return 0;
}