HDU 5573-Binary Tree【思维+二进制】-蒲公英云

HDU 5573-Binary Tree【思维+二进制】

野性酷女 2023-08-17 17:28 216阅读 0赞

题意：给你一个满二叉树，对于每个结点u，左儿子结点时2u，右儿子是2u+1，给你一个n和k，问你选一条k个节点的路径，每个点你可以选择加上或者减去这个结点的编号值，要求最终答案是n。

思路：我们考虑选择最左边的那条链，对于n是任意偶数而言，不难发现都可以构成。而对于n是奇数而言，我们在选择第k个时选择右儿子，最末尾的1就可以消掉转换成了偶数的情况。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ls rt << 1
#define rs rt << 1|1
#define mid ((l + r) >> 1)
#define lson l, mid, ls
#define rson mid + 1, r, rs
const int maxn = 100;
const int mod = 1e9 + 7;
bool vis[maxn];
int main()
{
    int t, t1 = 1;
    scanf("%d", &t);
    while(t--)
    {
        printf("Case #%d:\n", t1++);
        memset(vis, false, sizeof(vis));
        ll n; 
        int k;
        scanf("%lld%d", &n, &k);
        ll sum = 0;
        for(int i = 0; i < k; ++i)
        {
            sum += (1ll << i);
        }
        if(n % 2 == 0)
            sum++;
        ll tmp = (sum - n) / 2;
        for(int i = 60; i >= 0; --i)
        {
            if(tmp & (1ll << i))
                vis[i] = true;
        }
        for(int i = 0; i < k - 1; ++i)
        {
            printf("%lld ", (1ll << i));
            if(vis[i]) printf("-\n");
            else printf("+\n");
        }
        tmp = (1ll << (k - 1));
        if(n % 2 == 0) tmp++;
        printf("%lld +\n", tmp);
    }
    return 0;
}