当前位置: 首页> 科技> 能源 > 企业策划书模板_济南网站优化网站_苏州市网站_南宁百度seo排名优化软件

企业策划书模板_济南网站优化网站_苏州市网站_南宁百度seo排名优化软件

时间:2025/7/11 15:04:42来源:https://blog.csdn.net/qq_34434522/article/details/143999622 浏览次数:0次
企业策划书模板_济南网站优化网站_苏州市网站_南宁百度seo排名优化软件

前缀和

  • 题目
    • 题目链接
    • 题解
      • 方法一
      • 方法二

题目

描述
给你一个 n 行 m 列的矩阵 A ,下标从1开始。

接下来有 q 次查询,每次查询输入 4 个参数 x1 , y1 , x2 , y2

请输出以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和,
输入描述:
第一行包含三个整数n,m,q.

接下来n行,每行m个整数,代表矩阵的元素

接下来q行,每行4个整数x1, y1, x2, y2,分别代表这次查询的参数
在这里插入图片描述

输出描述:
输出q行,每行表示查询结果。

在这里插入图片描述

题目链接

二维前缀和题目链接

题解

方法一

显而易见,最容易想到的方法就是先录入数据,然后一行一行的求和。但是这种方法会超时。其时间复杂度为O(m * n * q)。

#include <iostream>
#include <vector>using namespace std;int main() {int n, m, q;cin >> n >> m >> q;vector<vector<int>> matrix(n, vector<int>(m));for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {cin >> matrix[i][j];}}for (int i = 0; i < q; ++i) {int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;int sum = 0;for (int row = x1 - 1; row <= x2 - 1; ++row) { // 数组是从0开始的,所以要减1for (int col = y1 - 1; col <= y2 - 1; ++col) {sum += matrix[row][col];}}cout << sum << endl;}return 0;
}

不多赘述,下面看最优解。

方法二

一遍遍求显然复杂度太高,那么能不能先求取(1,1)到(x,y)的和在找规律求取题目要求的和呢?答案是可以的。

先求前缀和数组,显然我们不能每次都遍历一次求和,复杂度太高,那么就可以利用前面已经求出的值求出当前的和。

ps:因为下标从1开始,所以不用考虑越界。
在这里插入图片描述

由此可以得出D区域的求和公式为dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j];

再求某一个小区域的和,与此类似,画图总结公式,利用已知和求取。

在这里插入图片描述
由此可以得出D区域的求和公式为dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];

最终代码

#include <iostream>
#include <vector>
using namespace std;int main() 
{int n, m, q;cin >> n >> m >> q;vector<vector<int>> arr(n+1,vector<int>(m+1));vector<vector<long long>> dp(n+1,vector<long long>(m+1));for (int i = 1; i <= n; i++) for(int j = 1; j <= m; j++)cin >> arr[i][j];for (int i = 1; i <= n; i++) for(int j = 1; j <= m; j++)dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j];int x1,y1, x2, y2;long long sum = 0;for (int i = 1; i <= q; i++) {cin >> x1 >> y1 >> x2 >> y2;sum = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];cout << sum << endl;}return 0;
}
关键字:企业策划书模板_济南网站优化网站_苏州市网站_南宁百度seo排名优化软件

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: