错误尝试
很显然,这道题是可以递归求解的。但是我刚开始的思路却是一个极其复杂,又非常模糊的错误思路:(如果怕被误导可以跳过这一段)
我的最初想法是:
从图中框出的3->2->1递归求解。虽然能手推得到一个似是而非的过程,但我始终抽象不出一个便于编程的公式。后来我意识到,这里每个问题并不是上一个的子问题。
看过y总的题解之后,我发现正确的递归是这样的:
从3->2->1递归求解。这其中每个问题都是上一个的子问题。那如何才能从子问题的解中找到规模较大问题的解呢?
找规律
我们以第一个点为原点,向左为y轴正向,向下为x轴正向。
对比2,3,我们可以看出:
- 左上角 是由2绕(1->11)这条对角线翻转而成。只需将2中x和y坐标交换一下即可。
- 右上角和右下角 都是2直接平移过去的,我们只需要简单地将2中的坐标加上对应的偏移量即可
- 左下角 是2绕原点逆时针旋转90°,再绕x轴翻转,最后平移得到的。(可以对比两个图形第一个点的位置和方向)
AC代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
PLL calcu(LL n, LL a){
if(n == 0) return {0, 0};
LL len = 1ll << n-1;
LL cnt = 1ll << (n-1)* 2;
auto pos = calcu(n-1, a % cnt);
LL x= pos.first;
LL y = pos.second;
int k = a / cnt;
switch(k){
case 0:
return {y, x};
case 1:
return {x, y + len};
case 2:
return {x + len, y + len};
default:
return {2 * len -1 - y, len - x - 1};
}
}
void solve(LL n, LL a, LL b){
PLL ap = calcu(n, a-1);
PLL bp = calcu(n, b-1);
double dx = ap.first - bp.first;
double dy = ap.second - bp.second;
//printf("%lld %lld\n", bp.first, bp.second);
double dis = sqrt(dx * dx + dy * dy);
printf("%.0lf\n", dis*10);
}
int main(void){
LL n;
LL a, b;
int t;
scanf("%d", &t);
while(t --){
scanf("%lld %lld %lld", &n, &a, &b);
solve(n, a, b);
}
}
懂了懂了