HDU - 5573 Binary Tree

淡淡的烟草味﹌ 2022-04-15 06:42 126阅读 0赞

## 题目：点击打开链接   题意：给你一个n和k和一颗完全二叉树（权值1 2 3 4 5 6 ...）,让你从1开始一直到第k层选择一条路径，路径上的每个点可以选择\*1或\*(-1)，让你输出一种构造方案恰好到第n层能得到n。   分析：很有意思的一道题，记录一下，首先明确由1.2.4...2k1.2.4...2k可以构造出所有小于2k+12k+1的数，那么实际上只要走2的幂次即最左边的结点即可。    那么实际上这个过程就类似整数的二进制表示，1表示加，0表示减，如果该位为0，那么意味着在2k+1−12k+1−1的基础上减去了二倍改为代表的数，所以我们求出n与2k+1−12k+1−1的差，将差的一半的二进制中为1的位置为0即可~~    注意偶数的时候，差为奇数，那么我们将差多加个一，让最后一步走右边的结点，即加一即可。参考博客[https://blog.csdn.net/yukizzz/article/details/51264836][https_blog.csdn.net_yukizzz_article_details_51264836]。   代码： ##

///#pragma comment(linker, "/STACK:102400000,102400000")
    ///#include<unordered_map>
    ///#include<unordered_set>
    #include<algorithm>
    #include<iostream>
    #include<fstream>
    #include<complex>
    #include<cstdlib>
    #include<cstring>
    #include<cassert>
    #include<iomanip>
    #include<string>
    #include<cstdio>
    #include<bitset>
    #include<vector>
    #include<cctype>
    #include<cmath>
    #include<ctime>
    #include<stack>
    #include<queue>
    #include<deque>
    #include<list>
    #include<set>
    #include<map>
    using namespace std;
    #define pt(a) cout<<a<<endl
    #define debug test
    #define mst(ss,b) memset((ss),(b),sizeof(ss))
    #define rep(i,a,n) for (int i=a;i<=n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pii pair<int,int>
    #define fi first
    #define se second
    #define ll long long
    #define ull unsigned long long
    #define pb push_back
    #define mp make_pair
    #define inf 0x3f3f3f3f
    #define eps 1e-10
    #define PI acos(-1.0)
    const ll mod = 1e9+7;
    const int N = 1e6+10;
    
    ll qp(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    int to[4][2]={
       {-1,0},{1,0},{0,-1},{0,1}};
    
    int a[N];
    int main ()
    {
        int t;
        cin>>t;
        int cnt = 0;
        while(t--){
            int n, k;
            cin>>n>>k;
            cnt++;
            cout<<"Case #"<<cnt<<":"<<endl;
            ll sum = 1<<(k+1) - 1;
            int f = 0;
            if(n % 2 == 0){
                f = 1;
                n--;
            }
            ll res = (sum - n) / 2;
            for(int i = 0; i < k - 1; i++){
                ll tmp = 1<<i;
                if(res&1)  cout<<tmp<<" -"<<endl;
                else cout<<tmp<<" +"<<endl;
                res = res>>1;
            }
            ll tmp = 1<< (k - 1);
            if(f) cout<<tmp + 1<<" +"<<endl;
            else cout<<tmp<<" +"<<endl;
        }
        return 0;
    }

[https_blog.csdn.net_yukizzz_article_details_51264836]: https://blog.csdn.net/yukizzz/article/details/51264836