2025年12月GESP(C++四级): 建造-编程阁

2025年12月GESP(C++四级): 建造

题目描述

小 A 有一张M MM行N NN列的地形图，其中第i ii行第j jj列的数字a i j a_{ij}aij代表坐标( i , j ) (i, j)(i,j)的海拔高度。

停机坪为一个3 × 3 3 \times 33×3的区域，且内部所有9 99个点的最大高度和最小高度之差不超过H HH。

小 A 想请你计算出，在所有适合建造停机坪的区域中，区域内部9 99个点海拔之和最大是多少。

输入格式

第一行三个正整数M , N , H M, N, HM,N,H，含义如题面所示。

之后M MM行，第i ii行包含N NN个整数a i 1 , a i 2 , … , a i N a_{i1}, a_{i2}, \dots, a_{iN}ai1,ai2,…,aiN，代表坐标( i , j ) (i, j)(i,j)的高度。

数据保证总存在一个适合建造停机坪的区域。

输出格式

输出一行，代表最大的海拔之和。

输入输出样例 1

输入 1

5 5 3 5 5 5 5 5 5 1 5 1 5 5 5 5 5 5 5 2 5 2 5 3 5 5 5 2

输出 1

数据范围

对于所有测试点，保证1 ≤ M , N ≤ 10 3 1 \leq M, N \leq 10^31≤M,N≤103，1 ≤ H , a i j ≤ 10 5 1 \leq H, a_{ij} \leq 10^51≤H,aij≤105。

思路分析

这个问题要求在 M×N 的地形图中，找到一个 3×3 的区域，满足区域内9个点中最大高度和最小高度之差不超过 H，并且在所有满足条件的区域中找到海拔之和最大的区域。

核心思想

暴力枚举法：遍历所有可能的 3×3 区域的左上角坐标
边界条件：由于是 3×3 区域，左上角坐标范围为(1 ≤ i ≤ m-2, 1 ≤ j ≤ n-2)
条件检查：对每个区域，计算最大值和最小值，检查差值是否 ≤ H
求和计算：对符合条件的区域计算9个点的和，并更新最大值

时间复杂度

外层循环：O((M-2)×(N-2)) ≈ O(M×N)
内层循环：固定 9 次操作（3×3 区域）
总复杂度：O(M×N)，在 M,N ≤ 1000 时是可行的

代码实现

#include<bits/stdc++.h>usingnamespacestd;intm,n,h,ans=0,a[1010][1010];// 检查以(x,y)为左上角的3×3区域是否满足高度差条件boolcheck(intx,inty){intmaxh=a[x][y];// 最大值初始化为第一个元素intminh=a[x][y];// 最小值初始化为第一个元素// 遍历3×3区域的所有9个点for(inti=x;i<=x+2;i++){for(intj=y;j<=y+2;j++){maxh=max(maxh,a[i][j]);// 更新最大值minh=min(minh,a[i][j]);// 更新最小值}}// 判断最大高度差是否不超过Hreturnmaxh-minh<=h;}// 计算以(x,y)为左上角的3×3区域的海拔之和intsum(intx,inty){intres=0;// 遍历3×3区域的所有9个点并累加for(inti=x;i<=x+2;i++){for(intj=y;j<=y+2;j++){res+=a[i][j];}}returnres;}intmain(){// 输入数据规模cin>>m>>n>>h;// 输入地形图数据for(inti=1;i<=m;i++){for(intj=1;j<=n;j++){cin>>a[i][j];}}// 枚举所有可能的3×3区域的左上角// i的范围：1 到 m-2（保证向下有3行）// j的范围：1 到 n-2（保证向右有3列）for(inti=1;i<=m-2;i++){for(intj=1;j<=n-2;j++){// 如果当前区域满足高度差条件if(check(i,j)){// 计算区域和并更新最大值ans=max(ans,sum(i,j));}}}// 输出最大海拔和cout<<ans;return0;}

功能分析

1.数据结构

使用二维数组a[1010][1010]存储地形图
数组大小定义为 1010×1010，满足 M,N ≤ 1000 的要求

2.核心函数

check(x, y)：检查指定区域是否满足建造条件
- 时间复杂度：O(9) = O(1)
- 空间复杂度：O(1)
sum(x, y)：计算指定区域的海拔总和
- 时间复杂度：O(9) = O(1)
- 空间复杂度：O(1)

3.算法流程

1. 读取输入：M, N, H 和地形图数据 2. 遍历所有可能的3×3区域左上角坐标 - 对每个区域调用check()检查是否满足条件 - 如果满足，调用sum()计算海拔和并更新最大值 3. 输出找到的最大海拔和

4.边界处理

循环条件i <= m-2和j <= n-2确保3×3区域不越界
题目保证至少存在一个满足条件的区域，所以ans一定有值

5.复杂度分析

时间复杂度：O(M×N × 9) ≈ O(9MN) = O(MN)
空间复杂度：O(MN) 用于存储地形图

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

一、CSP信奥赛C++通关学习视频课：
- C++语法基础
- C++语法进阶
- C++算法
- C++数据结构
- CSP信奥赛数学
- CSP信奥赛STL
二、CSP信奥赛C++竞赛拿奖视频课：
- 信奥赛csp-j初赛高频考点解析
- CSP信奥赛C++复赛集训课（12大高频考点专题集训）
三、考级、竞赛刷题题单及题解：
- GESP C++考级真题题解
- CSP信奥赛C++初赛及复赛高频考点真题解析
- CSP信奥赛C++一等奖通关刷题题单及题解

详细内容：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

3、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

2025 csp-j 复赛真题及答案解析（最新更新）
2025 csp-x(山东) 复赛真题及答案解析（最新更新）
2025 csp-x(河南) 复赛真题及答案解析（最新更新）
2025 csp-x(辽宁) 复赛真题及答案解析（最新更新）
2025 csp-x(江西) 复赛真题及答案解析（最新更新）
2025 csp-x(广西) 复赛真题及答案解析（最新更新）
2020 ~ 2024 csp 复赛真题题单及题解
2019 ~ 2022 csp-j 初赛高频考点真题分类解析
2021 ~ 2024 csp-s 初赛高频考点解析
2023 ~ 2024 csp-x (山东)初赛真题及答案解析
2024 csp-j 初赛真题及答案解析
2025 csp-j 初赛真题及答案解析（最新更新）
2025 csp-s 初赛真题及答案解析（最新更新）
2025 csp-x (山东)初赛真题及答案解析(最新更新)
2025 csp-x (江西)初赛真题及答案解析(最新更新)
2025 csp-x (辽宁)初赛真题及答案解析(最新更新)

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

129 道刷题练习和详细题解，涉及：模拟算法、数学思维、二分算法、前缀和、差分、深搜、广搜、DP专题、树和图

4、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}

2025年12月GESP(C++四级): 建造