P8783统计子矩阵

· · 个人记录

题面

从给定的一个大矩阵中最多能找到多少个总和不大于k的矩阵？

方法0.5

直接暴力左上端点和右下端点并统计这个矩阵的和看看是否大于k（好愚蠢的做法）。这样肯定会TLE到爆炸，所以这个方法就out了。

方法1

基于方法0.5，我们可以将一部分优化，就比如说我们对统计子矩阵和下手，这非常明显就可以用二维前缀和。然后我们就会获得一份时间复杂度为O(n^2m^2)的代码。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int a[1005][1005],sum[1005][1005];
int ans,k;
signed main()
{
    ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);//尝试使用愚蠢的优化卡过
     cin>>n>>m>>k;
    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 x1=1;x1<=n;x1++)
    {
        for(int y1=1;y1<=m;y1++)
        {
            for(int x2=x1;x2<=n;x2++)
            {
                for(int y2=y1;y2<=m;y2++)
                {
                    if(sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]<=k)
                    {
                        //cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;
                        ans++;
                    }
                }
            }
        }
    }
    cout<<ans;

    return 0;
}

但是，这份代码的时间复杂度并不客观 毕竟他足足有500^4的时间复杂度。

究极方法

那我们如何优化呢？于是我们开始想那些常见的优化方法。前缀和？已经用了。二分？可惜他并不是有序的。这时候我们就想到了双指针（不会的由此门出）。这里用这个方法非常合适，基于方法1我们可以将遍历左上、右下端点y轴位置的O(nm)暴力该为一个双指针，O(m)遍历右下y轴位置，再不断下移左上对应的y轴坐标直至这个矩阵比k小。我们也可以发现最大的矩阵比k小，那么他的子矩阵也比k小。这样一次双指针就可以找出许许多多的合法矩阵了。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int a[1005][1005],sum[1005][1005];
int ans,k;
signed main()
{
    ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);

    cin>>n>>m>>k;
    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 x1=1;x1<=n;x1++)
    {
        for(int y1=1;y1<=m;y1++)
        {
            for(int x2=x1;x2<=n;x2++)
            {
                for(int y2=y1;y2<=m;y2++)//我没有改变量名，方便大家对比超时代码
                {
                    if(sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]<=k)
                    {
                        ans++;
                    }
                }
            }
        }
    }
    cout<<ans;

    return 0;
}