当前位置: 代码迷 >> 综合 >> 【OPENJUDGE】【分治】2.4-8463-Stupid cat Doge
  详细解决方案

【OPENJUDGE】【分治】2.4-8463-Stupid cat Doge

热度:95   发布时间:2023-11-21 07:20:03.0

题目

描述:

动物园的规划和城市规划一样是个令人头疼的大问题。不幸的是,动物园规划师R.V.L.先生高估了小动物们 的智商,他设计了一个极其复杂的动物园道路规划方案,如下图所示:
动物园按照下述方法进行扩建:当动物园规模扩大之后,R.V.L.先生设计的解决方案是把与原来动物园结构一样的区域复制或旋转90度之后按照图中的方式建设在原来的动物园周围(即将原来的动物园复制一遍放在原动物园上方,将顺时针旋转90度后的动物园放在原动物园的左上方,将逆时针旋转90度后的动物园放在原动物园的左方),再用道路将四部分的首尾连接起来,即可提升动物园的等级。
容易看出,等级提升后的动物园仍然是由一条道路连接,等级为N的动物园共能容纳2^2N只小动物,每只小动物将被分配到唯一的一间房屋。对于任意等级的动物园,我们从左上角开始沿着唯一的道路走,按照道路为房屋标号,就能够得到每间房屋的编号了。
说了这么多,智商余额不足的Stupid cat和Doge早已晕头转向。他们想知道,如果城市发展到了一定等级,他俩各自所处的房屋之间的直线距离是多少。房屋之间的距离是指两座房屋中心点之间的距离,你可以认为每间房屋都是边长为10米的正方形。
这里写图片描述

输入:

输入包含多组测试数据,第一行有一个整数 T 表示测试数据的数目。每组测试数据包含一行用空格隔开的三个整数 N, S, D,表示动物园等级,Stupid cat分配到的房屋编号和Doge分配到的房间编号。

输出:

对于每组测试数据,在单独的一行内输出答案,四舍五入到整数。

样例

输入:

3
1 1 2
2 16 1
3 4 33

输出:

10
30
50

数据范围

N31,1S,D22N,1T10000N≤31,1≤S,D≤22N,1≤T≤10000

解析

许多人看到这里就MB了……
But,如果你仔细看的话你就会发现:
每一个图都可以分成四份!
它的左上角由上一等级图顺时针旋转90度得到;
它的左下角由上一等级图逆时针旋转90度得到;
而右下角和右上角就是上一等级图!!!

于是,我们自然地得出了下面的代码:

void turn(x,y)
{if(这个图在左上角)交换x,y;if(这个图在左下角)x=边长-1-y;y=边长-1-x;
}

很多人接下来一定会想到用递推,但是……
N≤31!即:边长≤2^N!!数组会爆!!!
So,只能用递归模拟!

我们也不难发现:编号与面积有关——
如果(编号-1)/面积/4==0,则:这个房子在左上角;
如果(编号-1)/面积/4==1,则:这个房子在右上角;
如果(编号-1)/面积/4==2,则:这个房子在左下角;
如果(编号-1)/面积/4==3,则:这个房子在右下角。

再调用turn函数就能求出当前x,y的值
然后,我们再分情况加上当前边长的一半就能求出具体的x,y值
最后,我们再调用一次find函数就能求出Stupid cat & Doge的坐标;
再套用两点间距离公式:

|AB|=(Ax?Bx)2+(Ay?By)2????????????????????|AB|=(Ax?Bx)2+(Ay?By)2

就可以求出Stupid cat & Dog直线距离了。

代码

#include<cstdio>
#include<cmath>
int f[5][2]={
   {
   0,0},{
   0,0},{
   0,1},{
   1,1},{
   1,0}};
void turn(int i,int n,long long &x,long long &y)
{long long xn=x,yn=y;if(i==1){x=yn;y=xn;}if(i==4){x=pow(2,n)-1-yn;y=xn;y=pow(2,n)-1-y;}
}
void find(int n,long long a,long long &x,long long &y)
{if(n==0)return;long long k=pow(2,2*(n-1));int i;for(i=1;i<=4;i++)if(k*i>=a)break;find(n-1,a-k*(i-1),x,y);turn(i,n-1,x,y);x+=pow(2,n-1)*f[i][0];y+=pow(2,n-1)*f[i][1];
}
int main()
{int t;scanf("%d",&t);for(int i=1;i<=t;i++){long long a,b,x1,x2,y1,y2,k;int n;scanf("%d %lld %lld",&n,&a,&b);x1=x2=y1=y2=0;find(n,a,x1,y1);find(n,b,x2,y2);k=round(sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))*10);printf("%lld\n",k);}return 0;
}