Luogu P1228 地毯填补问题

难想的巧妙的分治题

  • 我都不记得写过什么分治题,好像并没写过什么。。。
  • 题目上给了k一定是2的幂次,先考虑为0的情况,很明显不需要填,k为1时,只需要在所在点的其余三个空格填补完成即可。

k=1

k=2

  • k=2时,可以在中间点放一个适应的地毯,分治到其他剩余3个k=1的方格中,右上的k=1的方格可以把公主位置当作左下角,左下角的k=1的方格把公主当作右上角的位置,右下角的k=1方格把公主位置当作左上角,如下图

k=2

k=2

  • k=3同理,如下图

k=3

k=3

  • 递归用分治解决即可。
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
#include<bits/stdc++.h>
using namespace std;

struct Solution{
void dfs(int x, int y, int a, int b, int len){
if(len == 1) return;
if(x-a<=len/2-1 && y-b<=len/2-1){
printf("%d %d 1\n", a + len / 2, b + len / 2);
dfs(x, y, a, b, len / 2);
dfs(a + len / 2 - 1, b + len / 2, a, b + len / 2, len / 2);
dfs(a + len / 2, b + len / 2 - 1, a + len / 2, b, len / 2);
dfs(a + len / 2, b + len / 2, a + len / 2, b + len / 2, len / 2);
}
else if(x-a<=len/2-1 && y-b>len/2-1){//x<a+l/2 && y-b<=l/2-1
printf("%d %d 2\n", a + len / 2, b + len / 2 - 1);
dfs(a + len / 2 - 1, b + len / 2 - 1, a, b, len / 2);
dfs(x, y, a, b + len / 2, len / 2);
dfs(a + len / 2, b + len / 2 - 1, a + len / 2, b, len / 2);
dfs(a + len / 2, b + len / 2, a + len / 2, b + len / 2, len / 2);
}
else if(x-a>len/2-1 && y-b<=len/2-1){
printf("%d %d 3\n", a + len / 2 - 1, b + len / 2);
dfs(a + len / 2 - 1, b + len / 2 - 1, a, b, len / 2);
dfs(a + len / 2 - 1, b + len / 2, a, b + len / 2, len / 2);
dfs(x, y, a + len / 2, b, len / 2);
dfs(a + len / 2, b + len / 2, a + len / 2, b + len / 2, len / 2);
}
else{
printf("%d %d 4\n", a + len / 2 - 1, b + len / 2 - 1);
dfs(a + len / 2 - 1, b + len / 2 - 1, a, b, len / 2);
dfs(a + len / 2 - 1, b + len / 2, a, b + len / 2, len / 2);
dfs(a + len / 2, b + len / 2 - 1, a + len / 2, b, len / 2);
dfs(x, y, a + len / 2, b + len / 2, len / 2);
}
}

void Solve(){
int n, x, y;
scanf("%d%d%d", &n, &x, &y);
dfs(x, y, 1, 1, 1 << n);
}
};

int main(){
Solution().Solve();
return 0;
}
# 分治

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×