夜雨聆风学习资料网

ARTICLE · 1135731

2026信息机器人素养活动真题:矩阵区域和解析

发布时间：2026-10-07 20:41:47 最近访问：2026-10-07 20:41:48
2026信息机器人素养活动真题:矩阵区域和解析

2026信息机器人素养活动真题：矩阵区域和解析

科技节展区被排布成一片 m×n 的「热度矩阵」，每一项代表一个展位的受欢迎程度。评委想快速知道：任意一块矩形区域（比如从第 r1 行 c1 列到第 r2 行 c2 列）的总热度是多少？ 查询次数极多，如何做到每次 O(1) 回答？这就是二维前缀和要解决的问题。

一、真题引入（AIOJ 算法挑战项原创题）

在「全国青少年信息机器人科技素养实践活动（贵州省选拔活动）」的 AIOJ 算法挑战项 / 人工智能计算思维 中，区域聚合查询是高频考点。原创题如下：

【科技节展区热度矩阵】给定 m 行 n 列的整数矩阵 a，以及 q 次查询，每次给出矩形左上角 (r1,c1) 与右下角 (r2,c2)，求该矩形内所有元素之和。数据范围：m,n ≤ 500，q ≤ 10⁵。

二、暴力做法与瓶颈

最直观的做法：每次查询都把矩形里的元素逐个相加。单次查询时间复杂度 O(矩形面积)，最坏 O(m·n)。当 q 很大时整体退化到 O(q·m·n)，在 10⁵ 次查询下必然超时。我们需要把「重复计算」去掉——这正是前缀和的套路。

  

三、核心思路：二维前缀和

类比一维前缀和 s[i]=s[i-1]+a[i]，二维前缀和用 容斥原理 把「左上角到 (i,j) 的矩形和」预处理出来：

建表（O(m·n)）： s[i][j] = s[i-1][j] + s[i][j-1] − s[i-1][j-1] + a[i][j]查询（O(1)）： ans = s[r2][c2] − s[r1-1][c2] − s[r2][c1-1] + s[r1-1][c1-1] 

画图理解：大矩形减去上面多算的、左边多算的，再加回左上角被减了两次的小块。一次建表后，任意矩形查询都是四个数的加减，与矩阵大小无关。

四、C++ 参考代码

 #include <bits/stdc++.h> using namespace std; int main() {   int m, n; cin >> m >> n;   vector<vector<int>> a(m+1, vector<int>(n+1, 0));   for (int i=1;i<=m;++i) for (int j=1;j<=n;++j) cin >> a[i][j];   vector<vector<long long>> s(m+1, vector<long long>(n+1, 0));   for (int i=1;i<=m;++i)     for (int j=1;j<=n;++j)       s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];   int q; cin >> q;   while (q--) {     int r1,c1,r2,c2; cin >> r1 >> c1 >> r2 >> c2;     long long ans = s[r2][c2] - s[r1-1][c2] - s[r2][c1-1] + s[r1-1][c1-1];     cout << ans << "\n";   }   return 0; } 

五、Python 参考代码

 def build_prefix(a, m, n):     s = [[0]*(n+1) for _ in range(m+1)]     for i in range(1, m+1):         row = 0         for j in range(1, n+1):             row += a[i-1][j-1]             s[i][j] = s[i-1][j] + row     return s def query(s, r1, c1, r2, c2):     return s[r2][c2] - s[r1-1][c2] - s[r2][c1-1] + s[r1-1][c1-1] m, n = map(int, input().split()) a = [list(map(int, input().split())) for _ in range(m)] s = build_prefix(a, m, n) q = int(input()) for _ in range(q):     r1,c1,r2,c2 = map(int, input().split())     print(query(s, r1, c1, r2, c2)) 
  

六、考点拆解与易错点

  1. 下标从 1 开始
    ：前缀和数组 s 故意开成 (m+1)×(n+1) 并让 0 行 0 列为 0，查询公式里的 r1-1、c1-1 才不会出现负下标。
  2. 容斥加减顺序
    ：s[r2][c2] 先减上、再减左、最后加回左上角被多减一次的部分，四块严丝合缝。
  3. 用 long long / 大整数
    ：矩阵元素累加极易溢出 int，C++ 务必用 long long，Python 无此忧。
  4. 建表 O(m·n) 只做一次
    ，多次查询均摊 O(1)，这是它碾压暴力的关键。

七、对拍验证（已实跑）

我们把「暴力逐格求和」作为标准答案，对二维前缀和做随机对拍：C++ 版 2000 组、Python 版 5000 组，矩阵规模 1~8、元素 −20~20、矩形随机，结果 mismatch=0，全部一致。比赛前养成「写标准暴力对拍」的习惯，能挡掉九成边界错误。

八、举一反三 & 互动

二维前缀和可扩展到：子矩阵最大值/最小值（需单调队列）、改点求区域和（二维树状数组）、周长/面积并（扫描线）。你还能想到哪些「区域聚合」场景？

💬 互动：如果题目改成「每次修改一个格子的值，再查询区域和」，二维前缀和还够用吗？评论区聊聊你的思路，下期我们讲二维树状数组！

📚 免费少儿编程资料（夸克网盘领取）

以下资料来自夸克网盘分享。个人号链接暂不支持直接点击，请长按或复制下方链接，打开夸克网盘 App / 网页粘贴即可保存：

  1. 1. 全国青少年信息素养大赛复赛集训题目Python&C++.docx
    https://pan.quark.cn/s/93995d3cb150
  2. 2. 2024信息素养-智能算法应用挑战赛-复赛初中组题目7月7日.pdf
    https://pan.quark.cn/s/da97b5dbf75d
  3. 3. Python背记手册.pdf
    https://pan.quark.cn/s/7568ae9ca92b
  4. 4. Python课程
    https://pan.quark.cn/s/a94bf02d00c6
  5. 5. 2024信息素养大赛图形化复赛集训题答案3-9
    https://pan.quark.cn/s/6ccab7ec3cbc
  6. 6. 2025年03月份电子学会考级真题
    https://pan.quark.cn/s/4403c4228912
  7. 7. 2025全国青少年信息素养大赛赛项说明
    https://pan.quark.cn/s/d9d0df4a9f29
  8. 8. 青少儿信息素养大赛编程资料
    https://pan.quark.cn/s/4ab6bd83be8a

资料持续更新，关注本号第一时间获取新分享。

相关学习资料