P8730 [蓝桥杯 2020 国 ABC] 皮亚诺曲线距离
Alvin20100228
·
·
题解
题意
两个点之间, 如果沿着皮亚诺曲线走, 距离是多少?
思路
考虑递归求解
我们把每个 n 阶的图看成九个 n-1 阶的图。
根据 n 阶的和 n-1 阶的 (x,y) 之间的关系来逐层降阶。
对于 k 阶皮亚诺曲线点 a(k,x,y) 的距离表示为
其中
$a(1,\frac{x}{p},\frac{y}{p})$ 表示 $1$ 阶皮亚诺曲线距离，$p=3^{k-1}$。
$(3^p)^2$ 表示将整个 $k$ 阶皮亚诺曲线划分为 $1$ 阶皮亚诺曲线，$1$ 单元格内的总数,即总距离。
$a(k-1,xx,yy)$ 表示 $k$ 阶 $(xx,yy)$ 映射到 $k-1$ 阶的坐标, 为不完整单元格在 $k-1$ 阶到 $(xx,yy)$ 的距离。其划分规则为
```cpp
if(x/p==1) yy=p-1-y;
if(y/p==1) xx=p-1-x;
```
接下来，我们可以递归写出代码。
### 代码
```cpp
#include <iostream>
using namespace std;
long long pw[200],leng[3][3] = {{0, 1, 2}, {5, 4, 3}, {6, 7, 8}};//3的i次幂和1阶皮亚诺曲线的距离矩阵
long long len(long long p,long long &x,long long &y)//计算距离，变换x,y
{
long long ix=x/p,iy=y/p;
x%=p;
y%=p;
if(ix == 1) y=p-1-y;
if(iy == 1) x=p-1-x;
return leng[ix][iy];
}
long long a(long long k,long long x,long long y)//k阶皮亚诺曲线点(0, 0)到点(x, y)的距离
{
if(k==1) return leng[x][y];
else return pw[k-1]*pw[k-1]*len(pw[k-1],x,y)+a(k-1,x,y);
}
int main()
{
long long k,xx,yy,xxx,yyy;
cin>>k>>xx>>yy>>xxx>>yyy;
if(k>=40)k=39;//k>40无效且爆long long
pw[0]=1;
for (int i=1;i<=39;i++) pw[i] = pw[i - 1] * 3;
long long ans=a(k,xx,yy)-a(k,xxx,yyy);
cout<<(ans>0?ans:-ans)<<endl;//特判 ans<0
return 0;
}
```