自动搬运

查看原文

来自洛谷，原作者为

	WeLikeStudying 

搬运于2025-08-24 22:21:01，当前版本为作者最后更新于2020-08-30 13:44:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前言：

• 题目的数据似乎被人为扩充到了 n,m≤350 。
• 以前好像数据很水，各种暴力都能卡过。
• 题面是n,m≤100是错的。
• 注意 n,m≤350 ，别被坑得RE。

---

题面简述

• n×m 的方阵，得找一个金字塔那样的东西，第一圈是1，第二圈是2，...，有k次机会让某一个点的值提高1，求能够建成的最高的金字塔。
• n,m≤350 ，提高次数 k≤10⁸，矩阵的数字都在0到50之间。

---

思路

判断一个方阵是否能够搭建金字塔，需要：

• 判断金字塔要多少次提高地面的机会，这点，两个矩阵相减即可。
• 判断提高地面是否一定能建成，即判断第一层是否小于等于1，第二层是否小于等于2，...以此类推，否则机会再多也无法建成。

---

下面是一些算法（以下所有的时间复杂度基于m,n规模相差不大的假设)。

---

1. $O(n^5)$ 算法

• 分别枚举正方形的两个顶点，可以确定整个正方形。
• $O(n^5)$ 可以确定正方形是否合法。

---

2.另一个 $O(n^5)$ 算法

• 可以枚举正方形的中心和半径， $O(n^2)$ 验证。
• 这样的方式有个比较特别的性质：它的部分数据可以重复利用。可以利用这一点优化。

---

3. $O(n^4)$ 算法

• 也是基于二的改进，我们仍然 $O(n^2)$ 枚举中心。
• 在枚举半径时，许多数据可以重复使用，如判断矩阵合法性，我们可以一层一层地判断，举个例子：比如一圈的最大值为4，肯定至少还得拓展3层：4，3，2，1，我把它称作“前瞻性判断”。

	int maxv=get_square_max(i,j,d);//找到了最大值。
	mind=max(mind,d+maxv-1);//看看第几层才能判断。

• 至于矩阵的和，更简单了，每次扫一遍，加上去即可。
• 因此，平均每次判断矩阵合法性复杂度变成了 $O(n^2)$ 。

其它与2无异。

---

4.另一个 $O(n^4)$ 算法

还是基于2的改进，我们看一看能不能通过预处理，使得判断一个矩阵变快。

方阵数值的和

考虑差分。

它是可以O(n²)预处理，O(1)求出的。
设c[i+1][j+1]为1~i行，1~j列的数的和。
预处理可以先算行的前缀和，再算列的前缀和。
i~k行，j~l列的数的和就是c[k][l]-c[k][j-1]-c[i-1][l]+c[i-1][j-1]。

四边形边框的最大值

本质上是一个区间的最大值，求每行每列的可以 $O(n^2\log_2{n})$ 预处理 $O(1)$ 求出。 考虑 ST 表。

这里可以设a[i][j][k]为第i行j~j+2^k-1列中数的最大值，
b[i][j][k]为第j行i~i+2^k-1列中数的最大值。
那么显然：
a[i][j][k]=max(a[i][j][k-1],a[i][j+(1<<(k-1))][k-1])
b[i][j][k]=max(b[i][j][k-1],b[i+(1<<(k-1))][j][k-1])
至于判断，由于有重复不会影响max值正确性，直接把两个大区间拼在一起。
类似这样：
inline int get_row_max(int i,int j,int k)
{
	int len=k-j+1;
	len=log2[len];
	return max(a[i][j][len],a[i][k+1-(1<<len)][len]);
}

因此， $O(n)$ 可以单纯判断一个矩阵是否合法。

和 2 的做法几乎一致，不再赘述。

---

5. $O(n^3)$ 算法

• 基于 4 和 5 的改进，我们仍然 $O(n^2)$ 枚举中心。
• 在枚举半径时，和4一样，许多数据还是可以重复使用，但这次，我们的优化使得矩阵合法性的复杂度降到了 $O(1)$ 。
• 估算了一下， 5×350 ³ =214375000 。确实会 TLE，但加 O2 优化就没事了。也就是说，对于题面的 n , m ≤ 100 它是一个完全可接受的算法。

程序

#include<fstream>
using namespace std;
const int MAXN=350,MAXLOG=10;
int T,n,m,v[MAXN][MAXN],a[MAXN][MAXN][MAXLOG];
int b[MAXN][MAXN][MAXLOG],log2[MAXN];
long long maxcost,c[MAXN][MAXN];
inline void input()
{
	scanf("%d%d%lld",&n,&m,&maxcost);
	for(int i=0;i<n;i++)
	for(int j=0;j<m;j++)
	{
		scanf("%d",&v[i][j]);
		a[i][j][0]=b[i][j][0]=c[i+1][j+1]=v[i][j];
	}
}
inline void prepare_sum()
{
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	c[i][j]+=c[i-1][j];
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	c[i][j]+=c[i][j-1];
}
inline void prepare_max()
{ 
	for(int k=1;k<=log2[n];k++)
	for(int i=0;i<n;i++)
	for(int j=0;j<m;j++)
	{
		//The second mistake
		//if(i+(1<<(k-1)|1)>=n)
		if(i+(1<<(k-1))>=n)
		b[i][j][k]=b[i-1][j][k];
		else
		b[i][j][k]=
		//The first mistake
		//max(b[i][j][k-1],b[i+(1<<(k-1)|1)][j][k-1])
		max(b[i][j][k-1],b[i+(1<<(k-1))][j][k-1]);
	} 
	for(int k=1;k<=log2[m];k++)
	for(int i=0;i<n;i++)
	for(int j=0;j<m;j++)
	{
		//The second mistake
		//if(j+(1<<(k-1)|1)>=n)
		//The third mistake
		//if(j+(1<<(k-1))>=n)
		if(j+(1<<(k-1))>=m)
		a[i][j][k]=a[i][j-1][k];
		else
		a[i][j][k]=
		//The first mistake
		//max(a[i][j][k-1],a[i][j+(1<<(k-1)|1)][k-1]);
		max(a[i][j][k-1],a[i][j+(1<<(k-1))][k-1]);
	}
}
inline long long get_sum(int i,int k,int j,int l)
{
	return c[k+1][l+1]-c[k+1][j]-c[i][l+1]+c[i][j];
}
inline int get_row_max(int i,int j,int k)
{
	int len=k-j+1;
	len=log2[len];
	return max(a[i][j][len],a[i][k+1-(1<<len)][len]);
}
inline int get_column_max(int j,int k,int i)
{
	int len=k-j+1;
	len=log2[len];
	return max(b[j][i][len],b[k+1-(1<<len)][i][len]);
}
inline int get_square_max(int x,int y,int d)
{
	return max(max(get_row_max(x-d,y-d,y+d),
	get_row_max(x+d,y-d,y+d)),
	max(get_column_max(x-d,x+d,y-d),
	get_column_max(x-d,x+d,y+d)));
}
inline bool ok(int x,int y,int d)
{
	return x-d>=0&&x+d<n&&y-d>=0&&y+d<m; 
}
inline void just_do_it()
{
	int ans=0;
	for(int i=0;i<n;i++)
	for(int j=0;j<m;j++)
	{
		long long alsum=0;
		int mind=0;//最小的d 
		for(int d=0;ok(i,j,d);d++)
		{
			alsum+=(d<<1|1)*(d<<1|1);
			//需要检查： i±d (j-d,j+d)
			//j±d (i-d,i+d) 
			int maxv=get_square_max(i,j,d);//事实上是方框 
			//然后这个值说明了什么？
			//maxv(d)，maxv-1(d+1)，...，1(d+maxv-1)
			//说明……还有maxv-1歩才行
//			printf("(%d %d)*%d %d\n",i+1,j+1,d,maxv);
			long long sm=get_sum(i-d,i+d,j-d,j+d);
//			printf("(%d %d)*%d %lld %lld\n",i+1,j+1,d,
//			alsum,sm);
			mind=max(mind,d+maxv-1);
			if(mind<=d&&alsum-sm<=maxcost)
			ans=max(ans,d+1);
		}
	}
	printf("%d\n",ans);
}
inline void solve()
{
	input();
	prepare_sum();
	prepare_max();
/*	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=m;j++)
		printf("%3lld ",c[i][j]);
		printf("\n");
	}
	printf("%d\n",get_sum(1,2,1,3));
	printf("%d\n",get_row_max(1,1,4));*/
	just_do_it();
}
int main()
{
	scanf("%d",&T);
	for(int i=2;i<=MAXN;i++)
	log2[i]=log2[i-1]+!(i&(i-1));
	while(T--)
	solve(); 
	return 0;
}

---