题解

him的自我修养 · 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