(A卷,200分)- 荒地（Java & JS & Python）

题目描述

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

输入描述

第一行输入为调研的地区长，宽，以及准备建设的电站【长宽相等，为正方形】的边长最低要求的发电量
之后每行为调研区域每平方公里的发电量

输出描述

输出为这样的区域有多少个

用例

题目解析

本题和

一模一样。题解请参考该博客。

还是有区别的，本题中有一句比较有歧义的话

其中不能建设的区域发电量为0kw

这里不能建设是什么意思？不能建设发电站吗？还是说单纯只是产出0发电量？

如果含义是不能建设发电站，那意思应该是，正方形发电站区域如果含0的话，则不能建设发电站。

如果含义是单纯发电量0，那应该没有什么影响。

下面我源码中，我对这两种情况都做了实现了。考试时，大家可以都试试。

2023.04.17

根据考友反馈，发电量为0的区域也可以建站。

基于二维矩阵前缀和的求解方法（更简单）

关于二维矩阵前缀和，请看算法设计 – 前缀和 & 差分数列_伏城之外的博客-CSDN博客

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
let len, wid, sid, min;
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 1) {
    [len, wid, sid, min] = lines[0].split(" ").map(Number);
  }

  if (len && lines.length === len + 1) {
    const matrix = lines.slice(1).map((line) => line.split(" ").map(Number));
    console.log(getResult(len, wid, sid, min, matrix));
    lines.length = 0;
  }
});

/**
 * @param {*} r 调研区域的行数
 * @param {*} c 调研区域的列数
 * @param {*} s 正方形电站的边长
 * @param {*} min 正方形电站的最低发电量
 * @param {*} matrix 调研区域每单位面积的发电量矩阵
 */
function getResult(r, c, s, min, matrix) {
  const preSum = new Array(r + 1).fill(0).map(() => new Array(c + 1).fill(0));

  for (let i = 1; i <= r; i++) {
    for (let j = 1; j <= c; j++) {
      preSum[i][j] =
        preSum[i - 1][j] +
        preSum[i][j - 1] -
        preSum[i - 1][j - 1] +
        matrix[i - 1][j - 1];
    }
  }

  let ans = 0;

  for (let i = s; i <= r; i++) {
    for (let j = s; j <= c; j++) {
      const square =
        preSum[i][j] -
        (preSum[i - s][j] + preSum[i][j - s]) +
        preSum[i - s][j - s];

      if (square >= min) ans++;
    }
  }

  return ans;
}

Java算法源码

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int r = sc.nextInt();
    int c = sc.nextInt();

    int s = sc.nextInt();
    int min = sc.nextInt();

    int[][] matrix = new int[r][c];
    for (int i = 0; i < r; i++) {
      for (int j = 0; j < c; j++) {
        matrix[i][j] = sc.nextInt();
      }
    }

    System.out.println(getResult(matrix, r, c, s, min));
  }

  /**
   * @param matrix 调研区域每单元面积的发电量矩阵
   * @param r 调研区域的长，即行数
   * @param c 调研区域的宽，即列数
   * @param s 正方形电站的边长
   * @param min 正方形电站的最低发电量
   * @return 调研区域内有几个符合要求的正方形发电站
   */
  public static int getResult(int[][] matrix, int r, int c, int s, int min) {
    int[][] preSum = new int[r + 1][c + 1];

    for (int i = 1; i <= r; i++) {
      for (int j = 1; j <= c; j++) {
        preSum[i][j] =
            preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i - 1][j - 1];
      }
    }

    int ans = 0;

    for (int i = s; i <= r; i++) {
      for (int j = s; j <= c; j++) {
        int square = preSum[i][j] - (preSum[i - s][j] + preSum[i][j - s]) + preSum[i - s][j - s];
        if (square >= min) ans++;
      }
    }

    return ans;
  }
}

Python算法源码

# 输入获取
r, c, s, minV = map(int, input().split())
matrix = [list(map(int, input().split())) for i in range(r)]


def getResult(r, c, s, minV, matrix):
    """
    :param r: 调研区域的长
    :param c: 调研区域的宽
    :param s: 正方形电站的边长
    :param minV: 正方形电站的最低发电量
    :param matrix: 调研区域每单位面积的发电量矩阵
    :return: 返回调研区域有几个符合要求正方形电站
    """

    preSum = [[0 for j in range(c + 1)] for i in range(r + 1)]

    for i in range(1, r + 1):
        for j in range(1, c + 1):
            preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i - 1][j - 1]

    ans = 0

    for i in range(s, r + 1):
        for j in range(s, c + 1):
            square = preSum[i][j] - (preSum[i - s][j] + preSum[i][j - s]) + preSum[i - s][j - s]

            if square >= minV:
                ans += 1

    return ans


# 算法调用
print(getResult(r, c, s, minV, matrix))