求01矩阵里有多少个不同的1矩阵

首先预处理出pre[i][j]表示i上面连续的1个数,对每行的高度进行单调栈处理

栈里的元素维护两个值:pre[i][j]和向前延伸最多能维护的位置pos

然后算贡献,从左往右扫时维护一个最靠右下面没有1的列的位置p,

元素在被弹出时判断其pos是否能包含p,如果能说明这个元素代表的矩阵是有贡献的

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
typedef vector<int>vi; #define rep(i,a,b) for(int i=(a);i<(b);i++)
#define fi first
#define se second
#define de(x) cout<<#x<<"="<<x<<endl;
#define dd(x) cout<<#x<<"="<<x<<" " ;
#define pb(x) push_back(x)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
const int N=5e3+;
char mp[N][N];
int h[N][N];
int area[N][N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=;i<=n;++i)
scanf("%s",mp[i]+); memset(h,,sizeof(h));
for(int i=;i<=n;++i)
for(int j=;j<=m;++j)
if(mp[i][j]==''){
h[i][j]=h[i-][j]+;
}
int ans=;
for(int i=;i<=n;++i){
stack<pii>stk;
int ma=-;
for(int j=;j<=m+;++j){
int pos=j;
while(!stk.empty()&&stk.top().fi>h[i][j]){
cout<<stk.top().fi<<'\n';
if(stk.top().se<=ma){
ans++;
}
pos=stk.top().se;
stk.pop();
}
if(!h[i+][j])ma=j;
if(h[i][j]&& ( stk.empty() || (stk.top().fi<h[i][j]) ) )
stk.push(pii(h[i][j],pos));
}
}
cout<<ans<<endl;
return ;
}

最新文章

  1. Oracle两列字段替换和复制
  2. 在四合院里写code是什么体验(非拉仇恨)
  3. jQuery对json快速赋值
  4. Kiwi iOS驱动测试开发
  5. mgo中DBRef-数据查询测试
  6. Swift 3.0 使用Core Data
  7. 解决&amp;nbsp在IE与firefox宽度不一致的问题
  8. php __autoload使用
  9. 如何编写makefile
  10. mysql处理存在则更新,不存在则插入(多列唯一索引)
  11. 命令行调试smali
  12. 团队作业10--Beta阶段项目复审
  13. golang的GET请求(类似于PHP的CURL)
  14. Python基础:六、变量和常量
  15. 2019/2/11 LinuxRPM包管理
  16. C++实现第三方资源释放与载入过程(以DLL为例)
  17. linux shell系列9 统计用户的权限
  18. discuz 忘记安全密码的处理方式 修改pre_common_setting表的数据,
  19. django 模型类的常见字段约束,以及filter 过滤和查询
  20. 《jquery实战》javascript 必知必会(1)

热门文章

  1. 【LeetCode】二分
  2. 影响Acorn for Mac图像打印质量的因素有什么?怎样处理这些因素才能得到打印效果最佳的图像?
  3. layer.msg的使用
  4. php重定向说明
  5. Vue学习笔记【18】——Vue中的动画(使用过渡类名)
  6. Vue学习笔记【4】——Vue指令之v-on
  7. Android中的Toast重复显示的问题
  8. MySql中创建用户,授权
  9. DNS域名服务器的搭建
  10. [ZJOI2011]看电影(组合数学/打表+高精)