题目

分析

首先，设\(f_{i,j}\)表示最大的以(i,j)为左下角的正方形的边长。

转移显然，\(f_{i,j}=\max(f_{i-1,j},f_{i,j-1},f_{i-1,j-1})+1\)

接着，再设\(g_{i,j,k,l}\)表示在以\((k,l)\)为左上角，\((k+2^i-1,l+2^j-1)\)为右下角的矩阵中，最大的f。

二维rmq就不讲了。

假设询问矩阵(x,y,x1,y1)，

二分答案ans（想想为什么？）

用rmq看红色区域中的最大f值是否合法。

注意：出题人将输入调的太大了，要打读入优化。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

#include <cmath>

const int maxlongint=2147483647;

const int mo=1000000007;

const int N=1002;

using namespace std;

int f[N][N],n,m,T,g[11][11][N][N],a[N][N],logn,logm;

int read(int &n)

{

	char ch=' ';

	int q=0,w=1;

	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());

	if(ch=='-') w=-1,ch=getchar();

	for(;ch>='0' && ch<='9';ch=getchar()) q=q*10+ch-48;n=q*w;

	return n;

}

int min2(int x,int y)

{

	if(x>y) x=y;

	return x;

}

int max2(int x,int y)

{

	if(x<y) x=y;

	return x;

}

int min1(int x,int y,int z)

{

	if(x>y) x=y;

	if(x>z) x=z;

	return x;

}

int max1(int x,int y,int z,int a)

{

	if(x<y) x=y;

	if(x<z) x=z;

	if(x<a) x=a;

	return x;

}

int pref()

{

	int i,j;

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

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

			if(a[i][j])

				g[0][0][i][j]=f[i][j]=min1(f[i-1][j-1],f[i-1][j],f[i][j-1])+1;

}

int prermq()

{

	int i,j,k,l;

	for(i=0;i<=logn;i++)

	{

		for(j=0;j<=logm;j++)

		{

			if(j+i!=0)

			{

				int p=1<<(i-1);

				int q=1<<(j-1);

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

					if(k+p<=n)

					{

						for(l=1;l<=m;l++)

							if(l+q<=m)

							{

								if(i!=0 && j!=0)

									g[i][j][k][l]=max1(g[i-1][j-1][k][l],g[i-1][j-1][k+p][l],g[i-1][j-1][k+p][l+q],g[i-1][j-1][k][l+q]);

								else

								if(i==0)

									g[i][j][k][l]=max2(g[i][j-1][k][l],g[i][j-1][k][l+q]);

								else

								if(j==0)

									g[i][j][k][l]=max2(g[i-1][j][k][l],g[i-1][j][k+p][l]);

							}

							else break;

					}

					else break;

			}

		}

	}

}

int rmq(int x,int y,int x1,int y1)

{

	int p=log2(x1-x+1),q=log2(y1-y+1);

	return max1(g[p][q][x][y],g[p][q][x1-(1<<p)+1][y],g[p][q][x][y1-(1<<q)+1],g[p][q][x1-(1<<p)+1][y1-(1<<q)+1]);

}

int rf(int x,int y,int x1,int y1)

{

	int lx=x1-x+1,ly=y1-y+1,l=1,r=min2(lx,ly);

	while(l<r-1)

	{

		int mid=(l+r)/2;

		if(rmq(x+mid-1,y+mid-1,x1,y1)>=mid)

			l=mid;

		else

			r=mid-1;

	}

	if(rmq(x+r-1,y+r-1,x1,y1)>=r)

		printf("%d\n",r);

	else

	if(rmq(x+l-1,y+l-1,x1,y1)>=l)

		printf("%d\n",l);

	else

		printf("0\n");

}

int main()

{

	scanf("%d%d",&n,&m);

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

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

		{

			read(a[i][j]);

			f[i][j]=a[i][j];

		}

	pref();

	logn=log2(n);

	logm=log2(m);

	prermq();

	scanf("%d",&T);

	int x1,x2,y1,y2;

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

	{

		read(x1);

		read(y1);

		read(x2);

		read(y2);

		rf(x1,y1,x2,y2);

	}

}

巴特西

【NOIP2016提高A组五校联考4】square

题目

分析

最新文章

热门文章