hdu 5573 binary tree

###Pro：2015上海区域赛B题

题意：一颗编号为 1 2 3 2^k 2^k+1…的满二叉树，从root点初始num=0，开始向下遍历k层，加或减去编号，使得num等于N；

题解：注意题目条件，N <= 2^k <= 2^60,所以一个N，是可以被最左边一条边（1,4,8，，2 ^ k)表示,或者被次左（1,2,4，，2 ^ k + 1)表示;

若设x为+的数，那么
x-（2^k-x)=n;
x=(2^k+n)/2
=_=大概是这个理，分奇数，偶数讨论下

代码:



using namespace std;

typedef long long LL;

int (){
    int T, cas=0;
    scanf("%d",&T);
    while(T--){
        int n,k;
        scanf("%d%d",&n,&k);
        printf("Case #%d:n",++cas);
        LL x;
        if(n&1){
            x=((1L<<k)-1+n)>>1;
            for(int i=0;i<k;i++){
                if(x&1) printf("%lld +n",1L<<i);
                else printf("%lld -n",1L<<i);
                x>>=1;
            }
        }
        else{
            x=(((1L<<k)+n)>>1)-1;
            for(int i=0;i<k;i++){
                if(i==k-1){
                    if(x&1) printf("%lld +n",1L<<i|1);
                    else printf("%lld -n",1L<<i|1);
                }
                else{
                    if(x&1) printf("%lld +n",1L<<i);
                    else printf("%lld -n",1L<<i);
                }
                x>>=1;
            }
        }

    }
    return 0;
}

hdu 5573 binary tree

END

近期文章

近期评论

标签

热门

文章归档

分类目录

功能