P8730 [蓝桥杯 2020 国 ABC] 皮亚诺曲线距离 题解

· · 题解

简要题意

求两点之间的皮亚诺曲线距离。

思路

将该矩形分为 9 个部分，如图所示，用红色方框按顺序框出了就各部分，蓝框是每个部分的起点：

记 (0, 0) 到 (x, y) 的距离在 k 阶时为 dis(k, x, y)。

可以发现 (x_1, y_1) 到 (x_2, y_2) 的距离等于 |dis(k, x_1, y_1) - dis(k, x_2, y_2)| 于是可以考虑计算两个距离然后得出答案。

首先记此时矩形的边长 len = 3^k 和走完其中一个部分所需的步数 step = \frac{3^{2\times k}}{9} = 2^{2\times k - 2}。

在这里明确一个问题：因为皮亚诺曲线距离是以左下角为起点，右上角为终点的，所以我们在计算每一个部分的时候要把蓝框放到左下角，每次计算的时候都要把原先的 (x, y) 改变成以当前部分的起点为参考系的坐标。

接下来分类讨论：

  1. - $\texttt{if }y < \frac{len}{3}$：说明在第 $1$ 个部分，起点是 $(0, 0)$，以第 $1$ 部分起点为参考系计算 $dis(k-1, x, y)$。 - $\texttt{else if }y < \frac{2len}{3}$：说明在第 $2$ 个部分，起点为 $(\frac{len}{3}-1, \frac{len}{3})$，以第 $2$ 部分起点为参考系，再加上第 $1$ 部分走的距离计算 $step + dis(k-1, \frac{len}{3}-1-x, y-\frac{len}{3})$。 - $\texttt{else}$：说明在第 $3$ 部分，起点为 $(0, \frac{2len}{3})$ 计算 $2 \times step + dis(k - 1, x, y - \frac{2len}{3})$。
  2. - $\texttt{if }y < \frac{len}{3}$：说明在第 $6$ 个部分，起点是 $(\frac{len}{3}, \frac{len}{3}-1)$，计算 $5 \times step + dis(k-1, x-\frac{len}{3}, \frac{len}{3}-1-y)$。 - $\texttt{else if }y < \frac{2len}{3}$：说明在第 $5$ 个部分，起点为 $(\frac{2len}{3}-1, \frac{2len}{3}-1)$，计算 $4\times step + dis(k-1, \frac{2len}{3}-1-x, \frac{2len}{3}-1-y)$。 - $\texttt{else}$：说明在第 $4$ 部分，起点为 $(\frac{len}{3}, len-1)$ 计算 $3 \times step + dis(k - 1, x-\frac{len}{3}, len-1-y)$。
  3. - $\texttt{if }y < \frac{len}{3}$：说明在第 $7$ 个部分，起点是 $(\frac{2len}{3}, 0)$，计算 $6\times dis(k-1, x-\frac{2len}{3}, y)$。 - $\texttt{else if }y < \frac{2len}{3}$：说明在第 $8$ 个部分，起点为 $(len-1, \frac{len}{3})$，计算 $7\times step + dis(k-1, len-1-x, y-\frac{len}{3})$。 - $\texttt{else}$：说明在第 $9$ 部分，起点为 $(\frac{len}{3}, len-1)$ 计算 $8 \times step + dis(k - 1, x-\frac{2len}{3}, y - \frac{2len}{3})$。

代码

注意在 k > 40 时会爆 long long，注意特判一下。

#include <bits/stdc++.h>
#define ll long long
#define setp setprecision
#define mem(a, m) memset(a, m, sizeof(a));
using namespace std;

ll k;
ll x1, Y1, x2, y2;
ll qpow(ll a, ll b)
{
    if(!b)  return 1;
    ll t=qpow(a, b/2);
    if(b%2 == 0)    return t * t;
    else    return t * t * a;
}
ll dis(ll k, ll x, ll y)
{
    if(k == 0)  return 1;
    ll step = qpow(3, 2 * k - 2);
    ll len = qpow(3, k);
    if(x < len / 3)
    {
        if(y < len / 3) return dis(k - 1, x, y);//区域一 
        else if(y < len * 2 / 3)    return step + dis(k - 1, len / 3 - 1 - x, y - len / 3);//区域二
        return 2 * step + dis(k - 1, x, y - len * 2 / 3);//区域三 
    }
    else if(x < len * 2 / 3)
    {
        if(y < len / 3) return 5 * step + dis(k - 1, x - len / 3, len / 3 - 1 - y);//区域六 
        else if(y < len * 2 / 3)    return 4 * step + dis(k - 1, len * 2 / 3 - 1 - x, len * 2 / 3 - 1 - y);//区域五 
        return 3 * step + dis(k - 1, x - len / 3, len - 1 - y);//区域四 
    }
    else
    {
        if(y < len / 3) return 6 * step + dis(k - 1, x - len * 2 / 3, y);//区域七 
        else if(y < len * 2 / 3)    return 7 * step + dis(k - 1, len - 1 - x, y - len / 3);//区域八 
        return 8 * step + dis(k - 1, x - len * 2 / 3, y - len * 2 / 3);//区域九 
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> k >> x1 >> Y1 >> x2 >> y2;
    if(k >= 40) k = 39;
    cout << abs(dis(k, x1, Y1) - dis(k, x2, y2));
    return 0;
}