做宣传网站,开发公司需要什么资质,永州网站推广,design网站统计子矩阵
题目链接 思路#xff1a; 使用前缀和滑动窗口 #xff0c;可以先计算出纵向或横向的前缀和#xff0c;matrix[i][j]表示前i行第j列之和 然后遍历上边界top和下边界buttom#xff0c;再这个上下边界内使用滑动窗口#xff0c;由于前面维护了纵向前缀和…统计子矩阵
题目链接 思路 使用前缀和滑动窗口 可以先计算出纵向或横向的前缀和matrix[i][j]表示前i行第j列之和 然后遍历上边界top和下边界buttom再这个上下边界内使用滑动窗口由于前面维护了纵向前缀和所以转化成类似一维的滑动窗口。 滑动窗口[l,r]遍历右端点根据区间和调整左端点如果区间和大了左端点右移。注意区间和也要移除左端点直到找到满足的区间区间大小r-l1就是以r为右端点的满足条件子矩阵个数累加即可
#include iostream
using namespace std;
const int MAXN502;
int matrix[MAXN][MAXN];
int n,m,k,ans0;int main()
{scanf(%d%d%d,n,m,k);for(int i1;in;i){for(int j1;jm;j){scanf(%d,matrix[i][j]);matrix[i][j]matrix[i-1][j]; //前缀和第i行j列为第1行到第i行j列的和}}//枚举上下边界for(int top1;topn;top){for(int buttomtop;buttomn;buttom){int l1,r1; //滑动窗口的左右端点int sum0; //滑动窗口的和for(r1;rm;r){ //枚举右端点summatrix[buttom][r]-matrix[top-1][r]; //更新区间和加上右端那一列的值while(sumk){sum-matrix[buttom][l]-matrix[top-1][l]; //当前矩阵的sum大于k缩减左端l;}ansr-l1; //方法数就是区间大小}}}coutansendl;return 0;
}
