Fractal Streets

On the first line of the input is a positive integer, the number of test cases. Then for each test case:
A line containing a three positive integers, n < 32 and h, o < 2³¹, specifying the order of the Hilbert curve, and the house numbers of the offered house and the local city planning office.

C++14(g++5.4) 解法, 执行用时: 7ms, 内存消耗: 608K, 提交时间: 2020-05-03 19:22:00

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pii;
int t,n;
ll a,b,x,y;
pii calc(int n,ll m)
{
	if(n==0)return make_pair(0,0);
	long long len=1ll<<(n-1),cnt=1ll<<(2*n-2);
	pii pos=calc(n-1,m%cnt);
	ll x=pos.first,y=pos.second;
	ll z=m/cnt;
	if(z==0)return make_pair(y,x);
	else if(z==1)return make_pair(x,y+len);
	else if(z==2)return make_pair(x+len,y+len);
	else return make_pair(2*len-1-y,len-1-x);
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%lld%lld",&n,&a,&b);
		pii fa=calc(n,a-1),fb=calc(n,b-1);
		x=fa.first-fb.first,y=fa.second-fb.second;
		printf("%.0lf\n",sqrt(x*x+y*y)*10);
	}
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 10ms, 内存消耗: 456K, 提交时间: 2022-08-14 20:56:04

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PLL;
PLL cal(ll n,ll k){
    if(n==0) return{0,0};
    ll len=1<<n-1,cen=1ll<<2*(n-1);
    auto pos=cal(n-1,k%cen);
    auto x=pos.first,y=pos.second;
    auto z=k/cen;
    if(z==0) return{y,x};
    if(z==1) return{x,y+len};
    if(z==2) return{x+len,y+len};
    else return{2*len-1-y,len-1-x};
}
int main(){
    int t;
    cin>>t;
    while(t--){
        ll n,a,b;
        cin>>n>>a>>b;
        auto ac=cal(n,a-1);
        auto bc=cal(n,b-1);
        double x=ac.first-bc.first,y=ac.second-bc.second;
        printf("%.0lf\n",sqrt(x*x+y*y)*10);
    }
    return 0;
}

C++(clang++11) 解法, 执行用时: 10ms, 内存消耗: 504K, 提交时间: 2021-01-25 20:23:21

#include<iostream>
#include<cmath>
using namespace std;

typedef long long LL;
typedef pair<LL,LL> PLL;

PLL calc(LL n,LL m)
{
	if(n==0)return {0,0};
	LL len=1ll<<n-1, cnt=1ll<< 2*n-2;
	auto pos=calc(n-1,m%cnt);
	auto x=pos.first,y=pos.second;
	auto z=m/cnt;
	if(z==0)return {y,x};
	if(z==1)return {x,y+len};
	if(z==2)return {x+len,y+len};
	return {2*len-1-y,len-1-x};
}
 
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		LL N,A,B;
		cin>>N>>A>>B;
		auto ac=calc(N,A-1);
		auto bc=calc(N,B-1);
		double x=ac.first-bc.first,y=ac.second-bc.second;
		printf("%.0lf\n",sqrt(x*x+y*y)*10);
	}
	return 0;
}

详情