题目

https://www.luogu.com.cn/problem/P8783

思路

首先很容易想到的就是使用前缀和计算子矩阵的元素和。之后可以用暴力四重循环拿到80%的分数。

可以通过双指针“滑动窗口”优化一下。首先使用二重循环枚举子矩阵的上下边界，对于每一个确定上下边界的子矩阵，接下来要做的就是确定子矩阵的左右边界。

那么接下来的问题就由二维转换为了一维，和一维的滑动窗口具有异曲同工之妙。
使用双指针维护子矩阵的左右边界。按照习惯，使用外循环来维护滑动窗口的右端点（在这里是子矩阵的右边界），负责窗口的扩张；
然后左端点按照要求进行缩减窗口，维护一个边界状态。

对于一个确定右边界的滑动窗口，其左边界在窗口内均满足条件。所以加上贡献t-s+1即可。

Code

暴力80分代码

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

const int N = 510;
int n,m,k;
int a[N][N];

int Get(int x1,int y1,int x2, int y2)
{
    return a[x2][y2]-a[x2][y1-1]-a[x1-1][y2]+a[x1-1][y1-1];
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    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 ++)
            a[i][j] = a[i-1][j]+a[i][j-1]+a[i][j]-a[i-1][j-1];

    int res = 0;
    //开始枚举
    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 ++)
                {
                    int sum = Get(x1,y1,x2,y2);
                    if(sum <= k)
                    {
                        res ++;
//                      printf("%d %d %d %d\n",x1,y1,x2,y2);
                    }
                    else
                        break;
                }
    printf("%d",res);
    return 0;
}

滑动窗口优化

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

typedef long long ll;
const int N = 510;
int n,m,k;
int a[N][N];

int Get(int x1,int y1,int x2, int y2)
{
    return a[x2][y2]-a[x2][y1-1]-a[x1-1][y2]+a[x1-1][y1-1];
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    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 ++)
            a[i][j] = a[i-1][j]+a[i][j-1]+a[i][j]-a[i-1][j-1];

    ll res = 0;
    //i,j枚举子矩阵的上下边界
    for(int i = 1; i <= n; i ++)
        for(int j = i; j <= n; j ++)
        //暴力枚举子矩阵的上下边界(C[n,2]种选法)
            for(int t = 1, s = 1; t <= m; t ++)//t为右边界
            {
                //对于每一个右边界t，找到一个满足条件的左边界s
                //维护一个滑动窗口[s,t]
                while(s<=t && Get(i,s,j,t)>k) //直到左右边界构成的矩阵满足条件
                    s++;
                if(s<=t)
                    res += t-s+1;
            }
            //t s指针都不回退，利用单调性维护一个窗口，进行窗口的缩减和扩张
    printf("%lld",res);
    return 0;
}

注意res要开long long，因为所有可能的子矩阵个数为 $C^2_{500}=6·10^{10}$，会爆int。