【CSP】CSP-XL 2025辽宁复赛真题-第二题, 积分（points）

CSP-XL 2025辽宁复赛真题-第二题，二维数组前缀和考点，个人认为约相当于GESP四级+，五级-，难度⭐⭐★☆☆。

CSP-XL 2025辽宁复赛真题-第二题, 积分（points）

题目要求

---

题目分析

解题思路

1. 题意梳理
   给定一个 $n \times m$ 的整数矩阵，每个格子有一个积分值。
   再给出两个边长 $x$ 和 $y$，要求分别找出所有边长为 $x$ 的正方形区域与边长为 $y$ 的正方形区域，计算它们内部积分之和，最终输出这两个“最大子正方形和”中的较大者。
   若 $x$ 或 $y$ 大于矩阵行列尺寸，则对应尺寸无法形成合法正方形，跳过。

2. 核心思路——二维前缀和
   • 预处理：
     构造二维前缀和数组 pre_sum[i][j]，表示从左上角 $(1,1)$ 到 $(i,j)$ 子矩阵的积分和。
     递推式：
     pre_sum[i][j] = pre_sum[i-1][j] + pre_sum[i][j-1] - pre_sum[i-1][j-1] + a_array[i][j]
     这样可在 $O(1)$ 时间内算出任意子正方形和。
   • 枚举：
     分别用两重循环枚举所有可能的左上角 $(i,j)$，若 i+k-1≤n 且 j+k-1≤m（$k$ 取 $x$ 或 $y$），则用前缀和公式
     sum = pre_sum[i+k-1][j+k-1] - pre_sum[i-1][j+k-1] - pre_sum[i+k-1][j-1] + pre_sum[i-1][j-1]
     得到当前正方形积分，更新对应尺寸的最大值。
   • 结果：
     最终取 max(max_x, max_y) 输出即可。
3. 复杂度分析
   • 时间：
     预处理前缀和 $O(n \cdot m)$；
     枚举所有 $x \times x$ 正方形最多 $(n-x+1)(m-x+1)$ 个，$y \times y$ 同理，总体仍为 $O(n \cdot m)$。
   • 空间：
     两个 $n \times m$ 的 long long 数组，约 $O(n \cdot m)$。
4. 边界与细节
   • 当 $x$ 或 $y$ 大于 $n$ 或 $m$ 时，对应尺寸无法形成合法正方形，循环内提前 break 减少无效枚举。
   • 初始化最大值用 LLONG_MIN 防止全负矩阵出错。
   • 使用 freopen 按复赛要求读写文件，行列下标统一从 1 开始，避免越界。

---

示例代码

#include <algorithm>
#include <climits>
#include <iostream>

long long a_array[1005][1005];     // 存放原始二维数组，行列下标从1开始
long long pre_sum[1005][1005];    // 二维前缀和数组，pre_sum[i][j]表示(1,1)到(i,j)子矩阵的和
int main() {
    freopen("points.in", "r", stdin);   // 复赛标准输入文件
    freopen("points.out", "w", stdout); // 复赛标准输出文件
    int n, m, x, y;                     // n行m列，x×x与y×y两种尺寸的正方形区域
    std::cin >> n >> m >> x >> y;
    // 读入原始矩阵
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            std::cin >> a_array[i][j];
        }
    }

    // 计算二维前缀和
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            pre_sum[i][j] = pre_sum[i - 1][j] + pre_sum[i][j - 1] -
                            pre_sum[i - 1][j - 1] + a_array[i][j];
        }
    }

    // 枚举所有x×x正方形区域，求最大积分
    long long max_x_points = LLONG_MIN; // 初始化为最小值
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i + x - 1 <= n && j + x - 1 <= m) {
                long long cur_points =
                    pre_sum[i + x - 1][j + x - 1] - pre_sum[i - 1][j + x - 1] -
                    pre_sum[i + x - 1][j - 1] + pre_sum[i - 1][j - 1];
                max_x_points = std::max(max_x_points, cur_points);
            } else {
                break; // 当前行剩余位置无法满足x×x区域，直接跳出内层循环
            }
        }
    }

    // 枚举所有y×y正方形区域，求最大积分
    long long max_y_points = LLONG_MIN;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i + y - 1 <= n && j + y - 1 <= m) {
                long long cur_points =
                    pre_sum[i + y - 1][j + y - 1] - pre_sum[i - 1][j + y - 1] -
                    pre_sum[i + y - 1][j - 1] + pre_sum[i - 1][j - 1];
                max_y_points = std::max(max_y_points, cur_points);
            } else {
                break; // 同理，提前结束本行后续枚举
            }
        }
    }

    // 输出两种尺寸中的最大积分
    long long max_points = std::max(max_x_points, max_y_points);
    std::cout << max_points << std::endl;
    return 0;
}

---

附：样例和测试数据下载地址：

链接：https://pan.quark.cn/s/79e0531a87ed?pwd=1bK8 提取码：1bK8

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号