[PYTHON-CSP-前缀和]20210402-邻域均值

题目

描述

样例

• 样例1
  输入

  4 16 1 6
  0 1 2 3
  4 5 6 7
  8 9 10 11
  12 13 14 15
  1
  2
  3
  4
  5

  输出

  7
  1

• 样例2
  输入

  11 8 2 2
  0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0
  0 7 0 0 0 7 0 0 7 7 0
  7 0 7 0 7 0 7 0 7 0 7
  7 0 0 0 7 0 0 0 7 0 7
  7 0 0 0 0 7 0 0 7 7 0
  7 0 0 0 0 0 7 0 7 0 0
  7 0 7 0 7 0 7 0 7 0 0
  0 7 0 0 0 7 0 0 7 0 0
  0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12

  输出

  83
  1

链接👉邻域均值

题解

暴力破解三四层循环必超时
可以看到块移动后再求和时，有很大一部分是重复的，不需要再计算
所以提升速度的话可以记录下每次求和的结果，通过各个位置间关系算出所需结果
特征：移动区域求和->前缀和
附一篇大佬的前缀和算法：前缀和(差分)算法
所以这里我们可以记录从(0,0)到(i,j)的正方形的和，求哪一部分进行计算即可

NT：记录的仅是小矩形的，不是之前的所有数据！！！
由上图可以得到所求区域的递推公式
为了计算简便（首行首列计算矩形的时候要考虑边界），考虑再增一行一列
具体代码如下

n, L, r, t, = map(int, input().split())
A = [[0 for i in range(n+1)]]
for i in range(n):
    temp = list(map(int, input().split()))
    temp.insert(0, 0)   # 首列为0
    A.append(temp)

S = [[0 for i in range(n+1)] for i in range(n+1)] # 初始化前缀和数组

for i in range(1,n+1):
    for j in range(1,n+1):
        S[i][j] = A[i][j] + S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] # 递推表达式


count = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        y_s = max(1,j - r) # 找到矩形所有求值边界
        y_e = min(j + r,n) # 考虑数组边界问题
        x_s = max(1,i - r)
        x_e = min(i + r,n)

        Sum = S[x_e][y_e] - S[x_e][y_s-1] - S[x_s-1][y_e] + S[x_s-1][y_s-1] # 邻域内元素和
        c = (x_e-x_s+1)*(y_e-y_s+1)  # 计算有多少个像素
        
        if Sum/c <= t:
            count += 1

print(count)

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

附录

前缀和常和差分数组结合
就比如20210902非零段划分那个题。。。
附一个链接可以一起看👉非零段划分