题目中已经说明Hn是由4个Hn-1旋转拼接而成，递归的结构非常明显。所以对于求Hn中(x, y)的序号，我们自然而然会想能否转化成在Hn-1中求(x', y')的序号。
实际上我们只需要考虑Hn中的(x, y)是在左下、左上、右上、右下4个Hn-1中的哪一个里，即可转化成在Hn-1中求(x', y')序号的子问题。具体(x, y)到(x', y')的对应关系涉及到坐标平移和旋转，留给大家思考，不再赘述。
以样例为例，如上图所示，H3中的(6, 1)在右下角的H2中，并且对应着H2中(4, 3)这个点。
如果我们能正确求出H2中(4, 3)这个点的序号是12，又因为前3个H2中一共包含16x3=48个点，那么我们就能求出H3中的(6, 1)的序号是12+48=60。
最后需要注意的是n=30时一共包含2^60个点，所以计算序号的时候需要用64位整型存储。
一开始一直是50%，用了long int就AC了。。。
#include<stdio.h>
#include<math.h>
int main(){
long int N, n,x,y,i,j, jieguo=0,tmpn,t;
scanf("%ld %ld %ld",&n,&x,&y);
N=pow(2,n);
tmpn=n;
for(i=0;i<n;i++){
if(x<=N/2&&y<=N/2){
//1
t=y;
y=x;
x=N/2-t+1;
x=N/2+1-x;
N=N/2;
}else if(x<=N/2&&y>N/2){
//2
N=N/2;
jieguo+=N*N;
y-=N;
}else if(x>N/2&&y>N/2){
//3
N=N/2;
jieguo+=N*N*2;
y-=N;
x-=N;
}else{
//4
t=x;
x=y;
y=N-t+1;
x=N/2+1-x;
N=N/2;
jieguo+=N*N*3;
}
}
printf("%ld",++jieguo);
return 0;
}
大佬帮我看下我的代码为啥一直只能过90%啊
public static long solve(long x,long y, int n){
if (n<=1){
if (x==1 && y==1){
return 1;
}else if (x==1 && y==2){
return 2;
}else if (x==2 && y==2){
return 3;
}else{
return 4;
}
}
long rows=(long) Math.pow(2, n)/2;
int xth=0;
long oneCount=rows*rows;
if (x<=rows && y<=rows){
xth=1;
}else if (x<=rows && y>rows){
xth=2;
}else if (x>rows && y>rows){
xth=3;
}else {
xth=4;
}
if (xth==1){
return (xth-1)*oneCount+solve(y, x, n-1);
}else if (xth==2){
long x0=0;
long y0=rows;
return (xth-1)*oneCount+solve(x, y-y0, n-1);
}else if (xth==3){
long x0=rows;
long y0=rows;
return (xth-1)*oneCount+solve(x-x0, y-y0, n-1);
}else{
long x0=2*rows+1;
long y0=rows+1;
return (xth-1)*oneCount+solve(y0-y,x0-x, n-1);
}
}
你把你完整代码PO上来？ 我看你90的是计算xth那里有问题，应该是>的地方写的>=。上面这个代码这里已经修改过来了，应该能AC了。
你看题目分析特别在最后提醒要用64bit整型 :D