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)\)

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

参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#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。。。我在写这篇题解的时候才发现问题,但是随手造了一点数据(包括上面提到的那个),都是对的。(虽然中间过程是错的😔)


Topcoder 12550 FoxAndAvatar
https://shmilyty.cf/tc12550/
作者
ShmilyTY
发布于
2022年10月2日
许可协议