文章

统计子矩阵(2022省赛)

统计子矩阵1.png统计子矩阵2.png

前缀和+滑动窗口

#include<bits/stdc++.h>
using namespace std;
long long int a[1001][1001];
long long int s[1001][1001];
int main()
{
    long long int n,m,k,key,i,j,f,cnt=0,t;
    cin>>n>>m>>key;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        cin>>a[i][j];
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
        }
    }
    for(k=1;k<=n;k++){
        for(f=1;f<=m;f++){//右下角 
            for(i=1;i<=k;i++){
                for(j=1;j<=f;j++){//左上角 
                    t=s[k][f]-s[i-1][f]-s[k][j-1]+s[i-1][j-1];
                    if(t<=key){
                        cnt+=(f-j+1);
                        break;
                    }
                }
            }
        }
    }
    cout<<cnt<<endl;
    return 0;
}

原题链接

https://www.lanqiao.cn/problems/2109/learning/

License:  CC BY 4.0