2015年ACM/ICPC上海赛区 B题（构造+二进制思维）
题意：给你n,k(n<=1e9,n<=2^k<=2^60)，让你按完全二叉树（层序编号）形式从根节点（1号节点）往下找一条路径，深度为k，+-符号自己确定，使得答案为n。
注意题目中的关键条件：n<=2^k
这是解决本题的关键。以为一个长度为k的二进制串中一定可以构造1~2^k次方中的任意一个数。只有第k可能为2^(k-1)或2^(k-1)+1，然后剩下的一定是1~2^(k-2)。从第k层开始构造，如果n>0则为+,n<0则为-。
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,k;
ll p[66],o[66],a[66];
int main()
{
p[0]=1;
for(int i=1;i<=61;i++) p[i]=p[i-1]*2;
int T,cas=1;
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld",&n,&k);
if(n&1) a[k]=p[k-1];
else a[k]=p[k-1]+1;
o[k]=1;a[1]=1;n-=a[k];
for(int i=k-1;i>=1;i--)
{
a[i]=p[i-1];
if(n<0) o[i]=0,n+=a[i];
else o[i]=1,n-=a[i];
}
printf("Case #%d:\n",cas++);
for(int i=1;i<=k;i++) printf("%lld %c\n",a[i],o[i]?'+':'-');
}
}