「NOIP模拟赛」chenzeyu97要请客

众所周知，哲♂学家chenzeyu97由于在前面的许多场比赛中都取得了优♂异成绩！所以他在这场赛后要请客！

题目描述

chenzeyu97的家可以看成是一个n*m的矩阵，每块区域都有独一无二的海拔高度h（h>0）！其最大值为n*m。现在他要选择一个子矩阵摆放一张桌子，在他眼里，这样摆放桌子的美观度为这个子矩阵的最小值，他想知道，如果他要求摆放桌子的美观度为i，那么可以选择多少种子矩阵呢？对于所有可能的i值（1<=i<=n*m），你都应该得出其方案数，这样你就能顶替蒟蒻hzwer获得被请客的资格！

输入格式

第一行两个整数n，m

接下来n行，每行m个整数，描述chenzeyu97的家

输出格式

n*m行，每行一个整数，第i行表示美观度i的方案数

样例数据 1

输入

2 3
2 5 1
6 3 4

输出

6
4
5
1
1
1

备注

30%的数据1<=n,m<=50

100%的数据1<=n,m<=300

题解

首先肯定要枚举左右边界L-R吧。。。

我们知道每一行L-R的最小值，这个可以从L-1-R在O1的时间内转移

然后考虑在行上统计答案

问题转换为一个数列，要在On的时间内统计出每个子区间最小值

对于每个数a[x]，我们只要知道前一个比它小的数a[y]，则a[y+1]到a[x-1]在x之后都不重要了

可以用一个a[x]和f[x]来替代他们，将a[x]和f[x]放入单调栈

具体过程是：如果要加入一个点i，只要栈顶最小值比它大，就不停地把栈顶并给i，同时考虑对答案的影响

for(int i=1;i<=n;i++)
	{
		f[i]=1;sum=1;
		while(top&&mn[st[top]]>mn[i])
		{
			f[i]+=f[st[top]];
			ans[mn[st[top]]]+=f[st[top]]*sum;
			sum+=f[st[top]];
			top--;
		}
		st[++top]=i;
	}

for(int i=1;i<=n;i++)

{

f[i]=1;sum=1;

while(top&&mn[st[top]]>mn[i])

{

f[i]+=f[st[top]];

ans[mn[st[top]]]+=f[st[top]]*sum;

sum+=f[st[top]];

top--;

}

st[++top]=i;

}

类似的，最后处理栈中剩余元素

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define ll long long 
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;
int a[305][305];
int mn[305],st[305];
ll f[305],ans[90005];
void cal(int l,int r)
{
	int top=0;ll sum;
	for(int i=1;i<=n;i++)
	{
		f[i]=1;sum=1;
		while(top&&mn[st[top]]>mn[i])
		{
			f[i]+=f[st[top]];
			ans[mn[st[top]]]+=f[st[top]]*sum;
			sum+=f[st[top]];
			top--;
		}
		st[++top]=i;
	}
	sum=0;
	for(int i=top;i;i--)
	{
		ans[mn[st[i]]]+=f[st[i]];
		ans[mn[st[i]]]+=f[st[i]]*sum;
		sum+=f[st[i]];
	}
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			a[i][j]=read();
	for(int i=1;i<=m;i++)
	{
		memset(mn,127,sizeof(mn));
		for(int j=i;j<=m;j++)
		{
			for(int k=1;k<=n;k++)
				mn[k]=min(mn[k],a[k][j]);
			cal(i,j);
		}
	}
	for(int i=1;i<=n*m;i++)
		printf("%lld\n",ans[i]);
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cstring>

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m;

int a[305][305];

int mn[305],st[305];

ll f[305],ans[90005];

void cal(int l,int r)

{

int top=0;ll sum;

for(int i=1;i<=n;i++)

{

f[i]=1;sum=1;

while(top&&mn[st[top]]>mn[i])

{

f[i]+=f[st[top]];

ans[mn[st[top]]]+=f[st[top]]*sum;

sum+=f[st[top]];

top--;

}

st[++top]=i;

}

sum=0;

for(int i=top;i;i--)

{

ans[mn[st[i]]]+=f[st[i]];

ans[mn[st[i]]]+=f[st[i]]*sum;

sum+=f[st[i]];

}

int main()

{

n=read();m=read();

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

a[i][j]=read();

for(int i=1;i<=m;i++)

{

memset(mn,127,sizeof(mn));

for(int j=i;j<=m;j++)

{

for(int k=1;k<=n;k++)

mn[k]=min(mn[k],a[k][j]);

cal(i,j);

}

for(int i=1;i<=n*m;i++)

printf("%lld\n",ans[i]);

return 0;

}

hzwer.com _ Home | http://hzwer.com

题目背景

题目描述

输入格式

输出格式

样例数据 1

备注

分类目录

热门文章

Myfriends

近期评论