试题 F: 统计子矩阵

时间限制: 1.0s 内存限制: 256.0MB 本题总分：15 分

【问题描述】

给定一个 N × M 的矩阵 A，请你统计有多少个子矩阵 (最小 1 × 1，最大
N × M) 满足子矩阵中所有数的和不超过给定的整数 K?

【输入格式】

第一行包含三个整数 N, M 和 K.
之后 N 行每行包含 M 个整数，代表矩阵 A.

【输出格式】

一个整数代表答案。

【样例输入】

3 4 10
1 2 3 4
5 6 7 8
9 10 11 12

【样例输出】

19

【样例说明】

满足条件的子矩阵一共有 19，包含：
大小为 1 × 1 的有 10 个。
大小为 1 × 2 的有 3 个。
大小为 1 × 3 的有 2 个。
大小为 1 × 4 的有 1 个。
大小为 2 × 1 的有 3 个。

【评测用例规模与约定】

对于 30% 的数据，N, M ≤ 20.
对于 70% 的数据，N, M ≤ 100.
对于 100% 的数据，1 ≤ N, M ≤ 500; 0 ≤ Ai j ≤ 1000; 1 ≤ K ≤ 250000000.

30分思路

朴素做法：5重循环暴力求解

70分思路：

预处理二维前缀和，枚举对角线
时间复杂度：O(nnmm(m+1)(n+1)/4)~O(nnnmmm/4);

70分代码

#include<cstdio>
#include<iostream>
using namespace std;
int n,m,k,a[510][510],s[510][510];
int ans,f[510][510];
int get(int x1,int y1,int x2,int y2)
{
	return s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];
}

int main()
{
     cin>>n>>m>>k;
     for(int i=1;i<=n;i++)
     {
     	for(int j=1;j<=m;j++)
     	{
     		cin>>a[i][j];
     		s[i][j]+=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
		}
	 }
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			for(int ii=0;ii<=n-i;ii++)
			{
				for(int jj=0;jj<=m-j;jj++)
				{
					int x1=i,y1=j,x2=i+ii,y2=j+jj;
					if(get(x1,y1,x2,y2)<=k) f[i][j]++;
			
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(f[i][j]) ans+=f[i][j];
		
		}
	}
	cout<<ans;
	return 0;
}

100分思路

二维前缀和+枚举上下界 双指针左右查找

时间复杂度O(nnm)

100分AC代码：

#include<cstdio>
#include<iostream>
using namespace std;
int n,m,k,a[510][510],s[510][510];
long long ans,f[510][510];
#define ll long long
long long get(int x1,int y1,int x2,int y2)
{
    return s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];
}

int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
     	{
     	    cin>>a[i][j];
     		s[i][j]+=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
	}
    }
    for(int l=1;l<=m;l++)
    {
        for(int r=l;r<=m;r++)
        {
	    int j=1;
	    for(int i=1;i<=n;i++)
	    {
	        while(j<=i&&1ll*get(j,l,i,r)>k) j++;
	        ans+=(i-j+1);
            }
        }
    }
  /*for(int i=1;i<=n;i++)
    {
	for(int j=1;j<=m;j++)
	{
	    if(f[i][j]) ans+=f[i][j];
	}
    }*/
    cout<<ans;
    return 0;
}