题解：AT_abc461_d [ABC461D] Count Subgrid Sum = K

Ethan_sun · 2026-06-07 08:20:58 · 题解

solution

暴力加前缀和优化可过。

首先显然有一个 \mathcal{O}(n^3m^3) 最低级的暴力，写出来就是下面这样。

::::error[暴力]

#include <bits/stdc++.h>
#define debug(a) cerr << (#a) << " = " << (a) << endl;
#define int long long
#define maxn 510
#define endl '\n'
using namespace std;

int h, w, k;
int s[maxn][maxn];
void solve() {
    cin >> h >> w >> k;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            char ch; cin >> ch;
            s[i][j] = ch - '0';
        }
    }
    int ans = 0;
    for (int i = 1; i <= h; i++) {
        for (int ii = i; ii <= h; ii++) {
            for (int j = 1; j <= w; j++) {
                for (int jj = j; jj <= w; jj++) {
                    int cnt = 0;
                    for (int a = i; a <= ii; a++) {
                        for (int b = j; b <= jj; b++) {
                            cnt += s[a][b];
                        }
                    }
                    ans += (cnt == k);
                }
            }
        }
    }
    cout << ans << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t; t = 1;
//  cin >> t;
    while (t--) solve();
    return 0;
}

::::

可这实在是太慢了，我们考虑优化。

观察最里面两层循环，每次都需要计算这样一个矩形的和，直接使用二维前缀和即可做到单次 \mathcal{O}(1) 的查询。如果你不会二位前缀和，这里能给你介绍。

所以去掉里面两层循环后复杂度降至 \mathcal{O}(n^2m^2)，我赛后试了一下，直接过了。

code

给出 submission。

::::success[展开]

#include <bits/stdc++.h>
#define debug(a) cerr << (#a) << " = " << (a) << endl;
#define int long long
#define maxn 510
#define endl '\n'
using namespace std;

int h, w, k;
int s[maxn][maxn];
int sum[maxn][maxn];
int query(int x, int y, int xx, int yy) {
    return sum[xx][yy] - sum[x - 1][yy] - sum[xx][y - 1] + sum[x - 1][y - 1];
}
void solve() {
    cin >> h >> w >> k;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            char ch; cin >> ch;
            s[i][j] = ch - '0';
        }
    }
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            sum[i][j] = s[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    }
    int ans = 0;
    for (int i = 1; i <= h; i++) {
        for (int ii = i; ii <= h; ii++) {
            for (int j = 1; j <= w; j++) {
                for (int jj = j; jj <= w; jj++) {
                    ans += (query(i, j, ii, jj) == k);
                }
            }
        }
    }
    cout << ans << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t; t = 1;
//  cin >> t;
    while (t--) solve();
    return 0;
}

::::