博客

题意：

在一颗满二叉树中从根节点出发选一个路径，每个节点可加可减，最终得到数n，输出路径。

思路：

最靠左的那条链可以表示出任何数，因为都是2的倍数，相当于用二进制在表示。需要注意的是，每个数+和-相差的是这个数的2倍，所以需要将n/2进行二进制运算。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=110;
int bit[maxn];
int binary(ll x){
    int cnt=1;
    while(x){
        bit[cnt++]=x%2;
        x/=2;
    }
    return cnt;
}
int main(){
    int t;scanf("%d",&t);
    int flag=1;
    while(t--){
        ll n,k;scanf("%lld%lld",&n,&k);
        printf("Case #%d:\n",flag++);
        ll tmp=n/2;
        if(n%2==0){
            tmp--;
        }
        int len=binary(tmp);
//        ll ans=0;
        ll cnt=1;
        for(int i=1;i<len;i++){
            if(bit[i]){
                printf("%lld +\n",cnt);
            }
            else{
                printf("%lld -\n",cnt);
//                ans-=cnt;
            }
            cnt*=2;
        }
        if(n%2){
//            ans+=cnt;
            printf("%lld +\n",cnt);
        }
        else{
            printf("%lld +\n",cnt+1);
        }
//        printf("%lld\n",ans);
    }
}