Topcoder 12550 FoxAndAvatar

TC 12550

---

一开始看到题目的时候，觉得每次操作的矩形都得贴着目标位置，但是这个贪心是不对的。

反例：\(n=47,w=6,x=24\)，看上去需要 \(4\) 步，其实可以三步完成：

显然剩下的部分可以一步完成。

但是我们并非回到起点——可以发现，如果每次操作的矩形都贴着目标位置，\(4\) 次一定可以完成，也就是说，答案的上界为 \(4\)。

可以考虑去进行搜索。用 \((a,b)\) 表示当前状态：在 \(x\) 前有 \(a\) 个格子，\(x\) 后有 \(b\) 个。

每次枚举一个矩形并删除，有三种情况：这个矩形只包含在 \(x\) 前的位置；只包含在 \(x\) 后的；同时包含两种。

对于第一种和第二种情况，显然我们只关心删除的矩形的面积（而不是位置），可以直接 \(\mathcal O(n)\) 地枚举，但是对于最后一种情况，看似需要枚举 \(\mathcal O(n^2)\) 的内容，因为此时得确定一整个矩形，需要枚举左上角和右下角。

这时候需要一些研究，可以发现，如果能确定本次删除在 \(x\) 前删除的格子个数的话，那么在 \(x\) 后删除的格子的个数应该越多越好。

那么就可以枚举左上角，这样就能确定要删除多少个在 \(x\) 之前的格子，进而通过讨论 \(\mathcal O(1)\) 地算出在 \(x\) 后删除的格子的个数。

整个过程可以用深搜实现：先 \(\mathcal O(1)\) 判断是否可以直接放一个矩形后结束，如果不行，再 \(\mathcal O(n)\) 地枚举下一个矩形在哪里。但这样似乎是 \(\mathcal O(n^3)\) 的，因为最多要枚举 \(3\) 次。

不过我们可以发现，如果给定的图形无法在 \(3\) 次操作内结束，答案就必然是 \(4\)，因此只需要判断 \(0,1,2,3\)，那么最多就只要枚举 \(2\) 次了。

时间复杂度：\(\Theta(n^2)\)。

我觉得最后的这个技巧貌似还挺常见的。。。也令人眼前一亮。

参考代码：

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define int long long
#define elif else if
#define ALL(x) x.begin(),x.end()
#define lowbit(x) (x&(-x))
using namespace std;
int w;
bool dfs(int x,int y,int op)
{
	if(!op)
		return (!x)&&(!y);
	if(op==1)
	{
		if(x==0&&y<w)
			return 1;
		if((!y)&&(x<w||x%w==0))
			return 1;
		if(w==1&&x==0)
			return 1;
		if(x==w-1&&y<=x)
			return 1;
		return 0;
	}
	int L=min(y,(w-(x+1)%w)%w);
	int R=y>L?(x+y+1)%w:0;
	if(dfs(x,(y-R)%w,op-1))
		return 1;
	for(int i=1;i<=x/w;i++)
		for(int l=1;l<=w;l++)
			if(dfs(x-i*l,y,op-1))
				return 1;
	for(int i=0;i<=x/w+1;i++)
		for(int l=1;l<=x%w;l++)
			if(dfs(x-i*l,y-(y-L-R)/w*l-min(R,l),op-1))
				return 1;
	for(int i=0;i<=x/w;i++)
		for(int l=1;l<=w-x%w-1;l++)
			if(dfs(x-i*l,y-y/w*l-min(l,y%w),op-1))
				return 1;
	return 0;
}
class FoxAndAvatar
{
public:
	int minimalSteps(int n,int _w,int x)
	{
		w=_w;
		for(int i=0;i<=3;i++)
			if(dfs(x-1,n-x,i))
				return i;
		return 4;
	}
}sol;
#undef int

---

后记：我一开始写的时候可能有点晕，导致我写错了很多地方（包括我把 \(x\) 和 \(y\) 完全搞反了）但是居然能 AC。。。我在写这篇题解的时候才发现问题，但是随手造了一点数据（包括上面提到的那个），都是对的。（虽然中间过程是错的😔）