[HDU5573]Binary Tree_binarytree-程序员宅基地

技术标签: -----------------------归纳  

Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)

分数:2500,构造还是比较难的

Problem Description
The Old Frog King lives on the root of an infinite tree. According to the law, each node should connect to exactly two nodes on the next level, forming a full binary tree.

Since the king is professional in math, he sets a number to each node. Specifically, the root of the tree, where the King lives, is 1. Say f r o o t = 1 f_{root}=1 froot=1.
And for each node u, labels as fu, the left child is f u × 2 f_{u×2} fu×2 and right child is f u × 2 + 1 f_{u×2+1} fu×2+1. The king looks at his tree kingdom, and feels satisfied.

Time flies, and the frog king gets sick. According to the old dark magic, there is a way for the king to live for another N years, only if he could collect exactly N soul gems.

Initially the king has zero soul gems, and he is now at the root. He will walk down, choosing left or right child to continue. Each time at node x, the number at the node is f x f_x fx (remember f r o o t = 1 f_{root}=1 froot=1), he can choose to increase his number of soul gem by fx, or decrease it by f x f_x fx.

He will walk from the root, visit exactly K K K nodes (including the root), and do the increasement or decreasement as told. If at last the number is N N N, then he will succeed.
Noting as the soul gem is some kind of magic, the number of soul gems the king has could be negative.
Given N , K N, K N,K, help the King find a way to collect exactly N N N soul gems by visiting exactly K K K nodes.

Input
First line contains an integer T T T, which indicates the number of test cases.
Every test case contains two integers N N N and K K K, which indicates soul gems the frog king want to collect and number of nodes he can visit.

1 ≤ T ≤ 100 1≤T≤100 1T100
1 ≤ N ≤ 1 0 9 1≤N≤10^9 1N109
N ≤ 2 K ≤ 2 60 N≤2^K≤2^{60} N2K260

Output
For every test case, you should output “Case #x:” first, where x indicates the case number and counts from 1.

Then K lines follows, each line is formated as ‘a b’, where a is node label of the node the frog visited, and b is either ‘+’ or ‘-’ which means he increases / decreases his number by a.

It’s guaranteed that there are at least one solution and if there are more than one solutions, you can output any of them.

Sample Input

2
5 3
10 4

Sample Output

Case #1:
1 +
3 -
7 +
Case #2:
1 +
3 +
6 -
12 +

题意:
给定 n , k n,k n,k
刚开始你位于二叉树的1号节点,编号x的两个儿子分别是 x × 2 x×2 x×2 x × 2 + 1 x×2+1 x×2+1,每次你可以选择增加等于这个节点编号的灵魂石,或者减少这个节点编号的灵魂石,要求最后到达第 k k k层的时候,得到的灵魂石的个数恰好为 n n n

题解:
我们想想一直走 1 , 2 , 4 , . . . , 2 k − 1 1,2,4,...,2^{k-1} 1,2,4,...,2k1这种方法
考虑 n n n为偶数的时候。设 y = 2 k − 1 − n y = 2^k-1-n y=2k1n我们显然可以根据 y y y的二进制从低到高来考虑,如果第k+1位是0则我们加上第k层,否则减去第k层。
然后对于n为奇数的情况。我们只要把n变为n-1之后,就可以直接按照奇数的做了,但是最后一层要加上 2 k − 1 + 1 2^{k-1}+1 2k1+1

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int k;
ll n;
int w33ha(int CASE){
    
    scanf("%lld%d",&n,&k);
    printf("Case #%d:\n",CASE);
    ll res=(1LL<<k)-1-n;
    ll flag=0;
    if(res&1){
    
        res++;
        flag=1;
    }
    for(int i=0;i<k-1;i++){
    
        if(res&(1LL<<(i+1))){
    
            printf("%lld -\n",(1LL<<i));
        }
        else{
    
            printf("%lld +\n",(1LL<<i));
        }
    }
    printf("%lld +\n",(1LL<<(k-1))+flag);
    return 0;
}
int main(){
    
    int T;scanf("%d",&T);
    for(int i=1;i<=T;i++)w33ha(i);
    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/dxyinme/article/details/100529608

智能推荐

面试中经典函数的实现_面试常见需要实现的库函数-程序员宅基地

文章浏览阅读634次。很多经典的库函数如strcpy,memcpy等在面试中经常出现,虽然思想并不复杂,但要写出一个比较完善甚至是完全正确的程序非常考验一个程序员思维的严谨性和编程的风格,这里简单实现strcpy、strncpy、memcpy、memmove、memset、strlen等函数,仅供参考。一 字符串复制strcpy  strcpy函数把一个字符串的内容复制到另一个字符串里,以'\0'作_面试常见需要实现的库函数

android 锤子桌面壁纸,锤子桌面使用技巧|锤子桌面 1.5.1 安卓版_久友下载站_壁纸美化...-程序员宅基地

文章浏览阅读686次。锤子ROM从来都是只闻其声,未见其人。发布会开到现在已经大半年了,却只弄出了这么个玩意来,我对它已无力吐槽,想体验一下的就自己下吧!新版特性:新增:适配 Smartisan OS 3.0 视觉规范新增:桌面图标按“应用分类”排序新增:桌面图标排序方式支持实时预览新增:命名桌面板块时的建议标题新增:搜索功能,你可以通过桌面上的搜索 app 或在桌面上滑呼出搜索功能,以快速查找本机的应用程序、联系人与...

华为手机如何设置鸿蒙系统,华为手机怎样安装鸿蒙系统 安装步骤如下-程序员宅基地

文章浏览阅读665次。描述鸿蒙系统是一款全新的面向全场景的分布式操作系统,基于微内核打造了一个超级虚拟终端互联的世界,将人、设备、场景有机地联系在一起,一站式解决智能家居、智慧办公、智慧出行、运动健康、影音娱乐五大生活场景。并支持PC、手机、平板、手表等多设备多硬件。同时,鸿蒙系统解决了以往安卓系统卡顿及老化问题,更流畅、续航更持久,极大的提升了用户体验。鸿蒙系统的安装步骤:1、6月2日起,首批启动公测升级 Harmo..._鸿蒙系统怎样和华为手机

“华为云杯”2020深圳开放数据应用创新大赛·生活垃圾图片分类(目标检测)_华为公司垃圾分类大赛开放数据集-程序员宅基地

文章浏览阅读741次。代码和思路分享来自Github:https://github.com/selous123/yolov3-pytorch-custom调ultralytics/yolov3这个炉子,目前b榜在0.74左右,一阶段准确率很高的网络了。前排大佬可能大部分都是基于MMdet的二阶段网络,Faster-RCNN,Cascade-RCNN等。比赛数据集下载地址:链接: https://pan.baidu.com/s/1lh1D1wvXUV3rjJOUpWsBlA 提取码: znk3MMdetection安._华为公司垃圾分类大赛开放数据集

matlab实现PS算法之色调分离_ps去色和matlab-程序员宅基地

文章浏览阅读2.3k次。%{色调分离的原理就是将R, G, B每个通道 0-255 的色调区间进行强制划分到给定的区间里去,所以色调会合并,最终的图像看起来颜色就是一块一块的。%}clear,clc;[filename,pathname] = uigetfile('*.jpg;*.bmp','选择图片','E:\pictures\For_Project\Matlab');imgaepath = strcat_ps去色和matlab

快来新媒体:通过社交媒体建立个人IP的 5 种行之有效的策略_新媒体营销设计ip-程序员宅基地

文章浏览阅读141次。成为有影响力的社交媒体达人为个人IP营销和小型商业机会打开了大门,因此请从他们的主页内容中找出一些如何帮助您利用的个人IP的信息。在您不发帖的日子里,专注于生成您的关注者希望看到的内容类型,例如可共享的信息图、播客链接或有关您参加的有价值的网络研讨会的帖子。您可以谈论您的成就并添加有关您个人生活的有趣信息,但请记住,注入过多的个人观点可能会孤立您的目标受众。由于社交媒体的成功并不是建立个人IP的万能方法,因此您必须做一些工作并做出一些明智的决定,以确保您通过社交媒体投射出正确的个人IP形象。..._新媒体营销设计ip

随便推点

Maven——Project configuration is not up-to-date with pom.xml问题_this pm2 is not up to date-程序员宅基地

文章浏览阅读4.8k次。Maven——Project configuration is not up-to-date with pom.xml问题_this pm2 is not up to date

java基础笔试题(一)--取二进制位,变量互换,for循环标记_java笔试题 二进制 难-程序员宅基地

文章浏览阅读362次。一、取出一个二进制的某一段。采用与运算方式 二、对两个变量的值进行互换。1.使用第三方变量2.相加进行互换两个数相加的时候,值有可能超出int表示范围,不推荐。3.通过异或运算 该方式虽然效率高,而且避免了超出int值,但是可读性较差。三种方式都可以对两个变量的值进行交换,但是推荐使用第一种。(面试除外)_java笔试题 二进制 难

RNNoise: Learning Noise Suppression(深度学习噪声抑制)(1)_rnnoise模型-程序员宅基地

文章浏览阅读1.2w次,点赞4次,收藏65次。前言我将通过几篇文章来介绍一下RNN用于降噪的实例。综合论文和项目介绍及代码编写原文链接:https://people.xiph.org/~jm/demo/rnnoise/上图显示了前后音频噪声抑制的频谱图。(上:noisy,中:RNNoise,下:clean speech)RNNoise该演示介绍了RNNoise项目,显示了如何将深度学习应用于噪声抑制。主要思想是将经典信号处理与深..._rnnoise模型

制作抖音卡点视频?Python来帮你~-程序员宅基地

文章浏览阅读1k次。点击上方“AirPython”,选择“置顶公众号”第一时间获取Python技术干货!阅读文本大概需要10 分钟。1目 标 场 景玩抖音的朋友都应该知道,最近「卡点视..._python将多个视频根据音乐自动卡点混剪成一个视频?

PHP ApiDoc接口文档工具,提供php api文档模板-程序员宅基地

文章浏览阅读500次。ApiDoc参考前言ApiDoc 用来比较规范的管理 API 文档。ApiDoc 这个 API 文档管理器,可以根据你代码的注释来进行自动生成 API 文档。同时支持 C#、Java、JavaScript、PHP、Python等语言。目录目录结构12345678910111213project 项目目录├─src 源代码目录│ ├─commo..._php apidoc

ubuntu中docker的安装和使用--学习笔记_compose1.1.1-程序员宅基地

文章浏览阅读260次。1. Docker & Docker Compose1.1. Docker1.1.1. Docker安装sudo apt install docker.io1.1.2. Docker修改国内镜像加速器您可以通过修改daemon配置文件/etc/docker/daemon.json来使用加速器sudo mkdir -p /etc/dockersudo tee /etc/docker/daemon.json <<-'EOF'{ "registry-mirrors":_compose1.1.1