首页 > 编程语言 >算法基础:子矩阵的和

算法基础:子矩阵的和

时间:2022-11-25 11:22:22浏览次数:43  
标签:x1 int 矩阵 基础 x2 算法 y1 y2

算法:子矩阵的和

以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和为:
s[x2, y2] - s[x1 - 1, y2] - s[x2, y1 - 1] + s[x1 - 1, y1 - 1]

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;
int a[N][N], s[N][N];  //s[n][n]二维矩阵前缀和

int main(){
	int n, m, q;
	cin >> n >> m >> q;
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
		}
	}
	
	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] + a[i][j]; //二维矩阵前缀和的预处理公式
		}
	}
	
	while(q--){
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		
		cout << s[x2][y2] - s[x2][y1 - 1] - s[x1 -1][y2] + s[x1 -1][y1-1] << endl; 
	}
	
	
	return 0;
}

标签:x1,int,矩阵,基础,x2,算法,y1,y2
From: https://www.cnblogs.com/csai-H/p/16924559.html

相关文章

  • 软件技术基础(3)-电梯演讲
    软件技术基础软件技术基础第三次作业作业目标完成一个电梯演讲姓名-学号严隽铭-20193303010321.小组成员严隽铭-2019330301032陈奕涛-2019330301007......
  • 算法基础
    算法:前缀和#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;inta[N],s[N];//s[N]前缀和数组s[i]=a[1]+a[2]+a[3]+...+a[i]int......
  • Python 基础(一):入门必备知识
    教程源码下载sv20.com目录1标识符2关键字3引号4编码5输入输出6缩进7多行8注释9数据类型10运算符10.1常用运算符10.2运算符优先级基础进阶爬虫自动化数据分析......
  • BSN-DDC基础网络DDC SDK详细设计(六):交易查询、区块查询、签名事件
    2022年1月25日,区块链服务网络发展联盟(简称“BSN联盟”)推出了“BSN-DDC基础网络”(简称DDC网络)。DDC网络的推出,为NFT技术在我国的落地提供基础设施能力支撑,并为其合规发展保驾......
  • 一文熟悉 Go 的基础语法和基本数据类型
    耐心和持久胜过激烈和狂热。前言快速上手一门新的语言,首先要做的就是熟悉新语言的基本语法和基本数据类型,本文将对Go语言的基础语法和基本数据类型进行介绍。Hello,World!记......
  • 每日算法之二维数组中的查找
    JZ4二维数组中的查找描述在一个二维数组array中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这......
  • day20 --> (JQuery基础)
     JQuery基础:1.概念:一个JavaScript框架。简化JS开发JavaScript框架【简单理解】:本质上就是一些js文件,封装了js的原生代码而已2.快速入门:1、下载JQuery文件jQuery-......
  • 算法5: LeetCode_单链表_两数相加
    题目:*给你两个非空的链表,表示两个非负的整数。它们每位数字都是按照逆序的方式存储的,并且每个节点只能存储一位数字。*请你将两个数相加,并以相同形式返回一个......
  • 第10节-MySQL数据库的编程基础
     10.1、变量、运算符介绍用户变量:使用@开头。【set定义,会话有效】系统变量:使用@@开头。【declare定义,begin..end有效】局部变量:在存储过程中有效。--1、用户变......
  • 算法基础
    算法——差分https://www.acwing.com/problem/content/description/799/#include<bits/stdc++.h>usingnamespacestd;constintN=100010;inta[N],b[N];intm......