盛日辉的博客
0%

蓝桥-统计子矩阵

发表于 分类于 ， ，

题目

https://www.lanqiao.cn/problems/2109/learning/

思路

思路并不难理解，要非常注意的是二维前缀和的区间计算的下标。

代码

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
# 统计子矩阵

n, m, k = map(int, input().split())

# matrix = [[0 for _ in range(m + 1)]] + [[0] for _ in range(n)]
# # print(matrix)
# for i in range(n):
#     matrix[i + 1].extend(map(int, input().split()))
# # print(matrix)
# # 计算前缀和
# pre_sum = [[0 for _ in range(m+1)] for _ in range(n+1)]
# for i in range(1,n + 1):
#     for j in range(1,m + 1):
#         pre_sum[i][j]=pre_sum[i-1][j]+pre_sum[i][j-1]-pre_sum[i-1][j-1]+matrix[i][j]

# 因为后面用不到原始矩阵值，所以用另一种初始化前缀和的方法
pre_sum = [[0 for _ in range(m + 1)]]
for i in range(1, n + 1):
    pre_sum.append([0] + list(map(int, input().split())))
    for j in range(1, m + 1):
        pre_sum[i][j] += pre_sum[i - 1][j] + pre_sum[i][j - 1] - pre_sum[i - 1][j - 1]

# for i in pre_sum:
#     print(i)

res = 0
for i1 in range(1, n + 1):
    for i2 in range(i1, n + 1):
        z = 0
        j1 = 1
        for j2 in range(1, m + 1):
            while pre_sum[i2][j2] - pre_sum[i1 - 1][j2] - pre_sum[i2][j1 - 1] \
                    + pre_sum[i1 - 1][j1 - 1] > k:  # 某一个的区间和比k大了，移动j1，缩小区间
                j1 += 1
            #     print("z=",z,i1, i2, j1, j2)
            # print(i1, i2, j1, j2)
            res += j2 - j1 + 1
print(res)

上面是我的，用二维前缀和做的，下面是别人在计算前缀和的时候只对列上做了计算。

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
n, m, k = map(int, input().split())
a = [[0] for i in range(n)]
a.insert(0, [0] * (m + 1))
for i in range(1, n + 1):  # 从a[1][]开始，读矩阵
    a[i].extend(map(int, input().split()))
s = [[0] * (m + 1) for i in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        s[i][j] = s[i - 1][j] + a[i][j]
ans = 0
for i in s:
    print(i)
for i1 in range(1, n + 1):
    for i2 in range(i1, n + 1):
        j1 = 1;
        z = 0
        for j2 in range(1, m + 1):
            z += s[i2][j2] - s[i1 - 1][j2]
            while z > k:
                z -= s[i2][j1] - s[i1 - 1][j1]
                j1 += 1
            ans += j2 - j1 + 1
            print(i1, i2, j1, j2, j2 - j1 + 1, z)
print(ans)