首页 > 其他分享 >全零子矩形计数问题

全零子矩形计数问题

时间:2024-11-10 16:09:50浏览次数:1  
标签:sum 矩阵 up 零子 计数问题 矩形 rep 单调

经典问题,但是我为什么不会呢?????

题意

给定一张 \(n\times m\) 的 01 矩阵,求出有多少个子矩阵使得子矩阵内没有 1。

\(n,m\le 10^3\)

分析

考虑枚举每一行,计算以该行上每个点为右下角的合法子矩形个数 \(\sum sum_{i,j}\),也就是说,计算左上角的个数使得左上角和该右下角形成的子矩形不包含 1。

其实到这里已经可以思考单调栈了,但是为了捋顺思路,我们还是考虑对于每一行,只有该列上方的第一个 1 会对子矩形大小产生限制,而在某一个 1 往左的比该 1 所在行数要靠前的那些 1 也不会产生限制。据此我们考虑单调栈,预处理 \(up_{i,j}\) 表示 \((i,j)\) 往上第一个 1 和它本身的距离,单调栈里维护一个递增的 \(up_{i,j}\) 和 \(\sum sum_{i,j}\),将比 \(up_{i,j}\) 大的点弹完后,令栈顶的列为 \(c\),由于单调栈 \(up\) 递增,\(sum_{i,c}\) 的答案可以直接继承到 \(sum_{i,j}\) 中,额外的贡献还有 \(x\in(up_{i,c},up_{i,j}],y\in (c,j]\) 这部分子矩形的点,把它们加进 \(sum_{i,j}\) 中。

时间复杂度 \(O(nm)\)。

rep(j,1,m){
	rep(i,1,n){
		if(s[i][j]=='1')up[i][j]=0;
		else up[i][j]=up[i-1][j]+1;
	}
}
int ans=0;
rep(i,1,n){
	tp=0;
	sum[0]=0;
	rep(j,1,m){
		while(tp&&up[i][j]<=up[i][sta[tp]])--tp;
		sum[j]=(sum[sta[tp]]+1ll*(j-sta[tp])*up[i][j]%mod)%mod;
		ans=(ans+sum[j])%mod;
		sta[++tp]=j;
	}
}

标签:sum,矩阵,up,零子,计数问题,矩形,rep,单调
From: https://www.cnblogs.com/dcytrl/p/18538111

相关文章

  • Leetcode 3235. 判断矩形的两个角落是否可达
    1classSolution{2public:3boolcanReachCorner(intxCorner,intyCorner,vector<vector<int>>&circles){4vector<bool>visited(circles.size(),false);56function<bool(int)>dfs=[&](inti)......
  • 力扣21 打卡16 判断矩形的两个角落是否可达
    思路:首先,检查矩形的起点和终点是否在任何一个圆的范围内,如果是则不存在合法路径。接着,判断每个圆是否与矩形的左上角边界或右下角边界相交。对于与左上边界相交的圆,使用深度优先搜索(DFS),查找是否存在一组相连的圆,最终能连接到右下边界。若找到这样的路径,则矩形被封锁,返回Fa......
  • 纯基础,新手小白也能学会:python的循环,循环控制以及图形输出(矩形,三角形,九九乘法表)
    python循环1.python的循环2.python循环控制3.图形输出1.矩形2.平行四边形3.直角三角形4.等腰直角三角形5.打印九九乘法表1.python的循环循环三要素:循环变量初始化循环条件改变循环变量i=1#循环变量初始化whilei<=5:print(f'跑到了第{i}圈')i......
  • LeetCode题练习与总结:矩形区域不超过 K 的最大数值和--363
    一、题目描述给你一个 mxn 的矩阵 matrix 和一个整数 k ,找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。题目数据保证总会存在一个数值和不超过 k 的矩形区域。示例1:输入:matrix=[[1,0,1],[0,-2,3]],k=2输出:2解释:蓝色边框圈出来的矩形区域 [[......
  • 【PTA 编程题 7-3 】矩形运算 #C语言
    代码#include<stdio.h>#defineMAXM10#defineMAXN10intmain(void){intn;scanf("%d",&n);inta[MAXM][MAXN];for(inti=0;i<n;i++){for(intj=0;j<n;j++){scanf("%d",&a[i][j]);......
  • C#判断点是否在矩形内
    前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家!人工智能学习网站前言:大家好,我是上位机马工,硕士毕业4年年入40万,目前在一家自动化公司担任软件经理,从事C#上位机软件开发8年以上!我们在C#开发中经常需要对平面中的坐标位置进行一些判断,比如判......
  • 遍历矩形的主对角线
    B.SakurakoandWater对于上三角遍历的顺序是我们举例n=3,m=3(1,1)(2,2)(3,3)(1,2)(2,3)(1,3)所以上三角可以这样遍历 //上三角 for(inti=1;i<=n;i++) { for(intj=1,k=i;k<=n;k++,j++);//todo //j对应每次的横坐标,k对应每次的纵坐标 } //下三角同理 for(inti=2;i<=n;i++)......
  • Python数值计算(30)——矩形及复合矩形积分公式
    前面介绍了数值积分的基本背景知识,接下来就介绍各种常见的数值积分算法,本次主要介绍矩形和梯形积分公式。1.矩形积分公式对于一个连续函数,根据中值定理有:现在的关键是如何确定使误差尽可能比较小,一个比较简单的想法是使用该区间中间值,亦即Python中实现代码如下:defRectI......
  • React实现画布——可绘制矩形和箭头
    目录思路代码效果本文将使用React、JSX、Rough.js实现一个简单的画布,可以绘制矩形和箭头。思路每一个图形包括:绘制的类型、起点的x坐标、起点的y坐标、宽、高。调用rough的generator()函数传入图形信息进行绘制,其中对于箭头需要进一步处理:根据宽高确定终点,并且定义角度等生......
  • 字典树 计数问题(含 2022 icpc杭州 K)
    //最近学了字典树,补一下1.概念和实现首先,字典树是一棵树(废话),边表示字母,从根到叶子节点所有边的顺序组合表示字目排列顺序。看一下图明白很多:例如:abc这个字母排序(或者说“单词”),可以用1->2->5->8这条路径表示。有个性质就是:同一个单词的末尾节点标号是唯一的。比如以6为末尾......