2020年第十一届蓝桥杯国赛—c++B组—试题F：皮亚诺曲线距离

这道题我写了一个多小时，还是自己太菜了，两个样例都过了，三阶皮亚诺随便取了两个点，距离也是正确的，如果有大佬找到了我的问题，欢迎指正

以下是我的思路

<>思路

总体就是求出两个点到原点的距离，然后相减即可

那么具体如何求呢，可以发现，当 k > 1 k > 1 k>1 的时候，皮亚努曲线图都可以分解为 3 × 3 3 × 3 3×3 的 k − 1 k
- 1k−1 阶皮亚诺曲线块

那么假设当前是第 k i k_i ki​ 阶，那么我们可以求出经过了多少个 k i − 1 k_i - 1 ki​−1 阶块走到了当前坐标所在的 k
i − 1 k_i - 1ki​−1 阶块

只要求出了走过了几个块，那么因为每一个块中距离都是 ( k i − 1 ) ( k i − 1 ) (k_i - 1)(k_i - 1) (ki​−1)(k
i​−1) 个， 就能求出在当前块之前已经走过了多少个块

然后再递归 k i − 1 k_i - 1 ki​−1 阶的情况

直到 k = = 1 k == 1 k==1 时，就划归为了一阶皮亚诺曲线到出发点的距离

因为一阶皮亚诺曲线根据进出方向和矩阵方向，有四种不同的情况，经过分析其实可以写一个坐标的变化，将其都变换为某一种情况求解即可

<>代码
#include <iostream> #include <cmath> using namespace std; typedef long long LL;
int k; int x1, y1; int x2, y2; // 一阶皮亚诺距离函数 int get_k1(int x,int y) { int dis =
0; if(x == 0) dis = y; if(x == 1) dis = 3 + (2 - y); if(x == 2) dis = 6 + y;
return dis; } // 确定其前面几个 k 块 int get_block(int x, int y, int &d) { int sum = 0;
if(x == 0 && y == 0) { d = 0; sum = 0; } if(x == 0 && y == 1) { d = 1; sum = 1;
} if(x == 0 && y == 2) { d = 0; sum = 2; } if(x == 1 && y == 2){ d = 2; sum = 3;
} if(x == 1 && y == 1) { d = 3; sum = 4; } if(x == 1 && y == 0) { d = 2; sum = 5
; } if(x == 2 && y == 0) { d = 0; sum = 6; } if(x == 2 && y == 1) { d = 1; sum =
7; } if(x == 2 && y == 2) { d = 0; sum = 8; } return sum; } // 坐标转换. d
是用来确定哪一种情况，详细值参照题目图 void trans(LL &x, LL &y,int d) { if(d == 0) return; if(d ==
1) { x = 2 - x; return; } if(d == 2) { y = 2 - y; return; } if(d == 3) { x = 2 -
x; y = 2 - y; return; } } // 递归求解 LL get(LL x, LL y, int k,int d) { LL sum = 0;
if(k == 1) { trans(x,y,d); sum += get_k1(x,y); return sum; } LL sub = pow(3,k -
1); int tx = x / sub, ty = y / sub; int blocks = get_block(tx,ty,d); sum =
blocks* sub * sub; sum += get(x % sub,y % sub,k - 1,d); return sum; } int main()
{ cin >> k; cin >> x1 >> y1; cin >> x2 >> y2; get(x1,y1,k,0); cout << abs(get(x1
,y1,k,0) - get(x2,y2,k,0)) << endl; return 0; } /* 2 3 4 0 0 */

• « 上一篇：理解闭包
• » 下一篇：Browserslist: caniuse-lite is outdated. Please run: npx ....