DDOSvoid's Blog

2020年广西省CCPC大学生程序设计竞赛 A Landlord

发表于 更新于 分类于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

题目描述

给定一个 $n\times m$ 的矩阵，矩阵中所有值为正整数，求有多少子矩阵的和小于 $k$

$n\times m\le 2\times 10^5$

Solution

注意到 $n$ 和 $m$ 一定有一维小于 $\sqrt{2\times 10^5}$，不妨设其为 $n$

那么我们枚举行的上下边界，然后列的左端点和右端点可以 $two ~~pointer$

时间复杂度 $O(n^2m)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <cstdio>
#include <vector>
#define maxn 200010
#define ll long long
using namespace std;

int n, m; ll k;

vector<int> a[maxn], b[maxn];
vector<ll> s[maxn];

inline ll get_sum(int k, int l, int r) {
    return s[k][r] - s[k][l - 1];
}

void work() {
    cin >> n >> m >> k; 
    for (int i = 1; i <= n; ++i) b[i].resize(m + 1);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            int x; cin >> x;
            b[i][j] = x;
        }
    if (n > m) {
        for (int i = 1; i <= m; ++i) a[i].resize(n + 1);
        for (int i = 1; i <= n; ++i) 
            for (int j = 1; j <= m; ++j) a[j][i] = b[i][j];
        swap(n, m);
    }
    else for (int i = 1; i <= n; ++i) a[i] = b[i];
    for (int i = 1; i <= m; ++i) {
        s[i].resize(n + 1); 
        for (int j = 1; j <= n; ++j) 
            s[i][j] = s[i][j - 1] + a[j][i];
    } ll ans = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; ++j) {
            int r = 0; ll sum = 0;
            for (int l = 1; l <= m; ++l) {
                while (r < m && sum + get_sum(r + 1, i, j) <= k) ++r, sum += get_sum(r, i, j);
                ans += r - l + 1; sum -= get_sum(l, i, j);
            }
        }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work();
    return 0;
}