题目：
http://acm.hdu.edu.cn/showproblem.php?pid=5573
一棵二叉树，根结点值为1，左子结点为2i,右子结点为2i+1，
给出n和k，求在二叉树上从根向下共走k步（层），每步可以为当前结点权值取正号或者负号，求一种使最终取值和为n的可行方案（题目保证了k≤60）
解体思路
我把k=4 n从1到12列了下 发现……
n=1 -1-2-4+8
n=2 -1-2-4+9
n=3 +1-2-4+8
n=4 +1-2-4+9
n=5 -1+2-4+8
n=6 -1+2-4+9
....
n=11 +1-2+4+8
n=12 +1-2+4+9
发现 1.偶数只要把它减一的数最后的8改成9；
2.奇数：
最大到2^k-1 这里就是15 所以sum=15（即假设每位都拿来+了）
n=1时 式子是 -1-2-4+8；sum与n相差14；所以我们要做的就是不但没+7，反而-7，那么差就是14了
即（15-1）/2=7 二进制就是0111
一样的：
n=3时 （15-3）/2=6 二进制就是0110
他们的二进制1位拿来-，0位拿来+就好了（因为选中的要减去，没选中的也就是0位要加上）
#include<bits/stdc++.h> #define ll long long using namespace std; map<ll,ll>mp; int main() { int i,j,n,k; int t; cin>>t; int ki=1; ll aa[101]; ll sa=1; for(i=1;i<=60;i++) { aa[i]=sa;//算出每一位是多少，最后可以直接输出 sa*=2; } while(t--) { cin>>n>>k; printf("Case #%d:\n",ki++); int flag=0; if(n%2==0)flag=1,n-=1; ll sum=0; for(i=0;i<k;i++) sum+=pow(2,i); ll answer=(sum-n)/2; mp.clear(); for(i=60;i>=1;i--) { if(answer>=aa[i])answer-=aa[i],mp[aa[i]]=1;//标记出现过 } for(i=1;i<=k;i++) { if(i!=k)cout<<aa[i]<<" "; else { if(flag==1)cout<<aa[i]+1<<" ";//判断奇偶数 else cout<<aa[i]<<" "; } if(mp[aa[i]]==1)cout<<‘-‘; else cout<<‘+‘; cout<<endl; } } return 0; }
原文：https://www.cnblogs.com/ydw--/p/11729378.html
