语言漩涡

thirtiseven 的博客

0%

PA2011 Plotter 分形

Posted on Edited on

题意

你有一台画图机，它是这么工作的：先从 (0,0) 到 (1,1) 画一条线，然后根据指令左转或右转，然后再画一条 长度的线段，然后再根据下一个指令转弯，直到所有指令都执行完毕。画一条线段的时间是 1 秒。

指令序列是一个 L 或者 R 组成的字符串。设指令序列 ，那么更多的指令序列 可以按如下规则生成出来：

把字符串用空格隔开，并在串前和串后也分别添加一个空格，然后依次用L和R轮流填满这些空格。

例如：

如下图所示：

Screen Shot 2021-07-25 at 5.25.33 PM

给出n和m，n代表当前执行的指令序列是 ，m 次询问，给出一个坐标，回答画图机经过这个坐标的次数和每次经过它的时间。

输入输出

第一行给n和m，接下来m行每行询问一个坐标x,y

对每次询问，输出一个k表示这个坐标被经过了多少次。

样例

1
2
3
4
5
6
7
8
4 3
-3 -1
1 1
-1 0

2 7 11
1 1 
0

做法

这个玩意儿，aka gragon curve，aka 龙形曲线，是个著名的分形结构。

分形，我这种不会数学的数学爱好者最爱的玩意儿，很好看。

首先，拿到这个题，第一感觉就是这个每段在棋盘上走一个对角线的方式让人非常难受，变换一下坐标，让它在棋盘上走直线。这么搞： 然后，我们觉得这个生成的规则让人看上去看不出什么规律。打个表看一下这个图长什么样子：

plotter

我们惊喜地发现，这个 看上去就是两个 旋转一下拼在一起，也就是说，递推式可以这么写： 其中， 的意思是先翻转然后取反，就是说 LLR 会变成 LRR。

感性证明一下两个递推式等价：考虑把随便一个拆开，分解成交替的一个形如LRLRLRLR的序列和一个，显然前面那个序列符合上面那个翻转再取反的性质，后面符合这个性质根据归纳法也是显然的。

求t时刻画图机的位置

既然我们发现这个图形可以这样递归地分成本质一样的两截，那么我们就能在的时间里求 t 时刻画图机的位置。具体是这么搞的：

首先，所有序列画出来的图像都是一个无限的龙形曲线的一部分，我们可以预处理出每个序列结束的时候画图机所处的位置。因为更大的龙形曲线是两个更小的龙形曲线拼出来的，所以很自然地： 然后，我们发现每条指令序列的长度是 , 所以第n个曲线，我们叫它 ，的长度是 ,所以就有一个递归的算法：如果 t 比 小，那它就属于 ，否则它就相当于在一个和 本质一样的曲线上走了 步，我们可以就当它是 来做，再从我们已经预处理出来的 出发，加上一个右转九十度的这个坐标。

把这个过程递归下去，就求出来了。

引导问题：皮亚诺曲线

那么反过来，给出坐标求经过这个坐标的时刻该怎么做呢？

先来看个引导问题：ACM-ICPC World Finals 2003 Riding the Bus

问题是：给个坐标，求从原点沿着皮亚诺曲线，aka希尔伯特第二曲线走到这个坐标的路程。皮亚诺曲线长下面这样，把9个p1这样连起来就是p2，以此类推。

皮亚诺曲线

这个题就是个搜索题。一个n阶的皮亚诺曲线的大小是 ，考虑 和 ，我们就可以得出这个坐标具体属于九块中的哪一块。如果它属于第 i 块，我们就可以把 加入答案，然后把 当作新的坐标，递归地在n-1阶的皮亚诺曲线里求解子问题即可。

剪枝搜索解决原问题

那么这个题的解法对我们解决原问题有什么帮助吗？好像没有什么帮助，因为我们不能确切地知道哪个点在哪一块，而且每个点可能在多个块里，如果强行递归下去那复杂度就会达到惊人的 ，然后就可以交一个“看起来差不多啊我怎么就超时了呢”的日常。但是实际上，当我们进入一个错误的分支后，我们的位置就会离问题的坐标越来越远，所以实际上可以剪掉很多错误的分支。所以我们先把这个递推方程列出来，再考虑怎么剪枝的事情。

假设 是一个返回到 需要的时间的集合，可以列出递推方程： 当n=1时： 这个递推方程的意思是，要么 在 里面，要么在 里面，那我们就在 里找 这个点，然后用 去减它，如果看懂了上上节，这里还是挺自然的。

好，考虑剪枝的问题。我们要剪枝的情况是：虽然在 里面找 ，但是 根本不在 的区域。一个理想的剪枝方法是判断这个坐标在不在 上。但是我们其实不太会做。一个比较经济的方法是给 区域做一个目标检测 画一个 bounding box，这样就能足以将时间复杂度剪到 . 这个 bounding box 可以通过递推预处理，见下： 然后，在进行上面那个递归的时候，如果 在这个 bounding box 外面，就可以果断地返回空集。

然后就做完了。时间复杂度是 ，至于为什么其实是有证明的，不细说了，大概就是证明在整个图中包含 (x,y) 的点只有常数个，因此每轮递推只有常数次函数调用没有被剪枝剪掉，好像挺有道理的。

代码

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using ll = long long;

ll n, m;
ll u, v;

ll xn[73], yn[73];
ll pow2[64];
ll r[73], t[73], l[73], b[73];

void preprocess() {
	xn[1] = 1;
	yn[1] = 1;
	pow2[0] = 1;
	pow2[1] = 2;
	r[1] = t[1] = 1;
	l[1] = b[1] = 0;
	for (ll i = 2; i <= 62; i++) {
		xn[i] = xn[i-1] - yn[i-1];
		yn[i] = xn[i-1] + yn[i-1];
		pow2[i] = pow2[i-1] * 2;
		r[i] = std::max(r[i-1], t[i-1] + xn[i]);
		t[i] = std::max(t[i-1], l[i-1] + yn[i]);
		l[i] = std::max(l[i-1], b[i-1] - xn[i]);
		b[i] = std::max(b[i-1], r[i-1] - yn[i]);
//		std::cerr << r[i] << ' '  << t[i] << ' '  << l[i] << ' ' << b[i] << '\n';
	}
}

std::set<ll> dfs(ll x, ll y, ll n) {
	std::set<ll> res;
	if (n == 1) {
		if (0 <= y && y <= x && x <= 1) {
			res.insert(x+y);
		}
		return res;
	}
	if (x < -l[n] || x > r[n] || y < -b[n] || y > t[n]) {
		return res;
	}
	auto st = dfs(x, y, n-1);
	for (auto it: st) {
		res.insert(it);
	}
	st.clear();
	st = dfs(yn[n]-y, x-xn[n], n-1);
	for (auto it: st) {
		res.insert(pow2[n] - it);
	}
	return res;
}

int main(int argc, char *argv[]) {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0); 
	preprocess();
	std::cin >> n >> m;
	n = std::min(n, 62ll);
	for (ll i = 0; i < m; i++) {
		std::cin >> u >> v;
		if ((std::abs(u) + std::abs(v)) % 2 == 1) {
			std::cout << "0\n";
			continue;
		}
		ll x = (u + v) / 2, y = (v - u) / 2;
		auto st = dfs(x, y, n);
		std::cout << st.size();
		for (auto it: st) {
			std::cout << ' ' << it;
		}
		std::cout << '\n';
	}
}

吐槽

两个半月没做题，对着题解敲出来就直接过了，这题解真不错。

网上能找到的一句话题解是吉老师写的，吉老师说：

还看到了cf上有关这个题的讨论。坦克工程师，我的偶像