[C++知识库]蓝桥杯真题3

1. 统计子矩阵

输入:
3 4 10
1 2 3 4
5 6 7 8
9 10 11 12
输出：
19

#include<iostream>//前缀和与双指针的完美结合！！！
using namespace std;

int n,m,k;
int s[510][510];//存每一列上的前缀和
long long cnt;

int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&s[i][j]);
            s[i][j]=s[i][j]+s[i-1][j];
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)//外两层for循环遍历行
        {
            int l=1,sum=0;
            for(int r=1;r<=m;r++)//内层for循环对列进行双指针
            {
                sum=sum+s[j][r]-s[i-1][r];
                while(sum>k)//用双指针来维护sum，使其永远小于k
                {
                    sum=sum-(s[j][l]-s[i-1][l]);
                    l++;
                }
                cnt=cnt+r-l+1;//这里要着重说明一下r-l+1是怎么来的，并不是指的这个区间，而是从r开始往前数:[r,r], [r-1,r], [r-2,r],..., [l,r], 统计的这些区间和成立
            }
        }
    }
    cout<<cnt<<endl;
    return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖