E-光伏场地建设规划(100p)

光伏场地建设规划

问题描述

在祖国西北部有一片广阔的荒地，其中零星分布着一些湖泊、保护区和矿区。整体上这片区域常年光照良好，但也有一些地区光照条件不太理想。某电力公司希望在这里建设多个光伏电站，以生产清洁能源。公司对每平方公里的土地进行了发电评估，其中不能建设的区域发电量为 0kW，可以发电的区域根据光照、地形等因素给出了每平方公里的年发电量 千瓦。现在需要在这片区域中找到集中的矩形区域来建设电站，以获得良好的收益。

输入格式

第一行输入包含四个整数 、、 和 ，分别表示：

• ：调研地区的长度
• ：调研地区的宽度
• ：准备建设的电站边长（电站为正方形）
• ：建设电站的最低要求发电量

接下来 行，每行包含 个整数，表示调研区域每平方公里的发电量。

输出格式

输出一个整数，表示满足条件的区域数量。

样例输入1

2 5 2 6
1 3 4 5 8
2 3 6 7 1

样例输出1

4

样例输入2

2 5 1 6
1 3 4 5 8
2 3 6 7 1

样例输出2

3

样例解释

数据范围

• 
• 
• 
• 每个格子的发电量

题解

二维前缀和

这道题目本质上是一个二维前缀和问题。我们需要找到所有边长为 的正方形区域，其总发电量不小于 。解决这个问题的关键在于高效地计算任意矩形区域的总发电量。

首先，我们需要构建一个二维前缀和数组。对于任意位置 ，前缀和 表示从 到 这个矩形区域内所有格子的发电量之和。

构建前缀和数组的方法是：

sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + grid[i][j]

有了前缀和数组，我们就可以在 O(1) 的时间内计算出任意矩形区域的总发电量。对于左上角为 ，右下角为 的矩形区域，其总发电量为：

area_sum = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1]

然后，我们只需要遍历所有可能的 正方形区域，检查其总发电量是否不小于 。如果满足条件，就将计数器加一。

参考代码

以下是五种语言的实现，都采用了二维前缀和的方法：

• Python

def solve():
    # 读取输入
    m, n, k, p = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(m)]
    
    # 构建前缀和数组
    sum = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + grid[i-1][j-1]
    
    # 计算满足条件的区域数量
    count = 0
    for i in range(k, m + 1):
        for j in range(k, n + 1):
            area_sum = sum[i][j] - sum[i-k][j] - sum[i][j-k] + sum[i-k][j-k]
            if area_sum >= p:
                count += 1
    
    print(count)

solve()

• C

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 1001

int main() {
    int m, n, k, p;
    scanf("%d %d %d %d", &m, &n, &k, &p);
    
    int grid[MAX_SIZE][MAX_SIZE] = {0};
    long long sum[MAX_SIZE][MAX_SIZE] = {0};
    
    // 读取输入并构建前缀和数组
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &grid[i][j]);
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + grid[i][j];
        }
    }
    
    // 计算满足条件的区域数量
    int count = 0;
    fo