自动搬运

查看原文

来自洛谷，原作者为

	him的自我修养 尽力了

搬运于2025-08-24 22:41:52，当前版本为作者最后更新于2023-08-01 11:18:19，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意

求从 $x,y$ 到 $x1,y1$ 的皮亚诺距离

扯淡

地狱绘图。

思路

感觉可以用递归求解。函数 $f(a,x,y)$ 表示 $k$ 阶皮亚诺曲线下从 $0,0$ 到 $x,y$ 的距离。而 $ans=f(k,x,y)-f(k,x1,y1)$ 再输出求可以啦！

而 $f(a,x,y)$ 的递归形式如下 $f(a,x,y)=f(1,\frac{x}{k},\frac{y}{k})\times(3^{k})^{2}+f(a-1,x1,y1)$。 其中 $f(1,\frac{x}{k},\frac{y}{k})$。表示一阶皮亚诺曲线的距离，$p=3^{a-1}$。

而 $(3^{a-1})^{2}$ 表示把 $k$ 阶皮亚诺曲线分成一阶的皮亚诺曲线，就是总距离。

最后的 $f(a-1,x1,y1)$ 表示把 $k$ 阶皮亚诺曲线里的 $x,y$ 映射到 $k-1$ 阶皮亚诺曲线里，变成 $x1,y1$。

代码

我就知道你们只喜欢这里。

#include <iostream>
using namespace std;
typedef long long ll;
ll k;
ll p[45];
ll x1,y1,x2,y2;
ll pin[3][3]={
	{0,1,2},
	{5,4,3},
	{6,7,8},
};
ll len(ll p,ll &x,ll &y){
	ll ix=x/p,iy=y/p;
    x=x%p;
	y=y%p;
    if(ix==1) y=p-1-y;
    if(iy==1) x=p-1-x;
    return pin[ix][iy];
}
ll f(ll k,ll x,ll y){
	if(k==1) return pin[x][y];
	else return p[k-1]*p[k-1]*len(p[k-1],x,y)+f(k-1,x,y);
}
int main(){
	cin >>k;
	cin >>x1>>y1;
	cin >>x2>>y2;
	k=min(k,39ll);
	p[0]=1;
	for(int i=1;i<=39;i++) p[i]=p[i-1]*3;
	ll ans=f(k,x1,y1)-f(k,x2,y2);
	cout <<abs(ans);
	return 0;
}

管理大大求通过qwq