自动搬运

查看原文

来自洛谷，原作者为

	OIforJoy ...

搬运于2025-08-24 22:19:51，当前版本为作者最后更新于2024-05-20 20:23:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题解

我们首先考虑朴素的搜索算法：考虑最后一块的所有可能位置，并进行递推搜索。对于给定的 $m,n$（不妨设$n\geq m$），最后一块的占领方式需要使得地区的长边与短边之一与整个轮廓的长边和短边之一重合。这样的实际情况有 $3$ 种（地区的短边不会贴轮廓的长边）。而这 $3$ 种情况实际本质上至多发生两种，因为以下两种情况如果可能同时发生那么就会是等价的：

1. 地区的短边贴轮廓的短边（$n\geq 2m$）；
2. 地区的长边贴轮廓的长边（$n\leq 2m$）。

但是这种朴素的办法在 $n,m$ 具有数量级的差距的时候十分低效。对于这种情况，我们期待能够获得一个类似在计算 $\gcd$ 时将辗转相减优化为辗转相除的办法。这种办法确实存在。

在 $m$ 为奇数时，这更为简单一些。此时最后一个地区的位置本质上是唯一的，我们可以写出状态转移方程

$$\operatorname{maxans}[n][m]=\operatorname{maxans}[n-2m][m]+1,n\geq 2m. $$

并且可以迭代得出

$$\operatorname{maxans}[n][m]=\operatorname{maxans}[n-2m\cdot\lfloor\frac{n}{2m}\rfloor][m]+\lfloor\frac{n}{2m}\rfloor. $$

对于 $\operatorname{minans}$，方程是一样的。

$m$ 为偶数时困难一点。首先我们有类似的式子

$$\operatorname{maxans}[n][m]=\operatorname{maxans}[n-(0.5m)\cdot\lfloor\frac{n}{0.5m}-3\rfloor][m]+\lfloor\frac{n}{0.5m}-3\rfloor. $$

因为这里贪心的策略是直接适用的。

但对于 $\operatorname{minans}$，情况很不一样。仍然正确的是，在迭代到 $n<2m$ 的状态之前都只能贴着短边划分区域。我们称区域长边长为 $m$ 的区域为不稳定的，反之称为稳定的。那么在区域最少的可能性中，不稳定的区域最多有 $3$ 个，因为如果至少有 $4$ 个，就可以适当改变填法使得不稳定的区域减少 $4$ 个而稳定的区域增加 $1$ 个。因此在 $n\geq 4m$ 时

$$\operatorname{minans}[n][m]=\operatorname{minans}[n-2m][m]+1 $$

依然成立，因为这个时候保证至少能够存在$1$个稳定的区域。在 $2m\leq n<4m$ 时要么划分一个稳定的区域，要么一直划分不稳定的区域直到得到长边短于短边的两倍的情况。（注：我给的代码中此处的具体实现有一定不同）这样，我们就完成了状态转移。

到目前为止的算法经实测可以通过前两个 Subtask。为了完整解决题目，注意到规模比较小的状态有可能被重复搜索多次，对小的状态采取记忆化搜索的策略即可。完整代码如下。

复杂度的计算较为困难，而验证程序效率的大数据易于获得，并且以下代码耗时基本上不超过时限的 $30\%$，所以此处不再进行分析。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#define N 3000
using namespace std;
int smin[N][N]={0},smax[N][N]={0};
int solvemin(int n,int m)
{
	if(n==0||m==0)return 0;
	if(n<m)swap(n,m);
	if(n<N&&m<N&&smin[n][m]<800000000)return smin[n][m];
	int res=1000000000;
	if(n==2*m||m==2*n)return 1;
	if(n>=2*m)
	{
		if(m%2==1)res=solvemin(n-(n/(2*m))*2*m,m)+n/(2*m);
		if(m%2==0)
		{
			int l=(n-(n/(2*m)-1)*2*m)/(m/2)-3;
			res=min(res,solvemin(n-(n/(2*m)-1)*2*m-l*(m/2),m)+(n/(2*m)-1+l));
			res=min(res,solvemin(n-(n/(2*m))*2*m,m)+(n/(2*m)));
		}
		if(n<N&&m<N)smin[n][m]=res;
		return res;
	}
	if(m%2==0)res=min(res,1+solvemin(n-m/2,m));
	if(n%2==0)res=min(res,1+solvemin(n,m-n/2));
	if(n<N&&m<N)smin[n][m]=res;
	return res;
}
int solvemax(int n,int m)
{
	if(n==0||m==0)return 0;
	int res=-1000000000;
	if(n<m)swap(n,m);
	if(n<N&&m<N&&smax[n][m]>=0)return smax[n][m];
	if(n>=2*m)
	{
		if(m%2==1)
		{
			int t=n/(2*m);
			res=solvemax(n-t*2*m,m)+t;
		}
		if(m%2==0)
		{
			int t=n/(m/2)-3;
			res=solvemax(n-t*(m/2),m)+t;
		}
		if(n<N&&m<N)smax[n][m]=res;
		return res;
	}
	if(m%2==0)res=max(res,solvemax(n-m/2,m)+1);
	if(n%2==0)res=max(res,solvemax(n,m-n/2)+1);
	if(n<N&&m<N)smax[n][m]=res;
	return res;
}
int main()
{
	for(int i=0;i<N;i++)for(int j=0;j<N;j++)smin[i][j]=1000000000,smax[i][j]=-1000000000;
	int n,m;
	cin>>n>>m;
	cout<<solvemin(n,m)<<' '<<solvemax(n,m);
	return 0;
}