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

野性酷女 2023-08-17 17:28 83阅读 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;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，83人围观）

还没有评论，来说两句吧...

相关阅读

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

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

野性酷女/ 2023年08月17日 17:28/ 0 赞/ 84 阅读

相关 HDU 5534-Partial Tree【完全背包+思维】

题意：给你n个点，再给出来你f(1 ~ n) 就是每个度数的权值，让你构建一棵树，使得所有点的权值和最大。思路：首先每个点的度数至少都是1，而且这n个点的度数总和必须是2n

约定不等于承诺〃/ 2023年08月17日 15:44/ 0 赞/ 57 阅读

相关 HDU 5573 Binary Tree（规律题）

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=5573][http_acm.hdu.edu.cn_showproblem.ph

柔情只为你懂/ 2022年07月16日 03:14/ 0 赞/ 88 阅读

相关 Binary Bomb 二进制炸弹

实验报告实验（三）题目 Binary Bomb 二进制炸弹　　　计算机科学与技术学院目录第1章实验基本信息... - 3 - 1.1 实

￡神魔★判官ぃ/ 2022年04月22日 20:14/ 0 赞/ 442 阅读

相关 HDU - 5573 Binary Tree

题目：点击打开链接题意：给你一个n和k和一颗完全二叉树（权值1 2 3 4 5 6 ...）,让你从1开始一直到第k层选择一条路径，路径上的每个点可以选择\1或\(-1

淡淡的烟草味﹌/ 2022年04月15日 06:42/ 0 赞/ 86 阅读

相关 110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. For this problem, a height-bal

系统管理员/ 2022年03月26日 08:59/ 0 赞/ 153 阅读

相关 Invert Binary Tree

Invert a binary tree. 4 / \ 2 7 / \ / \ 1 3 6 9

太过爱你忘了你带给我的痛/ 2021年12月17日 10:41/ 0 赞/ 190 阅读

相关 [LintCode] Binary Tree Serialization

Design an algorithm and write code to serialize and deserialize a binary tree. Writing t

- 日理万妓/ 2021年12月03日 07:15/ 0 赞/ 187 阅读

相关 Binary Tree Tilt

Given a binary tree, return the tilt of the whole tree. The tilt of a tree node is defi

古城微笑少年丶/ 2021年10月01日 07:56/ 0 赞/ 191 阅读

相关 B. Binary Removals （思维）

[题目][Link 1] 思路：想要出现否的情况那一定会有0在1的后面，而我们的删除操作只能隔着删，所以当出现两个00或两个11必然会留下一个，所以从后往前遍历，如果发现

爱被打了一巴掌/ 2021年07月17日 00:37/ 0 赞/ 289 阅读