1505 子矩陣求和
2.0 秒 131,072.0 KB 10 分 初學者2級題
給出一個m * n的矩陣a，矩陣元素a[i,j]小于1000，進行q次查詢，每次查詢給出子矩陣的4個邊界（上下左右），求該子矩陣所有元素之和。

樣例中第一個查詢：1 3 1 2 表示從第1行到第3行，從第1列到第2列，對應的子矩陣是：

1 2
5 6
9 10

求和等于33

輸入
第一行2個整數n, m，中間用空格分割，分別對應數組的行數n、列數m(1 <= m,n <= 100)
接下來n行，每行m個整數表示矩陣的內容a[i,j] 。(0 <= a[i,j] <= 1000)
接下來1行，一個數q，對應查詢的數量。(1 <= q <= 1000)
接下來q行，每行4個整數，對應矩陣的上下左右邊界u,d,l,r。(1 <= u <= d <= n, 1 <= l <= r <= m)
輸出
輸出共q行，對應q個詢問的求和結果。
輸入樣例
3 4
1 2 3 4
5 6 7 8
9 10 11 12
3
1 3 1 2
1 2 1 3
1 3 1 3
輸出樣例
33
24
54
分析
查詢子矩陣的和。
二維矩陣存儲，這里數組下標從1開始，便于后面查詢使用。

ac代碼

#include<iostream> #include<cmath> using namespace std; int n,m,q,u,d,l,r,sum=0; int a[101][101];int main(){cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}cin>>q;while(q--){cin>>u>>d>>l>>r;for(int i=u;i<=d;i++)for(int j=l;j<=r;j++)sum+=a[i][j];cout<<sum<<endl;sum=0;}}

總結

以上是生活随笔為你收集整理的51Nod5105 子矩阵求和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。