C++蓝桥杯皮亚诺曲线距离求解

一、题目概述

给定指定阶数的皮亚诺曲线，以及曲线上的两个点的坐标，求解两个点之间的距离，曲线起点坐标规定为（0,0）。

一阶皮亚诺曲线如下图：

k+1阶的皮亚诺曲线是在k阶曲线的基础上，每一个格子由一阶曲线代替而生成。例如二阶曲线如下图：

三阶曲线如下图：

k阶曲线的边长为3的k次幂，格子总数为3的2k次幂。无论k取何值，曲线的起点总为左下角，坐标为（0,0），终点为右上角，坐标为（3的2k次幂-1,3的2k次幂-1）。

二、解题分析

2.1解题思路

经过初步分析：

1. 如果直接求解两点间的距离，那么需要求解任意两点间的详细路径，难度很大；
2. 可以将求两点间距离转换为求出到原点的距离然后相减；
3. k+1阶曲线是在1阶曲线的基础上层层细化网格而成，那么任意一点到原点的距离也可以先从宏观处入手，层层细化求解。

一阶曲线按照从起点到终点的行走顺序对网格进行划分，那么可分为1~9个区域，如下图所示：

任意k阶曲线都可以划分为上图所示的9个区域，例如二阶曲线划分如下图：

假设k阶曲线上的任意一点，该点到原点的距离=该点到所在区域起点的距离+本区域之前的区域网格数累加和，而该点到所在区域起点的距离又可以转换为以所在区域起点为原点的求解到原点距离的问题，因此可以层层递归求解。

根据上述解题思路，细化解题步骤如下：

1. 首先判断出k阶曲线上任意一点（x，y）所在区域，每个区域的边长为3的k-1次幂，因此可以通过对比大小得出判断；
2. 点到所在区域起点的距离如果要转换为以所在区域起点为原点的点到该原点的距离，就要将区域的起点映射为区域1的起点，即原点，该映射不仅仅是平移，可能还要旋转；
3. 以二阶曲线为例，区域2的起点转换为区域1的起点。区域2的起点坐标为（2,3），如果要转换到（0,0），那么就需要进行映射（2-x，y-3），（x，y）为区域2内的点，2-x说明区域2进行了X轴方向的翻转；
4. 本区域之前的区域网格数累加计算较为简单，每个区域的网格数为3的2k-2次幂，例如区域5之前的区域网格数累加，就等于4×3的2k-2次幂。

解题步骤大致如上，读者对皮亚诺曲线随阶数的增加而在形状上层层裂变的过程有一个形象的想象过程，有助于理解解题步骤。

2.2k值范围限制

由于题目中说明k值范围为1~100，而点的坐标的范围为不超过10的18次方，显然3的100次幂超过了10的18次方，同时也超过了C++中long long类型可表示的范围，因此不能直接将k值代入进行求解，而是要先判断出在10的18次方范围内的最大k值，判断代码如下：

void test_k()
{int k=0;long long p1;while(true){p1=pow(3, k);if(p1>=1e18)break;k++;}cout<<k<<endl;cout<<p1<<endl;
}

得出k值最大为38。

三、实现代码

代码使用C++实现，如下：

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;int k;
long long x11,y11,x12,y12;long long func01(long long x, long long y, int k)
{if(k == 0) return 0;long long tmp=pow(3, k-1);if(x < tmp && y < tmp) return func01(x, y, k-1);//region1 if(x < tmp && (y >= tmp && y < tmp*2)) return tmp*tmp + func01(tmp-1-x, y-tmp, k-1);//region2if(x < tmp && (y >= tmp*2 && y < tmp*3)) return 2*tmp*tmp + func01(x, y-tmp*2, k-1);//region3if((x >= tmp && x < tmp*2) && y < tmp) return 5*tmp*tmp + func01(x-tmp, tmp-1-y, k-1);//region6if((x >= tmp && x < tmp*2) && (y >= tmp && y < tmp*2)) return 4*tmp*tmp + func01(tmp*2-1-x, tmp*2-1-y, k-1);//region5if((x >= tmp && x < tmp*2) && (y >= tmp*2 && y < tmp*3)) return 3*tmp*tmp + func01(x-tmp, tmp*3-1-y, k-1);//region4if((x >= tmp*2 && x < tmp*3) && y < tmp) return 6*tmp*tmp + func01(x-tmp*2, y, k-1);//region7if((x >= tmp*2 && x < tmp*3) && (y >= tmp && y < tmp*2)) return 7*tmp*tmp + func01(tmp*3-1-x, y-tmp, k-1);//region8if((x >= tmp*2 && x < tmp*3) && (y >= tmp*2 && y < tmp*3)) return 8*tmp*tmp + func01(x-tmp*2, y-tmp*2, k-1);//region9return -1;
}int main()
{cin>>k;cin>>x11>>y11;cin>>x12>>y12;if(k > 38) k=38;cout<<abs(func01(x11,y11,k)-func01(x12,y12,k))<<endl;return 0;
}

此题代码并不长，关键在于解题思路。

四、代码测试

4.1蓝桥杯测试平台

为测试代码正确性，可以在蓝桥杯的刷题平台提交代码，网址为https://www.lanqiao.cn/problems/?first_category_id=1。

皮亚诺曲线距离题目编号为141，如下图所示：

4.2直接传入原始输入的k值

在蓝桥杯解题平台对代码进行测试，当将k值直接传入递归函数时，可以得到90%的分数，显示10个测试实例中有一个答案错误，如下图所示：

在本地运行代码，发现确实是因为3的100次方超出了long long类型的范围，导致错误输出。

4.3限制k值大小

对k值大小进行限制，采用了本文第三节中给出的代码，在蓝桥杯平台提交，结果依然显示10个测试实例中有一个答案错误，后将该错误实例的输入数据与输出数据下载到本地，测试数据如下：

k	x11	x12	y11	y12
100	972800214282722763	781912860110024270	972800214336621164	781912860202693276

正确输出应为191503939959914635。
在本地运行程序，得到的输出为191503939959943987，确实与答案不一致，经过一番检查后发现，是由于pow函数导致的答案错误。

4.4pow函数求整数高次幂存在误差

分别使用pow函数求3的k次幂与连续乘积计算3的k次幂测试结果的一致性，代码如下：

void test_pow()
{int k=1;long long p1,p2=1;while(true){p1=pow(3, k);p2*=3;if(p1>=1e18)break;k++;cout<<p1<<','<<p2<<endl;}cout<<k<<endl;cout<<p1<<endl;
}

输出如下图：

从输出结果分析，当k≥35时，两种方法计算出的3的k次幂出现了不同，且差异会越来越大。通过查找资料得知：pow函数返回的是double类型，在被强制转换为整型时会出现误差。

4.5满分代码

因此代码中不再使用pow函数，而是通过连续乘积计算幂，最终代码如下：

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;int k;
long long p[100];
long long x11,y11,x12,y12;long long func01(long long x, long long y, int k)
{if(k == 0) return 0;//long long tmp=pow(3, k-1);long long tmp=p[k-1];if(x < tmp && y < tmp) return func01(x, y, k-1);//region1 if(x < tmp && (y >= tmp && y < tmp*2)) return tmp*tmp + func01(tmp-1-x, y-tmp, k-1);//region2if(x < tmp && (y >= tmp*2 && y < tmp*3)) return 2*tmp*tmp + func01(x, y-tmp*2, k-1);//region3if((x >= tmp && x < tmp*2) && y < tmp) return 5*tmp*tmp + func01(x-tmp, tmp-1-y, k-1);//region6if((x >= tmp && x < tmp*2) && (y >= tmp && y < tmp*2)) return 4*tmp*tmp + func01(tmp*2-1-x, tmp*2-1-y, k-1);//region5if((x >= tmp && x < tmp*2) && (y >= tmp*2 && y < tmp*3)) return 3*tmp*tmp + func01(x-tmp, tmp*3-1-y, k-1);//region4if((x >= tmp*2 && x < tmp*3) && y < tmp) return 6*tmp*tmp + func01(x-tmp*2, y, k-1);//region7if((x >= tmp*2 && x < tmp*3) && (y >= tmp && y < tmp*2)) return 7*tmp*tmp + func01(tmp*3-1-x, y-tmp, k-1);//region8if((x >= tmp*2 && x < tmp*3) && (y >= tmp*2 && y < tmp*3)) return 8*tmp*tmp + func01(x-tmp*2, y-tmp*2, k-1);//region9return -1;
}int main()
{cin>>k;cin>>x11>>y11;cin>>x12>>y12;if(k > 38) k=38;p[0]=1;for(int i = 1; i <= k; i++) p[i]=p[i-1]*3;cout<<abs(func01(x11,y11,k)-func01(x12,y12,k))<<endl;return 0;
}

上述代码提交后，全部10个用例全部跑通。

附录

error: ‘long long int y1’ redeclared as different kind of symbol报错

初始编写上述代码时，第一个点的坐标变量本来定义为x1，y1，代码在本地Dev-C++编译器上能够正确运行，但是在蓝桥杯解题平台上运行就报出该错误，后经查找资料后发现，cmath头文件中定义了与y1同名的函数，所以导致报错，因此上述代码中的变量名改为x11,y11,x12,y12。

C++中int类型与long long类型取值范围

类型	专用存储空间	表示范围	次方表示
int	4个字节	-2,147,483,648～2,147,483,647	$-2^{31}$ ~ $2^{31}$-1，约为10的9次方
unsigned int	4个字节	0～4,294,967,295	0 ~ $2^{32}$-1，约为10的9次方
long	4个字节	-2,147,483,648～2,147,483,647	$-2^{31}$ ~ $2^{31}$-1，约为10的9次方
unsigned long	4个字节	0～4,294,967,295	0 ~ $2^{32}$-1，约为10的9次方
long long	8个字节	-9,223,372,036,854,775,808～9,223,372,036,854,775,807	$-2^{63}$ ~ $2^{63}$-1，约为10的18次方
unsigned long long	8个字节	0～18,446,744,073,709,551,615	0 ~ $2^{64}$-1，约为10的19次方