COJ 2105 submatrix
2024-08-21 01:56:44
submatrix |
难度级别: A; 编程语言:不限;运行时间限制:2000ms; 运行空间限制:131072KB; 代码长度限制:102400B |
试题描述
|
小A有一个N×M的矩阵,矩阵中1~N*M这(N*M)个整数均出现过一次。现在小A在这个矩阵内选择一个子矩阵,其权值等于这个子矩阵中的所有数的最小值。小A想知道,如果他选择的子矩阵的权值为i(1<=i<=N×M),那么他选择的子矩阵可能有多少种?小A希望知道所有可能的i值对应的结果,但是这些结果太多了,他算不了,因此他向你求助。 |
输入
|
第一行,两个整数N, M。
接下来的N行,每行M个整数,表示矩阵中的元素。 |
输出
|
N×M行,每行一个整数,其中第i行的整数表示如果小A选择的子矩阵权值为i,他选择的子矩阵的种类数。
|
输入示例
|
2 3
2 5 1 6 3 4 |
输出示例
|
6
4 5 1 1 1 |
其他说明
|
对于30%的数据,1<=N, M<=50;
对于全部的数据,1<=N, M<=300。 |
题解:%%%郑爷,先考虑一维,用单调栈维护一下可以到左边右边,更新答案。对于二维,把一维拍扁就可以了。。。。记得是取最小值。。。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
using namespace std;
const int maxn=+,maxans=+,inf=-1u>>;
int A[maxn][maxn],mi[maxn],R[maxn],L[maxn],s[maxn],pos[maxn],p[maxans],n,m;
inline int read(){
int x=,sig=;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')sig=;
for(;isdigit(ch);ch=getchar())x=*x+ch-'';
return sig?x:-x;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=,buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
void init(){
n=read();m=read();
for(int i=;i<=n;i++)for(int j=;j<=m;j++)A[i][j]=read();
for(int i=;i<=n;i++){
for(int j=;j<=m;j++)mi[j]=inf;
for(int j=i;j<=n;j++){
for(int k=;k<=m;k++)mi[k]=min(mi[k],A[j][k]);int top=;
for(int k=;k<=m;k++){//正
while(top&&(mi[k]<s[top]))R[pos[top--]]=k-;
s[++top]=mi[pos[top]=k];
}while(top)R[pos[top--]]=m;
for(int k=m;k>=;k--){//反
while(top&&(mi[k]<s[top]))L[pos[top--]]=k+;
s[++top]=mi[pos[top]=k];
}while(top)L[pos[top--]]=;
for(int k=;k<=m;k++)p[mi[k]]+=(R[k]-k+)*(k-L[k]+);
}
}int all=n*m;for(int i=;i<=all;i++)write(p[i]),ENT;
return;
}
void work(){
return;
}
void print(){
return;
}
int main(){init();work();print();return ;}
最新文章
- SQL存储过程分页(通用的拼接SQL语句思路实现)
- 转载《android:scaleType属性》
- hdu.1044.Collect More Jewels(bfs + 状态压缩)
- 【0 - 1】OC内存管理
- fetch API
- Ubuntu 16.04 Vysor 破解 和黑屏问题解决+ 闪屏问题解决
- WebView loadData出错(奇怪的设计)
- jQuery练习实例(四)
- http://python3-cookbook.readthedocs.io/zh_CN/latest/c14/p01_testing_output_sent_to_stdout.html
- 华为交换机boot默认密码
- 记住这个网站:服务器相关数据统计网站 http://news.netcraft.com/
- 数据库优化案例——————某知名零售企业ERP系统
- Python 学习 第十一篇:numpy
- win+python+selenium实现窗口和tab切换
- 第二章 C#语法基础(2.1 C#语言的数据类型一)
- git初始化本地项目及关联github远程库
- django的forms认证组件
- 移动端(处理边距样式)reset.css
- SQL Server 日期函数大全
- js读取iframe里的元素