8 solutions

  • 3
    @ 2024-4-20 15:32:25 
    #include<bits/stdc++.h>
using namespace std;
int m,n,q;
int a[105][105],p[105][105]={};
int x1,y11,x2,y2;

/*
	两条关键代码:

二维前缀和数组状态转移方程:
	
    p[i][j]=p[i-1][j]+p[i][j-1]-p[i-1][j-1]+a[i][j]
    
二维前缀和答案累加公式:
	
    ans=p[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]

*/

int main(){
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
		cin>>a[i][j];
		p[i][j]=p[i-1][j]+p[i][j-1]-p[i-1][j-1]+a[i][j];
	}
	while(q--){
		cin>>x1>>y11>>x2>>y2;
		cout<<p[x2][y2]-p[x1-1][y2]-p[x2][y11-1]+p[x1-1][y11-1]<<"\n";
	}
	return 0;
}
    • 1
      @ 2025-4-6 20:14:11 
      #include<iostream>
using namespace std;
int main(){
	int n,m,q,a[110][110]={},sum[110][110]={};
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++){
	    for(int j=1;j<=m;j++){
	    	cin>>a[i][j];
	    	sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
		}
	}
	for(int i=1;i<=q;i++){
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		int p=sum[x1-1][y1-1];
		int s=sum[x1-1][y2];
		int k=sum[x2][y1-1];
		cout<<sum[x2][y2]-s-k+p<<endl;
	}
}
      • 1
        @ 2025-4-6 19:57:22

        题目大意

        求一个矩阵中的子矩阵中所有元素的和。

        解题思路

        这种方法多用于二维前缀和的情形。给定大小为 m×nm\times n 的二维数组 AA，要求出其前缀和 SS。那么，SS 同样是大小为 m×nm\times n 的二维数组，且

        Si,j=∑i′≤i∑j′≤jAi′,j′S_{i,j} = \sum_{i'\le i}\sum_{j'\le j}A_{i',j'}

        类比一维的情形，Si,jS_{i,j} 应该可以基于 Si−1,jS_{i-1,j} 或 Si,j−1S_{i,j-1} 计算，从而避免重复计算前面若干项的和。但是，如果直接将 Si−1,jS_{i-1,j} 和 Si,j−1S_{i,j-1} 相加，再加上 Ai,jA_{i,j}，会导致重复计算 Si−1,j−1S_{i-1,j-1} 这一重叠部分的前缀和，所以还需要再将这部分减掉。这就是 容斥原理。由此得到如下递推关系：

        $$S_{i,j} = A_{i,j} + S_{i-1,j} + S_{i,j-1} - S_{i-1,j-1} $$

        实现时，直接遍历 (i,j)(i,j) 求和即可。

        同样的道理，在已经预处理出二位前缀和后，要查询左上角为 (i1,j1)(i_1,j_1)、右下角为 (i2,j2)(i_2,j_2)的子矩阵的和，可以计算

        $$S_{i_2,j_2} - S_{i_1,j_2} - S_{i_2,j_1} + S_{i_1,j_1} $$

        这可以在 O(1)O(1) 时间内完成。 在二维的情形，以上算法的时间复杂度可以简单认为是 O(mn)O(mn)，即与给定数组的大小成线性关系。但是，当维度 kk 增大时，由于容斥原理涉及的项数以指数级的速度增长，时间复杂度会成为 O(2kN)O(2^kN)，这里 kk 是数组维度，而 NN 是给定数组大小。因此，该算法不再适用。

        解题代码

        #include <bits/stdc++.h>
using namespace std;

int n, m, q, nx1, ny1, nx2, ny2, d[105][105], a[105][105];

int main()
{
	cin >> n >> m >> q;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			cin >> a[i][j];
			d[i][j] = d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1] + a[i][j];
		}
	}
	for(int i = 0; i < q; i++)
	{
		cin >> nx1 >> ny1 >> nx2 >> ny2;
		cout << d[nx2][ny2] - d[nx1 - 1][ny2] - d[nx2][ny1 - 1] + d[nx1 - 1][ny1 - 1] << endl;
	}
	return 0;
}

        拓展部分

        什么事逐维前缀和？

        对于一般的情形，给定 kk 维数组 AA，大小为 N，同样要求得其前缀和 SS。这里有，

        $$S_{i_1,\cdots,i_k} = \sum_{i'_1\le i_1}\cdots\sum_{i'_k\le i_k} A_{i'_1,\cdots,i'_k} $$

        从上式可以看出，kk 维前缀和就等于 kk 次求和。所以，一个显然的算法是，每次只考虑一个维度，固定所有其它维度，然后求若干个一维前缀和，这样对所有 kk 个维度分别求和之后，得到的就是 kk 维前缀和。

        然后我们就可以推出三维前缀和了：

        #include <iostream>
#include <vector>
using namespace std;

int main() {

  	int N1, N2, N3;
  	cin >> N1 >> N2 >> N3;
  	vector<vector<vector<int>>> a(N1 + 1, vector<vector<int>>(N2 + 1, vector<int>(N3 + 1)));
  	
  	for (int i = 1; i <= N1; ++i)
    	for (int j = 1; j <= N2; ++j)
      	for (int k = 1; k <= N3; ++k) cin >> a[i][j][k];

  	auto ps = a;

  	for (int i = 1; i <= N1; ++i)
    	for (int j = 1; j <= N2; ++j)
      	for (int k = 1; k <= N3; ++k) ps[i][j][k] += ps[i][j][k - 1];

  	for (int i = 1; i <= N1; ++i)
    	for (int j = 1; j <= N2; ++j)
      	for (int k = 1; k <= N3; ++k) ps[i][j][k] += ps[i][j - 1][k];

  	for (int i = 1; i <= N1; ++i)
    	for (int j = 1; j <= N2; ++j)
      	for (int k = 1; k <= N3; ++k) ps[i][j][k] += ps[i - 1][j][k];

  	for (int i = 1; i <= N1; ++i) {
    	for (int j = 1; j <= N2; ++j) {
      		for (int k = 1; k <= N3; ++k) {
        		cout << ps[i][j][k] << ' ';
      		}
      		cout << '\n';
    	}
    	cout << '\n';
  	}

  	return 0;
}

        因为考虑每一个维度的时候，都只遍历了整个数组一遍，这样的算法复杂度是 O(kN)O(kN) 的，通常可以接受。

        • 1
          @ 2024-4-20 15:49:08

          A1472 子矩阵的元素之和

          题意：求一个子矩阵中元素的和

          暴力解法：

          循环遍历子矩阵中的每个元素，sum+=，数据小没问题，大了直接TLE

          思路：

          其实不妨可以想想，如果我们已经用某种方法知道了这里以a[1][1]为左上角，a[x][y]为右下角的子矩阵元素之和(其实就是二维前缀和），问题就变得简单多了。 我们只需要剔除不必要的部分，由此我们可以通过小学学过的容斥原理即可求出矩阵大小，即用大矩阵元素和-（左半边元素和+上半边元素和），再补回多加的重叠部分即可。

          状态转移方程

          pfS[x2][y2]-pfS[x1-1][y2]-pfS[x2][y1-1]+pfS[x1-1][y1-1]

          具体代码

          #include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
int pfS[maxn][maxn];
int a[maxn][maxn];
int n,m,q;
int main(){
	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++){
			pfS[i][j]=pfS[i-1][j]+pfS[i][j-1]-pfS[i-1][j-1]+a[i][j];
		}
	}
	for(int i=1;i<=q;i++){
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		printf("%d\n",pfS[x2][y2]-pfS[x1-1][y2]-pfS[x2][y1-1]+pfS[x1-1][y1-1]);
	}
	return 0;
}
          • 0
            @ 2024-4-18 13:29:42

            题意

            n*m的矩阵,q组样例,输出每组样例相应的区间和(前缀和)

            思路

            纯纯的二维前缀和

            不会的参考二维前缀和

            代码

            tips:建议循环从1开始

            #include<iostream>
using namespace std;
int a[114][114];
int f[114][114];
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];//输入
            f[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j];//计算区间和
        }
    }
    for(int i=0;i<q;i++)
    {
        int x1,x2,y1,y2;
        cin>>x1>>y1>>x2>>y2;//输入,注意顺序
        cout<<f[x2][y2]-f[x1-1][y2]-f[x2][y1-1]+f[x1-1][y1-1]<<endl;//输出二维前缀和
    }
    return 0;//完结散花
}
            • -1
              @ 2024-6-13 14:45:35 
              #include<bits/stdc++.h>
using namespace std;
int m,n,q;
int a[105][105],p[105][105]={};
int x1,y11,x2,y2;

int main(){
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
		cin>>a[i][j];
		p[i][j]=p[i-1][j]+p[i][j-1]-p[i-1][j-1]+a[i][j];
	}
	while(q--){
		cin>>x1>>y11>>x2>>y2;
		cout<<p[x2][y2]-p[x1-1][y2]-p[x2][y11-1]+p[x1-1][y11-1]<<"\n";
	}
	return 0;
}
              • -1
                @ 2024-4-10 16:53:13

                题意

                n*m的矩阵,q组样例,输出每组样例相应的区间和(前缀和)

                思路

                纯纯的二维前缀和

                不会的参考二维前缀和

                代码

                tips:建议循环从1开始

                #include<iostream>
using namespace std;
int a[114][114];
int f[114][114];
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];//输入
            f[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j];//计算区间和
        }
    }
    for(int i=0;i<q;i++)
    {
        int x1,x2,y1,y2;
        cin>>x1>>y1>>x2>>y2;//输入,注意顺序
        cout<<f[x2][y2]-f[x1-1][y2]-f[x2][y1-1]+f[x1-1][y1-1]<<endl;//输出二维前缀和
    }
    return 0;//完结散花
}
                • -2
                  @ 2025-3-27 13:31:21

                  2维推导公式：

                  二维前缀和数组状态转移方程:

sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]

二维前缀和答案累加公式:

ans=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]

                  代码：

                  #include<bits/stdc++.h>
using namespace std;
int n,m,sum[114][514],a[114][514],q,px1,py1,px2,py2;
int main(){
	cin>>n>>m>>q;
	for(int i = 1 ; i <=n ; i++){
		for(int j = 1 ; j <= m ; j++){
			cin>>a[i][j];
			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
		}
	}
	for(int i = 0 ; i < q ; i++){
		cin>>px1>>py1>>px2>>py2;
		cout<<sum[px2][py2]-sum[px1 - 1][py2]-sum[px2][py1 - 1]+sum[px1 - 1][py1 - 1]<<endl;
	}
	return 0;
}
                  • 1

                  子矩阵的元素之和

                  Information

                  ID
                  1016
                  Time
                  1000ms
                  Memory
                  256MiB
                  Difficulty
                  4
                  Tags
                  (None)
                  # Submissions
                  66
                  Accepted
                  32
                  Uploaded By
                  1. About
                  2. Contact Us
                  3. Privacy
                  4. Terms of Service
                  5. Copyright Complaint
                  6. Language
                  7. Legacy mode
                  8. Theme
                  2. 粤ICP备2022044963号-1
                  3. Worker 0, 31ms
                  4. Powered by Hydro v4.13.3 Community