P8783 题解

· · 题解

题目大意

给定一个 n\times m 的矩阵，求其中有多少个子矩阵的所有元素之和小于等于 k。

解题思路

要想确定一个矩阵，只需要确定其左上角的点 (x1,y1) 和右下角 (x2,y2) 的点即可。注意 x1\le x2,y1\le y2。

枚举左上角的点和右下角的点，再扫描 x\in[x1,x2],y\in[y1,y2] 的所有点，暴力加起来，就得到了一个矩阵中的所有元素之和。与 k 比较并统计答案。

时间复杂度 O(n^3\times m^3)。

与 30 分做法相同，扫描左上角与右下角的点，耗费 O(n^2\times m^2) 的时间复杂度。考虑如何 O(1) 求出矩阵中的元素之和。

使用二维前缀和，用 sum[i][j] 表示矩阵中 x\in[1,i],y\in[1,j] 的所有元素之和。其递推式为 sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]，具体不再赘述。

所以矩阵该矩阵的元素之和就可以用 sum[x2][y2]-sum[x2-1][y1]-sum[x1-1][y2]+sum[x1-1][y1-1] 来表示。我们就做到了 O(1) 求出矩阵中的元素之和。

时间复杂度 O(n^2\times m^2)

考虑如何把复杂度压到三次方的级别。

我们可以假想有水平的两条横线，切出了中间一块区域。用 O(n^2) 的时间，枚举这两条横线（如下图所示）。

枚举出两条横线之后，就可以把中间的每一列数给当成一个整体，例如上图 l1=1,l2=2 的情况下，就可以把矩阵视为一个序列 [6,8,10,12]。

我们只需要求出在这个序列中，有几个子序列的元素之和小于等于 k 即可。这就把二维问题转化为了一维问题，这种“降维打击”的方法，是很多题目解题的切入点。

那么现在我们还有 O(m) 的时间来处理子序列的问题。考虑有两个指针 l 和 r，代表子序列的左端点与右端点。注意到矩阵中所有的元素都是正数，那么显然有下面两个结论：

  1. 若 sum(l,r)\le k，且 l+1\le r，则 sum(l+1,r)\le k。
  2. 若 sum(l,r)>k，且 r+1\le n，则sum(l,r+1)>k。

在遍历 r 时，如果当前的子序列元素和小于等于 k，那么就有 r-l+1 个新答案。如果大于 k 了，就考虑向右移动 l，使得最终的子序列元素和仍然小于等于 k。

举个例子：有一个序列 [1,3,4,3]，试求出其中有多少个子序列，满足该子序列的所有元素之和小于等于 10。

批注：因为 l=1,r=2 都可以，那么 l=2,r=2 肯定可以。

批注：此时考虑移动 l 使得 sum\le k。 只需要向右移动一格 l 就行了。

此时 r=4，且有解了，停止循环。

参考代码与总结

#include<bits/stdc++.h>
using namespace std;
long long n,m,k,a[510][510],sum[510][510],b[510];
long long l,r,now,ans;
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    for(int j=1;j<=m;j++)
        for(int i=1;i<=n;i++)
            sum[i][j]=sum[i-1][j]+a[i][j];
    for(int x=1;x<=n;x++)
        for(int y=x;y<=n;y++){
        //  cout<<x<<" "<<y<<":"<<endl;
            for(int j=1;j<=m;j++)
                b[j]=sum[y][j]-sum[x-1][j];
            //双指针
            l=1;r=1;now=0;
            for(r=1;r<=m;r++){
                now+=b[r];
                if(now<=k){
                //  cout<<l<<" "<<r<<" "<<now<<endl; 
                    ans+=r-l+1;
                }
                else{
                    while(now>k){
                        now-=b[l];
                        l++;
                    }
                    ans+=r-l+1;
                }
            }
        //  cout<<"-------"<<endl;
        }
    cout<<ans<<endl;
    return 0;
}

总结：该题的解题方法：

  1. “降维打击” 法：把二维问题转化为一维。
  2. 双指针法：把 O(n^2) 的复杂度，通过单调性等优秀性质，转化为 O(n)。