AcWing 796.子矩阵的和
2022/1/30 23:11:15
本文主要是介绍AcWing 796.子矩阵的和,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
输入一个 nn 行 mm 列的整数矩阵,再输入 qq 个询问,每个询问包含四个整数 x1,y1,x2,y2x1,y1,x2,y2,表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数 n,m,qn,m,q。
接下来 nn 行,每行包含 mm 个整数,表示整数矩阵。
接下来 qq 行,每行包含四个整数 x1,y1,x2,y2x1,y1,x2,y2,表示一组询问。
输出格式
共 qq 行,每行输出一个询问的结果。
数据范围
1≤n,m≤10001≤n,m≤1000,
1≤q≤2000001≤q≤200000,
1≤x1≤x2≤n1≤x1≤x2≤n,
1≤y1≤y2≤m1≤y1≤y2≤m,
−1000≤矩阵内元素的值≤1000−1000≤矩阵内元素的值≤1000
输入样例:
3 4 3 1 7 2 4 3 6 2 8 2 1 2 3 1 1 2 2 2 1 3 4 1 3 3 4
输出样例:
17 27 21
S[i,j]即为图1红框中所有数的的和为:
S[i,j]=S[i,j−1]+S[i−1,j]−S[i−1,j−1]+a[i,j]
(x1,y1),(x2,y2)(x1,y1),(x2,y2)这一子矩阵中的所有数之和为:S[x2,y2]−S[x1−1,y2]−S[x2,y1−1]+S[x1−1,y1−1]
import java.util.*; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner reader =new Scanner(System.in); int n = reader.nextInt(); int m = reader.nextInt(); int q=reader.nextInt(); int arr [] [] =new int [n+1][m+1]; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { //预处理输入的矩阵 arr[i][j]=reader.nextInt(); } } int s [] [] =new int [n+1][m+1]; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { //用公式对二维数组进行前缀和求值 //求该点的前缀和s[i][j] 需要加上上一行该点的前缀和 s[i-1][j] 以及 //上一列该点的前缀和 s[i][j-1] //再减去公共部分 s[i-1][j-1] //最后加上自己本身点的值 arr[i][j] //最后的结果就是该点的前缀和 s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+arr[i][j]; } } while(q-->0) { int x1=reader.nextInt(); int y1=reader.nextInt(); int x2=reader.nextInt(); int y2=reader.nextInt(); //在这里和上面求前缀和相似 只是点不同 System.out.println(s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]); } } }
这篇关于AcWing 796.子矩阵的和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升