5935 小球

5935 小球

时间限制: 2 s

空间限制: 16000 KB

题目等级 : 黄金 Gold

题目描述 Description

许多的小球一个一个的从一棵满二叉树上掉下来组成FBT(Full Binary Tree,满二叉树),每一时间,一个正在下降的球第一个访问的是非叶子节点。然后继续下降时,或者走右子树,或者走左子树,直到访问到叶子节点。决定球运动方向的是每个节点的布尔值。最初,所有的节点都是FALSE,当访问到一个节点时,如果这个节点是FALSE,则这个球把它变成TRUE,然后从左子树走,继续它的旅程。如果节点是TRUE,则球也会改变它为FALSE,而接下来从右子树走。满二叉树的标记方法如下图。

因为所有的节点最初为FALSE,所以第一个球将会访问节点1,节点2和节点4,转变节点的布尔值后在在节点8停止。第二个球将会访问节点1、3、6,在节点12停止。明显地,第三个球在它停止之前,会访问节点1、2、5,在节点10停止。   现在你的任务是,给定FBT的深度D,和I,表示第I个小球下落,你可以假定I不超过给定的FBT的叶子数,写一个程序求小球停止时的叶子序号。

输入描述 Input Description

输入文件仅一行包含两个用空格隔开的整数D和I。其中2<=D<=20,1<=I<=524288。

输出描述 Output Description

对应输出第I个小球下落停止时的叶子序号。

样例输入 Sample Input

4 2

样例输出 Sample Output

1 2

数据范围及提示 Data Size & Hint

2<=D<=20,1<=I<=524288。

分类标签 Tags 点此展开

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 bool a[10000001];
 6 int main()
 7 {
 8     int n,m;
 9     scanf("%d%d",&n,&m);
10     double p=pow(2,n);
11     int flag=0;// 表示最后一次的变换情况 
12     for(int i=1;i<=m;i++)
13     {
14         int now=0;//表示正在访问的节点
15         
16         while(now<=(int)p-1)
17         {
18             if(a[now]==0)
19             {
20                 a[now]=1;
21                 now=2*now;    
22                 flag=1;
23             }    
24             else
25             {
26                 a[now]=0;
27                 now=2*now+1;
28                 flag=2;
29             }
30         } 
31         if(i==m)
32         {
33             if(flag=1)
34             printf("%d",now/2);
35             else
36             printf("%d",now/2-1);
37         }
38     }
39     return 0;
40 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏aCloudDeveloper

探秘堆结构

一、概述   此处所说的堆为数据结构中的堆,而非内存分区中的堆。堆通常可以被看做是树结构,满足两个性质:1)堆中任意节点的值总是不大于(不小于)其子节点的值;2...

244100
来自专栏小樱的经验随笔

平衡树初阶——AVL平衡二叉查找树+三大平衡树(Treap + Splay + SBT)模板【超详解】

平衡树初阶——AVL平衡二叉查找树 一、什么是二叉树 1. 什么是树。 计算机科学里面的树本质是一个树状图。树首先是一个有向无环图,由根节点指向子结点。但是不严...

33940
来自专栏大闲人柴毛毛

动态规划法(五)——多段图问题

问题描述 给定一个多段图,求出多段图中的最短路径和最短路径长度。 什么是多段图? 多段图是一个有向、无环、带权 图。 有且仅有一个起始结点(原点source...

39440
来自专栏Petrichor的专栏

leetcode: 78. Subsets

11310
来自专栏美团技术团队

红黑树深入剖析及Java实现

红黑树是平衡二叉查找树的一种。为了深入理解红黑树,我们需要从二叉查找树开始讲起。 BST 二叉查找树(Binary Search Tree,简称BST)是一棵二...

33030
来自专栏Jack的Android之旅

疯狂java笔记之树和二叉树

树是一种非常常用的数据结构,树与前面介绍的线性表,栈,队列等线性结构不同,树是一种非线性结构

23220
来自专栏fangyangcoder

leetcode(二)

给定一个二叉数(root),二叉树中一个node(target)以及整数K,求二叉树中所有与target距离K的节点值。问题描述与example如下。

14920
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之重建二叉树(九度OJ1385)

题目描述: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7...

22550
来自专栏用户2442861的专栏

红黑树深入浅出

先来看下算法导论对R-B Tree的介绍: 红黑树,一种二叉查找树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条...

10920
来自专栏Vamei实验室

纸上谈兵: 树, 二叉树, 二叉搜索树

树的特征和定义 树(Tree)是元素的集合。我们先以比较直观的方式介绍树。下面的数据结构是一个树: ? 树有多个节点(node),用以储存元素。某些节点之间存在...

23170

扫码关注云+社区

领取腾讯云代金券