hiho一下第163周《Hilbert Curve》题目分析

9
1

《希尔伯特曲线》题目分析

题目中已经说明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位整型存储。

2 answer(s)

0

一开始一直是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;
}
  • 你看题目分析特别在最后提醒要用64bit整型 :D

  • 添加评论
  • reply
1

大佬帮我看下我的代码为啥一直只能过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了。

  • 添加评论
  • reply

write answer 切换为英文 切换为中文


转发分享