HDU 5573 Binary Tree（规律题）

柔情只为你懂 2022-07-16 03:14 130阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=5573][http_acm.hdu.edu.cn_showproblem.php_pid_5573]

题目大意：  
给你一个满二叉树，可以向下无限延伸，每个结点的值从上到下从左到右就是12345678这样，给你一个数N和K，你要走K步，每步可以往下走一层，每次可以加上或者减去结点的值，求出一个能走到N的方案。

解题思路：注意到N的范围，所以可以每次只向左走，最后一步可以可以向右走，利用二进制判断每个节点加上还是减去即可（多种方法可以自己思考下）。如

10 -1 -2 4 9最后一步向右走  
11 1 -2 4 8一直向左走  
12 1 -2 4 9 最后一步向右  
13 -1 2 4 8 一直向左走

AC代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <string>
    #include <vector>
    #include <list>
    #include <map>
    #include <queue>
    #include <stack>
    #include <algorithm>
    #include <set>
    #include <functional>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    double EPS=1e-10;
    typedef long long LL;
    LL n,k,k1;
    bool mark=true; //是否奇数
    vector<int> vec;
    
    LL cal(LL k)
    {
        LL t=1;
        while(k--) t*=2;
        return t;
    }
    
    void get_sub()
    {
        k1--;
        k1-=n;
        if(k1%2)
        {
            mark=true;
            k1++;
        }
        else mark=false;
    }
    
    void get_bir()
    {
        k1>>=1;
        for(int i=0;i<k;i++)
        {
            if((k1>>i)&1) vec.push_back(1);
            else   vec.push_back(0);
        }
    }
    
    void solve()
    {
        LL t=1;
        for(int i=0;i<k-1;i++)
        {
            printf("%I64d",t);
            if(vec[i]==1) printf(" -\n");
            else printf(" +\n");
            t*=2;
        }
        if(mark) printf("%I64d +\n",t+1);
        else printf("%I64d +\n",t);
    
    
    }
    int main()
    {
        int T,cas=1;
        RI(T);
        while(T--)
        {
            vec.clear();
            scanf("%I64d %I64d",&n,&k);
            printf("Case #%d:\n",cas++);
            k1=cal(k);
            if(k1!=n)
            {
                get_sub();
                get_bir();
            }
            else
            {
                for(int i=0;i<k;i++)
                    vec.push_back(0);
                mark=true;
            }
            solve();
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_5573]: http://acm.hdu.edu.cn/showproblem.php?pid=5573