[AcWing 796] 子矩阵的和
2024-09-07 18:11:30
点击查看代码
#include<iostream>
using namespace std;
const int N = 1e3 + 10;
int a[N][N], s[N][N];
int main()
{
int n, m, q;
scanf("%d %d %d", &n, &m, &q);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
scanf("%d", &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;
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
}
return 0;
}
- 前缀和 s[ i ][ j ] 的计算公式,s[ i ][ j ] = s[ i - 1][ j ] + s[ i ][ j - 1 ] -s[ i - 1 ][ j - 1 ] + a[ i ][ j ];
- ( x2, y2 ) 和 ( x1, y1 ) 之间的矩阵和等于 s[ x2 ][ y2 ] - s[ x1 - 1 ][ y2 ] - s[ x2 ][ y1 - 1 ] + s[ x1 - 1 ][ y1 - 1 ];
- 可以画图,用表格表示,便于理解;
最新文章
- Android事件总线
- 《javascript权威指南》读书笔记——第二篇
- 操作JNI函数以及复杂对象传递
- SQL Server 2012清除连接过的服务器名称历史
- trunc函数
- javascript深度克隆与javascript的继承实现
- test_markdown
- ip地址0.0.0.0与127.0.0.1的区别(转载)
- Cup
- SpringBoot 2.0 mybatis mapper通用类
- 安装完MySQL数据库设置密码
- PCA降维实验代码
- 通过使用浏览器对象模型,输出当前浏览器窗口中打开的文档的URL信息,并将显示在窗口中。
- php官网下载的chm手册,源码字号太小的问题解决
- ROC曲线和PR曲线绘制【转】
- RSS Feeds with Spring Boot
- webstorm 上传代码到gitlab
- MySql存储引擎MyISAM和InnoDB的区别
- Windows Server 2012 R2
- Matlab中size、numel、length、fix函数的使用