制作手机网站用什么软件,wordpress移动底部菜单,化妆品可做的团购网站有哪些,免费注册com的网站前缀和 题目题目链接题解方法一方法二 题目
描述 给你一个 n 行 m 列的矩阵 A #xff0c;下标从1开始。
接下来有 q 次查询#xff0c;每次查询输入 4 个参数 x1 , y1 , x2 , y2
请输出以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和#xff0c; 输入描述#x… 前缀和 题目题目链接题解方法一方法二 题目
描述 给你一个 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行每行表示查询结果。 题目链接
二维前缀和题目链接
题解
方法一
显而易见最容易想到的方法就是先录入数据然后一行一行的求和。但是这种方法会超时。其时间复杂度为Om * n * q。
#include iostream
#include vectorusing namespace std;int main() {int n, m, q;cin n m q;vectorvectorint matrix(n, vectorint(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;
}不多赘述下面看最优解。
方法二
一遍遍求显然复杂度太高那么能不能先求取11到xy的和在找规律求取题目要求的和呢答案是可以的。
先求前缀和数组显然我们不能每次都遍历一次求和复杂度太高那么就可以利用前面已经求出的值求出当前的和。
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;vectorvectorint arr(n1,vectorint(m1));vectorvectorlong long dp(n1,vectorlong long(m1));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;
}
