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

· · 题解

题解区都是用递归（分治）法做的，这里我来讲一个非递归的做法，简单易懂，代码好写，格式化后加上注释仅 47 行。

分析

求两点间的距离（对本蒟蒻来说）并不简单，但求出曲线起点到一个点的距离稍微容易一些，所以我们参照前缀和的思想，只要求出两点分别到起点距离的差就好了。

我们考虑将曲线上每个点到起点的距离都求出来，画在一个表格里，对于 k=1，它应该是这样的：

这个表格我们称之为基础纹理，至于为什么，请继续往下读。

我们再来看 k=2 的情况（颜色略有不同，不影响，懒得改了）：

如果你把每个数都模 9：

就会发现，这九宫格里的每一宫（指粗线框出的 3\times3 正方形区域）和基础纹理都有点像——也就是说可以由基础纹理进行一定翻转得来。

而这张表与上一张表的差值：

还是基础纹理，只不过放大了 3 倍，同时数值乘以 9。

于是我们猜想：任意一阶的曲线都可以由若干层经过一定变换的基础纹理的和表示。

经过一定的观察（3 阶曲线这里就不画了累死我了），我们还可以发现规律：

知道了这些，代码就很好写了，当成大模拟就好了。

实现

Talk is cheap, show me the code!

#include <iostream>

using namespace std;

typedef long long ll;

int k;
ll x1, y1, x2, y2;

// 基础纹理，注意方向
const ll BASIC_TEXTURE[8][8] = {
    {0, 1, 2},
    {5, 4, 3},
    {6, 7, 8},
};

// 求 k 阶曲线上坐标为 (x, y) 的点到曲线起点的距离
ll distance(int k, ll x, ll y) {
  ll res = 0;
  // 共需叠加 k 层纹理
  for (ll i = 0, p = 1; i < k; i++, p *= 3) {
    // 纹理坐标
    ll tex_x = x / p % 3;
    ll tex_y = y / p % 3;
    // 所在九宫格坐标
    ll box_x = x / p / 3;
    ll box_y = y / p / 3;
    // 进行翻转
    if (box_x & 1)
      tex_y = 2 - tex_y;
    if (box_y & 1)
      tex_x = 2 - tex_x;
    // 叠加纹理
    res += p * p * BASIC_TEXTURE[tex_x][tex_y];
  }
  return res;
}

int main() {
  cin >> k;
  cin >> x1 >> y1;
  cin >> x2 >> y2;
  // 题目没有限定两个点谁在前谁在后，所以距离差要取绝对值
  cout << abs(distance(k, x1, y1) - distance(k, x2, y2));
  return 0;
}

后记

调这个还是挺崩溃的，找了半天最后发现没开 long long。

其实这个想法借鉴了一点计算机图形学的思路。