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