HDU 5573-Binary Tree (构造)

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5573

题目大意：
有一棵二叉树，根结点值为1，左子结点为$2*i$,右子结点为$2*i+1$，给出n和k，求在二叉树上从根向下共走k步，每步可以为当前结点权值取正号或者负号，求一种使最终取值和为n的可行方案

分析：
通过打表每一个数的构成方式可以发现，每一个数都可以由序列$1,2,4,8....(2^{k-1},2^{k-1}+1)$通过取正负，或者最后一项取奇偶来得到，不妨大胆假设从根开始每次取左子结点，可以取到所有$1,3,5,7,\dots 2^k-1 $ 等所有$2^k-1$内的奇数，那么在此基础上，最后一层不取$2^{k-1}$，转而取右子结点$2^{k-1}+1$，即可构造出$2^k$以内的所有偶数，而题意写明,$N\leq 2^K$，所以任意的N均可以由此方式构造得到

那么实际上这个过程就类似整数的二进制表示，1表示加，0表示减，如果该位为0，那么意味着在$2^k−1$的基础上减去了二倍改为代表的数，所以我们求出n与$2^k−1$的差，将差的一半的二进制中为1的位置为0即可
注意偶数的时候，差为奇数，那么我们将差多加个一，让最后一步走右边的结点，即加一即可

另外贪心也是可以的，由于当前层结点的值大于上层所有父结点的权值和，所以如果当前总权值<N，必须加上当前层结点，否则减去，依次递推即可得到一种方案，若最后得到的当前权值总和不为N，说明最后要取$2^{k-1}+1$，将最后一项改变即可

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>


using namespace std;

long long bm[100];
long long n,temp,now;
int k;
void init()
{
    bm[0] = 1;
    for (int i = 1 ; i <= 61 ; i ++)
        bm[i] = bm[i-1]*2;
}
long long path[100];
char f[100];


int main()
{
    init();
    int T,t=1;
    scanf("%d",&T);
    while (T--)
    {
        temp = 0;
        scanf("%lld%d",&n,&k);
        now = bm[k-1];
        printf("Case #%d:\n",t++);
        for (int i = 1 ; i <= k ; i ++)
        {
            path[i] = now;
            if (temp<n)
                temp += now,f[i] = '+';
            else
                temp -= now,f[i] = '-';
            now /= 2;
        }
        if (temp==n)
        {
            for (int i = k ; i >= 1 ; --i)
                printf("%lld %c\n",path[i],f[i]);
            continue;
        }
        path[1] = bm[k-1]+1;
        for (int i = k ; i >= 1 ; --i)
            printf("%lld %c\n",path[i],f[i]);
        continue;

    }
  return 0;

}