自学内容网 自学内容网
自学内容网 > 正文

【2024年华为OD机试】(A卷,200分)- 探索地块建立 （Java & JS & Python&C/C++）

🕗 发布于 2025-01-16 00:20 华为od  java  javascript  C/C++  python  

在这里插入图片描述

一、问题描述

题目描述

给一块nm的地块，相当于nm的二维数组，每个元素的值表示这个小地块的发电量；

求在这块地上建立正方形的边长为c的发电站，发电量满足目标电量k的地块数量。

输入描述

第一行为四个按空格分隔的正整数，分别表示n, m, c, k

后面n行整数，表示每个地块的发电量

输出描述

输出满足条件的地块数量

用例

输入

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

输出

4

说明
无

题目解析

本题最优解题思路是使用：二维矩阵前缀和。

解题思路

  1. 构建前缀和矩阵：

    • 创建一个(n+1) x (m+1)的前缀和矩阵prefixSum，用于存储从(0,0)到(i,j)的子矩阵的发电量总和。
    • 遍历每个地块的发电量，更新前缀和矩阵：
      • prefixSum[i+1][j+1] = prefixSum[i+1][j] + prefixSum[i][j+1] - prefixSum[i][j] + grid[i][j]

  2. 计算每个可能的发电站的发电量：

    • 遍历每个可能的发电站位置，计算其发电量：
      • 对于每个左上角位置(i, j)，计算右下角位置(i+c, j+c)的发电量：
        • sum = prefixSum[i+c][j+c] - prefixSum[i+c][j] - prefixSum[i][j+c] + prefixSum[i][j]
    • 如果计算出的发电量等于目标电量k，则计数器加1。

  3. 输出结果：

    • 输出满足条件的地块数量。
二维矩阵前缀和
  • 前缀和矩阵：前缀和矩阵prefixSum的每个元素prefixSum[i][j]表示从(0,0)到(i-1,j-1)的子矩阵的发电量总和。
  • 计算子矩阵发电量：通过前缀和矩阵，可以快速计算任意子矩阵的发电量：
    • sum = prefixSum[i2][j2] - prefixSum[i2][j1] - prefixSum[i1][j2] + prefixSum[i1][j1]

通过这种方法，我们可以高效地计算出满足条件的地块数量。时间复杂度为O(n * m)，其中n和m分别是地块的行数和列数，因为我们只需要遍历地块几次。

二、JavaScript算法源码

以下是 JavaScript 代码的详细中文注释与讲解。此代码的功能是计算一个 n * m 的地块中，所有边长为 c 的正方形区域内的电量总和是否大于等于目标电量 k，并统计满足条件的正方形区域数量。

代码功能

  1. 输入格式：

    • 第一行输入四个整数：n（地块行数）、m（地块列数）、c（正方形边长）、k（目标电量）。
    • 接下来输入 n 行，每行 m 个整数，表示地块中每个位置的电量。

  2. 处理逻辑：

    • 使用二维前缀和（Prefix Sum）快速计算任意正方形区域内的电量总和。
    • 遍历所有可能的边长为 c 的正方形区域，统计满足电量总和大于等于 k 的区域数量。

代码：

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

// 创建 readline 接口
const rl = readline.createInterface({
  input: process.stdin, // 输入流
  output: process.stdout, // 输出流
});

const lines = []; // 存储输入行
let n, m, c, k; // 定义变量：地块行数、列数、正方形边长、目标电量

// 监听输入事件
rl.on("line", (line) => {
  lines.push(line); // 将输入行存入数组

  // 如果输入行数为 1，解析第一行数据
  if (lines.length === 1) {
    [n, m, c, k] = lines[0].split(" ").map(Number); // 解析并转换为数字
  }

  // 如果输入行数为 n + 1，开始处理数据
  if (n && lines.length === n + 1) {
    // 解析地块矩阵
    const matrix = lines.slice(1).map((line) => line.split(" ").map(Number));

    // 调用算法函数并输出结果
    console.log(getResult(matrix, n, m, c, k));

    // 清空输入行数组
    lines.length = 0;
  }
});

/**
 * 计算满足条件的正方形区域数量
 * @param {*} matrix n*m的地块
 * @param {*} n 地块行数
 * @param {*} m 地块列数
 * @param {*} c 正方形的发电站边长为c
 * @param {*} k 目标电量k
 */
function getResult(matrix, n, m, c, k) {
  // 初始化二维前缀和数组
  const preSum = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0));

  // 计算前缀和
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; 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 = c; i <= n; i++) {
    for (let j = c; j <= m; j++) {
      // 计算当前正方形区域内的电量总和
      const square =
        preSum[i][j] - // 右下角前缀和
        (preSum[i - c][j] + preSum[i][j - c]) + // 减去上方和左方的前缀和
        preSum[i - c][j - c]; // 加上左上角重复减去的部分

      // 如果电量总和大于等于目标电量，统计
      if (square >= k) ans++;
    }
  }

  return ans; // 返回结果
}

详细讲解：

1. 输入获取
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
  • readline 模块：
    • 用于从控制台逐行读取输入。
    • rl.on("line", callback) 监听输入事件。
rl.on("line", (line) => {
  lines.push(line); // 将输入行存入数组

  if (lines.length === 1) {
    [n, m, c, k] = lines[0].split(" ").map(Number); // 解析第一行数据
  }

  if (n && lines.length === n + 1) {
    const matrix = lines.slice(1).map((line) => line.split(" ").map(Number));
    console.log(getResult(matrix, n, m, c, k)); // 调用算法函数
    lines.length = 0; // 清空输入行数组
  }
});
  • 输入处理：
    1. 第一行解析为 n, m, c, k。
    2. 接下来的 n 行解析为地块矩阵 matrix。
    3. 调用 getResult 函数计算结果并输出。
2. 二维前缀和
const preSum = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0));
  • 初始化前缀和数组：
    • preSum 是一个 (n+1) * (m+1) 的二维数组，初始值为 0。
    • 多一行一列是为了方便边界计算。
for (let i = 1; i <= n; i++) {
  for (let j = 1; j <= m; j++) {
    preSum[i][j] =
      preSum[i - 1][j] + // 上方前缀和
      preSum[i][j - 1] - // 左方前缀和
      preSum[i - 1][j - 1] + // 左上角重复计算的部分
      matrix[i - 1][j - 1]; // 当前地块的电量
  }
}
  • 计算前缀和：
    • preSum[i][j] 表示从 (0,0) 到 (i,j) 的矩形区域内的电量总和。
    • 公式：
      preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + matrix[i-1][j-1]
3. 计算正方形区域电量
for (let i = c; i <= n; i++) {
  for (let j = c; j <= m; j++) {
    const square =
      preSum[i][j] - // 右下角前缀和
      (preSum[i - c][j] + preSum[i][j - c]) + // 减去上方和左方的前缀和
      preSum[i - c][j - c]; // 加上左上角重复减去的部分

    if (square >= k) ans++; // 统计满足条件的区域
  }
}
  • 计算正方形区域电量：
    • 对于每个右下角 (i,j)，计算边长为 c 的正方形区域内的电量总和。
    • 公式：
      square = preSum[i][j] - preSum[i-c][j] - preSum[i][j-c] + preSum[i-c][j-c]
    • 如果 square >= k，则统计。

代码运行示例

示例 1：

输入：

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

执行过程：

  1. 解析输入：
    • n = 3, m = 3, c = 2, k = 5。
    • 地块矩阵：
      [ [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9] ]
  2. 计算前缀和：
    [ [0, 0, 0, 0],
  [0, 1, 3, 6],
  [0, 5, 12, 21],
  [0, 12, 27, 45] ]
  3. 遍历正方形区域：
    • (2,2)：12 - 1 - 3 + 0 = 8（满足条件）
    • (2,3)：21 - 3 - 6 + 1 = 13（满足条件）
    • (3,2)：27 - 5 - 12 + 1 = 11（满足条件）
    • (3,3)：45 - 12 - 21 + 5 = 17（满足条件）
  4. 输出结果：
    4
示例 2：

输入：

2 2 1 3
1 2
3 4

执行过程：

  1. 解析输入：
    • n = 2, m = 2, c = 1, k = 3。
    • 地块矩阵：
      [ [1, 2],
  [3, 4] ]
  2. 计算前缀和：
    [ [0, 0, 0],
  [0, 1, 3],
  [0, 4, 10] ]
  3. 遍历正方形区域：
    • (1,1)：1（不满足条件）
    • (1,2)：3（满足条件）
    • (2,1)：4（满足条件）
    • (2,2)：10 - 1 - 3 + 0 = 6（满足条件）
  4. 输出结果：
    3

总结

  1. 功能：

    • 统计满足条件的正方形区域数量。

  2. 优点：

    • 使用二维前缀和优化计算，时间复杂度为 O(n * m)。

  3. 适用场景：

    • 适用于需要快速计算矩形区域和的场景。

如果您有其他问题，欢迎随时提问！

三、Java算法源码

以下是 Java 代码的详细中文注释与讲解。此代码的功能是计算一个 n * m 的地块中，所有边长为 c 的正方形区域内的电量总和是否大于等于目标电量 k，并统计满足条件的正方形区域数量。

代码功能

  1. 输入格式：

    • 第一行输入四个整数：n（地块行数）、m（地块列数）、c（正方形边长）、k（目标电量）。
    • 接下来输入 n 行，每行 m 个整数，表示地块中每个位置的电量。

  2. 处理逻辑：

    • 使用二维前缀和（Prefix Sum）快速计算任意正方形区域内的电量总和。
    • 遍历所有可能的边长为 c 的正方形区域，统计满足电量总和大于等于 k 的区域数量。

代码：

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in); // 创建 Scanner 对象，用于读取输入

    // 读取输入的第一行数据
    int n = sc.nextInt(); // 地块行数
    int m = sc.nextInt(); // 地块列数
    int c = sc.nextInt(); // 正方形边长
    int k = sc.nextInt(); // 目标电量

    // 初始化地块矩阵
    int[][] matrix = new int[n][m];

    // 读取地块矩阵数据
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = sc.nextInt(); // 读取每个位置的电量
      }
    }

    // 调用算法函数并输出结果
    System.out.println(getResult(matrix, n, m, c, k));
  }

  /**
   * 计算满足条件的正方形区域数量
   * @param matrix n*m的地块
   * @param n 地块行数
   * @param m 地块列数
   * @param c 正方形的发电站边长为c
   * @param k 目标电量k
   * @return 可以建设几个发电站
   */
  public static int getResult(int[][] matrix, int n, int m, int c, int k) {
    // 初始化二维前缀和数组
    int[][] preSum = new int[n + 1][m + 1];

    // 计算前缀和
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; 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 = c; i <= n; i++) {
      for (int j = c; j <= m; j++) {
        // 计算当前正方形区域内的电量总和
        int square =
            preSum[i][j] - // 右下角前缀和
            (preSum[i - c][j] + preSum[i][j - c]) + // 减去上方和左方的前缀和
            preSum[i - c][j - c]; // 加上左上角重复减去的部分

        // 如果电量总和大于等于目标电量，统计
        if (square >= k) ans++;
      }
    }

    return ans; // 返回结果
  }
}

详细讲解：

1. 输入获取
Scanner sc = new Scanner(System.in); // 创建 Scanner 对象，用于读取输入
  • Scanner 类：
    • 用于从控制台读取输入。
    • nextInt() 方法用于读取整数。
int n = sc.nextInt(); // 地块行数
int m = sc.nextInt(); // 地块列数
int c = sc.nextInt(); // 正方形边长
int k = sc.nextInt(); // 目标电量
  • 读取第一行数据：
    • 解析并存储 n、m、c、k。
int[][] matrix = new int[n][m]; // 初始化地块矩阵

for (int i = 0; i < n; i++) {
  for (int j = 0; j < m; j++) {
    matrix[i][j] = sc.nextInt(); // 读取每个位置的电量
  }
}
  • 读取地块矩阵数据：
    • 使用双重循环读取 n * m 的地块矩阵。
2. 二维前缀和
int[][] preSum = new int[n + 1][m + 1]; // 初始化前缀和数组
  • 初始化前缀和数组：
    • preSum 是一个 (n+1) * (m+1) 的二维数组，初始值为 0。
    • 多一行一列是为了方便边界计算。
for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= m; j++) {
    preSum[i][j] =
        preSum[i - 1][j] + // 上方前缀和
        preSum[i][j - 1] - // 左方前缀和
        preSum[i - 1][j - 1] + // 左上角重复计算的部分
        matrix[i - 1][j - 1]; // 当前地块的电量
  }
}
  • 计算前缀和：
    • preSum[i][j] 表示从 (0,0) 到 (i,j) 的矩形区域内的电量总和。
    • 公式：
      preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + matrix[i-1][j-1]
3. 计算正方形区域电量
int ans = 0; // 统计满足条件的正方形区域数量

for (int i = c; i <= n; i++) {
  for (int j = c; j <= m; j++) {
    // 计算当前正方形区域内的电量总和
    int square =
        preSum[i][j] - // 右下角前缀和
        (preSum[i - c][j] + preSum[i][j - c]) + // 减去上方和左方的前缀和
        preSum[i - c][j - c]; // 加上左上角重复减去的部分

    // 如果电量总和大于等于目标电量，统计
    if (square >= k) ans++;
  }
}
  • 计算正方形区域电量：
    • 对于每个右下角 (i,j)，计算边长为 c 的正方形区域内的电量总和。
    • 公式：
      square = preSum[i][j] - preSum[i-c][j] - preSum[i][j-c] + preSum[i-c][j-c]
    • 如果 square >= k，则统计。

代码运行示例

示例 1：

输入：

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

执行过程：

  1. 解析输入：
    • n = 3, m = 3, c = 2, k = 5。
    • 地块矩阵：
      [ [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9] ]
  2. 计算前缀和：
    [ [0, 0, 0, 0],
  [0, 1, 3, 6],
  [0, 5, 12, 21],
  [0, 12, 27, 45] ]
  3. 遍历正方形区域：
    • (2,2)：12 - 1 - 3 + 0 = 8（满足条件）
    • (2,3)：21 - 3 - 6 + 1 = 13（满足条件）
    • (3,2)：27 - 5 - 12 + 1 = 11（满足条件）
    • (3,3)：45 - 12 - 21 + 5 = 17（满足条件）
  4. 输出结果：
    4
示例 2：

输入：

2 2 1 3
1 2
3 4

执行过程：

  1. 解析输入：
    • n = 2, m = 2, c = 1, k = 3。
    • 地块矩阵：
      [ [1, 2],
  [3, 4] ]
  2. 计算前缀和：
    [ [0, 0, 0],
  [0, 1, 3],
  [0, 4, 10] ]
  3. 遍历正方形区域：
    • (1,1)：1（不满足条件）
    • (1,2)：3（满足条件）
    • (2,1)：4（满足条件）
    • (2,2)：10 - 1 - 3 + 0 = 6（满足条件）
  4. 输出结果：
    3

总结

  1. 功能：

    • 统计满足条件的正方形区域数量。

  2. 优点：

    • 使用二维前缀和优化计算，时间复杂度为 O(n * m)。

  3. 适用场景：

    • 适用于需要快速计算矩形区域和的场景。

如果您有其他问题，欢迎随时提问！

四、Python算法源码

以下是 Python 代码的详细中文注释与讲解。此代码的功能是计算一个 n * m 的地块中，所有边长为 c 的正方形区域内的电量总和是否大于等于目标电量 k，并统计满足条件的正方形区域数量。

代码功能

  1. 输入格式：

    • 第一行输入四个整数：n（地块行数）、m（地块列数）、c（正方形边长）、k（目标电量）。
    • 接下来输入 n 行，每行 m 个整数，表示地块中每个位置的电量。

  2. 处理逻辑：

    • 使用二维前缀和（Prefix Sum）快速计算任意正方形区域内的电量总和。
    • 遍历所有可能的边长为 c 的正方形区域，统计满足电量总和大于等于 k 的区域数量。

代码：

# 输入获取
n, m, c, k = map(int, input().split())  # 读取第一行输入：n, m, c, k
matrix = [list(map(int, input().split())) for i in range(n)]  # 读取地块矩阵

# 算法入口
def getResult(n, m, c, k, matrix):
    """
    :param n: 调研区域的长，行数
    :param m: 调研区域的宽，列数
    :param c: 正方形电站的边长
    :param k: 正方形电站的最低发电量
    :param matrix: 调研区域每单位面积的发电量矩阵
    :return: 返回调研区域有几个符合要求正方形电站
    """
    # 初始化二维前缀和数组
    preSum = [[0 for j in range(m + 1)] for i in range(n + 1)]

    # 计算前缀和
    for i in range(1, n + 1):
        for j in range(1, m + 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(c, n + 1):
        for j in range(c, m + 1):
            # 计算当前正方形区域内的电量总和
            square = (
                preSum[i][j]  # 右下角前缀和
                - (preSum[i - c][j] + preSum[i][j - c])  # 减去上方和左方的前缀和
                + preSum[i - c][j - c]  # 加上左上角重复减去的部分
            )

            # 如果电量总和大于等于目标电量，统计
            if square >= k:
                ans += 1

    return ans  # 返回结果


# 算法调用
print(getResult(n, m, c, k, matrix))

详细讲解：

1. 输入获取
n, m, c, k = map(int, input().split())  # 读取第一行输入：n, m, c, k
matrix = [list(map(int, input().split())) for i in range(n)]  # 读取地块矩阵
  • input().split()：
    • 读取一行输入，并按空格分割成字符串列表。
  • map(int, ...)：
    • 将字符串列表转换为整数列表。
  • matrix：
    • 使用列表推导式读取 n 行输入，每行转换为一个整数列表。
2. 二维前缀和
preSum = [[0 for j in range(m + 1)] for i in range(n + 1)]  # 初始化前缀和数组
  • 初始化前缀和数组：
    • preSum 是一个 (n+1) * (m+1) 的二维数组，初始值为 0。
    • 多一行一列是为了方便边界计算。
for i in range(1, n + 1):
    for j in range(1, m + 1):
        preSum[i][j] = (
            preSum[i - 1][j]  # 上方前缀和
            + preSum[i][j - 1]  # 左方前缀和
            - preSum[i - 1][j - 1]  # 左上角重复计算的部分
            + matrix[i - 1][j - 1]  # 当前地块的电量
        )
  • 计算前缀和：
    • preSum[i][j] 表示从 (0,0) 到 (i,j) 的矩形区域内的电量总和。
    • 公式：
      preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + matrix[i-1][j-1]
3. 计算正方形区域电量
ans = 0  # 统计满足条件的正方形区域数量

for i in range(c, n + 1):
    for j in range(c, m + 1):
        # 计算当前正方形区域内的电量总和
        square = (
            preSum[i][j]  # 右下角前缀和
            - (preSum[i - c][j] + preSum[i][j - c])  # 减去上方和左方的前缀和
            + preSum[i - c][j - c]  # 加上左上角重复减去的部分
        )

        # 如果电量总和大于等于目标电量，统计
        if square >= k:
            ans += 1
  • 计算正方形区域电量：
    • 对于每个右下角 (i,j)，计算边长为 c 的正方形区域内的电量总和。
    • 公式：
      square = preSum[i][j] - preSum[i-c][j] - preSum[i][j-c] + preSum[i-c][j-c]
    • 如果 square >= k，则统计。

代码运行示例

示例 1：

输入：

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

执行过程：

  1. 解析输入：
    • n = 3, m = 3, c = 2, k = 5。
    • 地块矩阵：
      [ [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9] ]
  2. 计算前缀和：
    [ [0, 0, 0, 0],
  [0, 1, 3, 6],
  [0, 5, 12, 21],
  [0, 12, 27, 45] ]
  3. 遍历正方形区域：
    • (2,2)：12 - 1 - 3 + 0 = 8（满足条件）
    • (2,3)：21 - 3 - 6 + 1 = 13（满足条件）
    • (3,2)：27 - 5 - 12 + 1 = 11（满足条件）
    • (3,3)：45 - 12 - 21 + 5 = 17（满足条件）
  4. 输出结果：
    4
示例 2：

输入：

2 2 1 3
1 2
3 4

执行过程：

  1. 解析输入：
    • n = 2, m = 2, c = 1, k = 3。
    • 地块矩阵：
      [ [1, 2],
  [3, 4] ]
  2. 计算前缀和：
    [ [0, 0, 0],
  [0, 1, 3],
  [0, 4, 10] ]
  3. 遍历正方形区域：
    • (1,1)：1（不满足条件）
    • (1,2)：3（满足条件）
    • (2,1)：4（满足条件）
    • (2,2)：10 - 1 - 3 + 0 = 6（满足条件）
  4. 输出结果：
    3

总结

  1. 功能：

    • 统计满足条件的正方形区域数量。

  2. 优点：

    • 使用二维前缀和优化计算，时间复杂度为 O(n * m)。

  3. 适用场景：

    • 适用于需要快速计算矩形区域和的场景。

如果您有其他问题，欢迎随时提问！

五、C/C++算法源码：

以下是 C++ 和 C 语言 的版本，并附上详细的中文注释和讲解。

C++ 代码

代码：

#include <iostream>
#include <vector>
using namespace std;

/**
 * 计算满足条件的正方形区域数量
 * @param matrix n*m的地块
 * @param n 地块行数
 * @param m 地块列数
 * @param c 正方形的发电站边长为c
 * @param k 目标电量k
 * @return 可以建设几个发电站
 */
int getResult(vector<vector<int>>& matrix, int n, int m, int c, int k) {
    // 初始化二维前缀和数组
    vector<vector<int>> preSum(n + 1, vector<int>(m + 1, 0));

    // 计算前缀和
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; 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 = c; i <= n; i++) {
        for (int j = c; j <= m; j++) {
            // 计算当前正方形区域内的电量总和
            int square = preSum[i][j] - (preSum[i - c][j] + preSum[i][j - c]) + preSum[i - c][j - c];
            if (square >= k) ans++; // 如果电量总和大于等于目标电量，统计
        }
    }

    return ans; // 返回结果
}

int main() {
    int n, m, c, k;
    cin >> n >> m >> c >> k; // 读取输入

    vector<vector<int>> matrix(n, vector<int>(m)); // 初始化地块矩阵

    // 读取地块矩阵数据
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> matrix[i][j];
        }
    }

    // 调用算法函数并输出结果
    cout << getResult(matrix, n, m, c, k) << endl;

    return 0;
}

C++ 代码讲解：

  1. 输入获取：

    • 使用 cin 读取输入数据。
    • 使用 vector<vector<int>> 存储地块矩阵。

  2. 前缀和计算：

    • 初始化 preSum 为 (n+1) * (m+1) 的二维数组，初始值为 0。
    • 使用双重循环计算前缀和：
      preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i - 1][j - 1];

  3. 遍历正方形区域：

    • 使用双重循环遍历所有可能的正方形区域。
    • 计算当前正方形区域内的电量总和：
      int square = preSum[i][j] - (preSum[i - c][j] + preSum[i][j - c]) + preSum[i - c][j - c];
    • 如果电量总和大于等于 k，则统计。

  4. 输出结果：

    • 使用 cout 输出结果。

C 语言代码

代码：

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

/**
 * 计算满足条件的正方形区域数量
 * @param matrix n*m的地块
 * @param n 地块行数
 * @param m 地块列数
 * @param c 正方形的发电站边长为c
 * @param k 目标电量k
 * @return 可以建设几个发电站
 */
int getResult(int** matrix, int n, int m, int c, int k) {
    // 初始化二维前缀和数组
    int** preSum = (int**)malloc((n + 1) * sizeof(int*));
    for (int i = 0; i <= n; i++) {
        preSum[i] = (int*)malloc((m + 1) * sizeof(int));
        for (int j = 0; j <= m; j++) {
            preSum[i][j] = 0; // 初始化为 0
        }
    }

    // 计算前缀和
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; 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 = c; i <= n; i++) {
        for (int j = c; j <= m; j++) {
            // 计算当前正方形区域内的电量总和
            int square = preSum[i][j] - (preSum[i - c][j] + preSum[i][j - c]) + preSum[i - c][j - c];
            if (square >= k) ans++; // 如果电量总和大于等于目标电量，统计
        }
    }

    // 释放动态分配的内存
    for (int i = 0; i <= n; i++) {
        free(preSum[i]);
    }
    free(preSum);

    return ans; // 返回结果
}

int main() {
    int n, m, c, k;
    scanf("%d %d %d %d", &n, &m, &c, &k); // 读取输入

    // 动态分配地块矩阵内存
    int** matrix = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        matrix[i] = (int*)malloc(m * sizeof(int));
        for (int j = 0; j < m; j++) {
            scanf("%d", &matrix[i][j]); // 读取地块矩阵数据
        }
    }

    // 调用算法函数并输出结果
    printf("%d\n", getResult(matrix, n, m, c, k));

    // 释放动态分配的内存
    for (int i = 0; i < n; i++) {
        free(matrix[i]);
    }
    free(matrix);

    return 0;
}

C 语言代码讲解：

  1. 输入获取：

    • 使用 scanf 读取输入数据。
    • 使用动态分配的二维数组存储地块矩阵。

  2. 前缀和计算：

    • 使用 malloc 动态分配 preSum 数组。
    • 使用双重循环计算前缀和：
      preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i - 1][j - 1];

  3. 遍历正方形区域：

    • 使用双重循环遍历所有可能的正方形区域。
    • 计算当前正方形区域内的电量总和：
      int square = preSum[i][j] - (preSum[i - c][j] + preSum[i][j - c]) + preSum[i - c][j - c];
    • 如果电量总和大于等于 k，则统计。

  4. 内存管理：

    • 使用 malloc 动态分配内存。
    • 使用 free 释放动态分配的内存，避免内存泄漏。

  5. 输出结果：

    • 使用 printf 输出结果。

总结

  1. 功能：

    • 统计满足条件的正方形区域数量。

  2. 优点：

    • 使用二维前缀和优化计算，时间复杂度为 O(n * m)。

  3. 适用场景：

    • 适用于需要快速计算矩形区域和的场景。

如果您有其他问题，欢迎随时提问！

六、尾言

什么是华为OD？

华为OD（Outsourcing Developer，外包开发工程师）是华为针对软件开发工程师岗位的一种招聘形式，主要包括笔试、技术面试以及综合面试等环节。尤其在笔试部分，算法题的机试至关重要。

为什么刷题很重要？

  1. 机试是进入技术面的第一关：
    华为OD机试（常被称为机考）主要考察算法和编程能力。只有通过机试，才能进入后续的技术面试环节。

  2. 技术面试需要手撕代码：
    技术一面和二面通常会涉及现场编写代码或算法题。面试官会注重考察候选人的思路清晰度、代码规范性以及解决问题的能力。因此提前刷题、多练习是通过面试的重要保障。

  3. 入职后的可信考试：
    入职华为后，还需要通过“可信考试”。可信考试分为三个等级：

    • 入门级：主要考察基础算法与编程能力。
    • 工作级：更贴近实际业务需求，可能涉及复杂的算法或与工作内容相关的场景题目。
    • 专业级：最高等级，考察深层次的算法以及优化能力，与薪资直接挂钩。

刷题策略与说明：

2024年8月14日之后，华为OD机试的题库转为 E卷，由往年题库（D卷、A卷、B卷、C卷）和全新题目组成。刷题时可以参考以下策略：

  1. 关注历年真题：

    • 题库中的旧题占比较大，建议优先刷历年的A卷、B卷、C卷、D卷题目。
    • 对于每道题目，建议深度理解其解题思路、代码实现，以及相关算法的适用场景。

  2. 适应新题目：

    • E卷中包含全新题目，需要掌握全面的算法知识和一定的灵活应对能力。
    • 建议关注新的刷题平台或交流群，获取最新题目的解析和动态。

  3. 掌握常见算法：
    华为OD考试通常涉及以下算法和数据结构：

    • 排序算法（快速排序、归并排序等）
    • 动态规划（背包问题、最长公共子序列等）
    • 贪心算法
    • 栈、队列、链表的操作
    • 图论（最短路径、最小生成树等）
    • 滑动窗口、双指针算法

  4. 保持编程规范：

    • 注重代码的可读性和注释的清晰度。
    • 熟练使用常见编程语言，如C++、Java、Python等。

如何获取资源？

  1. 官方参考：

    • 华为招聘官网或相关的招聘平台会有一些参考信息。
    • 华为OD的相关公众号可能也会发布相关的刷题资料或学习资源。

  2. 加入刷题社区：

    • 找到可信的刷题交流群，与其他备考的小伙伴交流经验。
    • 关注知名的刷题网站，如LeetCode、牛客网等，这些平台上有许多华为OD的历年真题和解析。

  3. 寻找系统性的教程：

    • 学习一本经典的算法书籍，例如《算法导论》《剑指Offer》《编程之美》等。
    • 完成系统的学习课程，例如数据结构与算法的在线课程。

积极心态与持续努力：

刷题的过程可能会比较枯燥，但它能够显著提升编程能力和算法思维。无论是为了通过华为OD的招聘考试，还是为了未来的职业发展，这些积累都会成为重要的财富。

考试注意细节

  1. 本地编写代码

    • 在本地 IDE（如 VS Code、PyCharm 等）上编写、保存和调试代码，确保逻辑正确后再复制粘贴到考试页面。这样可以减少语法错误，提高代码准确性。

  2. 调整心态，保持冷静

    • 遇到提示不足或实现不确定的问题时，不必慌张，可以采用更简单或更有把握的方法替代，确保思路清晰。

  3. 输入输出完整性

    • 注意训练和考试时都需要编写完整的输入输出代码，尤其是和题目示例保持一致。完成代码后务必及时调试，确保功能符合要求。

  4. 快捷键使用

    • 删除行可用 Ctrl+D，复制、粘贴和撤销分别为 Ctrl+C，Ctrl+V，Ctrl+Z，这些可以正常使用。
    • 避免使用 Ctrl+S，以免触发浏览器的保存功能。

  5. 浏览器要求

    • 使用最新版的 Google Chrome 浏览器完成考试，确保摄像头开启并正常工作。考试期间不要切换到其他网站，以免影响考试成绩。

  6. 交卷相关

    • 答题前，务必仔细查看题目示例，避免遗漏要求。
    • 每完成一道题后，点击【保存并调试】按钮，多次保存和调试是允许的，系统会记录得分最高的一次结果。完成所有题目后，点击【提交本题型】按钮。
    • 确保在考试结束前提交试卷，避免因未保存或调试失误而丢分。

  7. 时间和分数安排

    • 总时间：150 分钟；总分：400 分。
    • 试卷结构：2 道一星难度题（每题 100 分），1 道二星难度题（200 分）。及格分为 150 分。合理分配时间，优先完成自己擅长的题目。

  8. 考试环境准备

    • 考试前请备好草稿纸和笔。考试中尽量避免离开座位，确保监控画面正常。
    • 如需上厕所，请提前规划好时间以减少中途离开监控的可能性。

  9. 技术问题处理

    • 如果考试中遇到断电、断网、死机等技术问题，可以关闭浏览器并重新打开试卷链接继续作答。
    • 出现其他问题，请第一时间联系 HR 或监考人员进行反馈。

祝你考试顺利，取得理想成绩！


原文地址：https://blog.csdn.net/m0_63168877/article/details/145141443

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2025