「NOIP模拟赛」土豪聪要请客

2014年10月23日4,1603

众所周知，聪哥(ndsf)是个土豪，不过你们不知道的是他的MZ和他的RMB一样滴多……

某天土豪聪又赚了10^10000e的RMB，他比较开心，于是准备请客。他在自己在XX星上的别墅里面大摆酒席，想要邀请尽可能多的MZ来参加他的宴会。他将会同MZ一起坐在一个巨大的长方形桌子上。这个桌子能坐下的人数等于他的边长。聪哥要求他的桌子能够放进他的别墅，并且桌子的边必须与别墅的边界平行。给定别墅的平面图，请你求出聪哥最多可以请多少个MZ。

输入格式

第一行n,m。表示别墅的长宽

下面n行，每行M个字符，表示一个方块是空的(‘ ’)或是被占用了(‘X’)。

聪哥只要他的桌子放在别墅里，并且桌子不能占用任何一个已经占用了的方块。

输出格式

一个数，表示聪哥最多可以请几个Maze。

样例输入1

2 2

样例输出1

样例输入2

4 4

X.XX

X..X

..X.

..XX

样例输出2

对于60%的数据，n,m<=100

对于100%的数据，n,m<=400

题解

首先预处理每个格子向左拓展的最大长度f[i][j]

然后枚举上下边界l,r。。。然后枚举列x，则min{f[i][x]}(l<=i<=r)与r-l+1构成的长方形可以更新答案

复杂度n^4

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define ll long long
#define inf 1000000000
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,ans;
char a[405][405];
int f[405][405];
void pre()
{
    for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	    if(a[i][j]=='.')f[i][j]=f[i][j-1]+1;
	    else f[i][j]=0;
}
void cal(int l,int r,int x)
{
    int mn=inf;
    for(int i=l;i<=r;i++)
    {
	if(f[i][x]==0)return;
	mn=min(mn,f[i][x]);
    }
    ans=max(ans,(r-l+1+mn)*2);
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)
	scanf("%s",a[i]+1);
    pre();
    for(int l=1;l<=n;l++)
	for(int r=l;r<=n;r++)
	    for(int i=1;i<=m;i++)
		cal(l,r,i);
    printf("%d",ans-1);
    return 0;
}

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#define ll long long

#define inf 1000000000

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,ans;

char a[405][405];

int f[405][405];

void pre()

{

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

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

if(a[i][j]=='.')f[i][j]=f[i][j-1]+1;

else f[i][j]=0;

}

void cal(int l,int r,int x)

{

int mn=inf;

for(int i=l;i<=r;i++)

{

if(f[i][x]==0)return;

mn=min(mn,f[i][x]);

}

ans=max(ans,(r-l+1+mn)*2);

}

int main()

{

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

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

scanf("%s",a[i]+1);

pre();

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

for(int r=l;r<=n;r++)

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

cal(l,r,i);

printf("%d",ans-1);

return 0;

}

或者用相同的预处理方法，枚举每个格子i,j

以f[i][j]为宽向上下拓展，拓展到极大时（r-l+1）与f[i][j]可以更新答案

然后f[i][j]–，继续拓展，以此类推，复杂度n^3

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define ll long long
#define inf 1000000000
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,ans;
char a[405][405];
int f[405][405];
void pre()
{
    for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	    if(a[i][j]=='.')f[i][j]=f[i][j-1]+1;
	    else f[i][j]=0;
}
void cal(int x,int y)
{
    int mx=f[x][y],len=1;
    int L=x,R=n;
    while(mx)
    {
	while(L>1&&f[L-1][y]>=mx)L--,len++;
	while(R<n&&f[R+1][y]>=mx)R++,len++;
	ans=max(ans,2*(len+mx));
	mx--;
	if(!mx)return;
    }
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)
	scanf("%s",a[i]+1);
    pre();
    for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	    cal(i,j);
    printf("%d",ans-1);
    return 0;
}

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#define ll long long

#define inf 1000000000

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,ans;

char a[405][405];

int f[405][405];

void pre()

{

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

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

if(a[i][j]=='.')f[i][j]=f[i][j-1]+1;

else f[i][j]=0;

}

void cal(int x,int y)

{

int mx=f[x][y],len=1;

int L=x,R=n;

while(mx)

{

while(L>1&&f[L-1][y]>=mx)L--,len++;

while(R<n&&f[R+1][y]>=mx)R++,len++;

ans=max(ans,2*(len+mx));

mx--;

if(!mx)return;

}

int main()

{

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

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

scanf("%s",a[i]+1);

pre();

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

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

cal(i,j);

printf("%d",ans-1);

return 0;

}

或者按最大01子矩阵那样用前缀和来搞好像也是n^3
似乎有n^2做法？

顺便贴个数据生成器

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
using namespace std;
int n,m;
char s[3]={'.','.','X'};
int main()
{
	srand(time(0));
	n=400,m=400;
	cout<<n<<' '<<m<<endl;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			cout<<s[rand()%3];
		cout<<endl;
	}
	return 0;
}