NYOJ63小猴子的下落

2024-05-05 05:58
文章标签 下落 小猴子 nyoj63

本文主要是介绍NYOJ63小猴子的下落,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

小猴子下落

时间限制: 3000  ms   内存限制: 65535  KB
难度: 3
描述

有一颗二叉树,最大深度为D,且所有叶子的深度都相同。所有结点从左到右从上到下的编号为1,2,3,·····,2的D次方减1。在结点1处放一个小猴子,它会往下跑。每个内结点上都有一个开关,初始全部关闭,当每次有小猴子跑到一个开关上时,它的状态都会改变,当到达一个内结点时,如果开关关闭,小猴子往左走,否则往右走,直到走到叶子结点。

一些小猴子从结点1处开始往下跑,最后一个小猴儿会跑到哪里呢?

输入
输入二叉树叶子的深度D,和小猴子数目I,假设I不超过整棵树的叶子个数,D<=20.最终以 0 0 结尾
输出
输出第I个小猴子所在的叶子编号。
样例输入
4 2
3 4
0 0
样例输出
12
7
开始的时候对题目的理解除了问题,不知道是所有的节点的状态都会改变还是只改变猴子经过节点的状态,后来看了解题报告后恍然大悟了,就是单个节点的状态改变了。 其实这题目不难,关键的是得有点宏观的思想。 先从第一个节点开始,初始状态时关闭的,当第一只猴子经过时,状态改变,以此类推,一只猴子经过,改变一次,一只猴子经过改变一次,由此我们发现,奇数猴子关闭往左,偶数猴子打开向右。于是我们推出了第I只猴子在第一个节点处的走向。 其它节点也是同样的,不过每一层状态的改变次数都会比上层的减半。理解了吧?下面是代码。 #include int main() {   int d,i;   while(scanf("%d%d",&d,&i)&&(i+d)){      int k=1;      for(int j=0;j      if(i%2==0){         k=k*2+1;i=i/2;//往右走后达到的位置,      }else{         k=k*2;i=(i+1)/2;      }      }      printf("%d\n",k);   } } 还有一种高上大的写法哦: #include int main() {   int i,value,depth,base,newValue;   while(scanf("%d%d",&depth,&value)&&depth||value)   {       for(i=base=1;i       base<<=1;       for(value--,newValue=i=0;i       {           newValue=(newValue<<1)+(value&1);           value>>=1;       }       printf("%d\n",newValue+base);   }   return 0; }

这篇关于NYOJ63小猴子的下落的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/960935

相关文章

面试or笔试6——小球下落距离

小东和三个朋友一起在楼上抛小球,他们站在楼房的不同层,假设小东站的楼层距离地面N米,球从他手里自由落下,每次落地后反跳回上次下落高度的一半,并以此类推知道全部落到地面不跳,求4个小球一共经过了多少米?(数字都为整数) 给定四个整数A,B,C,D,请返回所求结果。 测试样例: 100,90,80,70 返回:1020 根据极限的思想可直接求得单个小球的下落距离之和为3*N c

NYISTOJ 63 小猴子下落 二叉树

小猴子下落 时间限制:3000 ms  |  内存限制:65535 KB 难度:3 描述 有一颗二叉树,最大深度为D,且所有叶子的深度都相同。所有结点从左到右从上到下的编号为1,2,3,·····,2的D次方减1。在结点1处放一个小猴子,它会往下跑。每个内结点上都有一个开关,初始全部关闭,当每次有小猴子跑到一个开关上时,它的状态都会改变,当到达一个内结点时,如果

Algorithm学习笔记 --- 小球下落问题(二叉树解法)

有一颗二叉树,最大深度为D,且所有的叶子深度都相同。所有的结点从上到下从左到右编号为 1,2,3,4,....,2^D-1.在结点1处放一个小球,它会往下落。每个结点上都有一个开关,初始全部关闭,当每次有小球落到一个开关上时,它的状态都会改变。当小球到达一个内结点时,如果该结点上的开关关闭,则往左走,否则往右走,知道走到叶子结点。 一些小球从结点1处开始下落,最后一个小球会落到哪里呢?输入叶子深

【小球下落反弹】小球自由落下,每次落地后反跳回原高度的一半

一小球从100米高度自由落下,每次落地后反跳回原高度的一半;再落下,求它在第10次落地时,共经过多少米?第10次反弹多高? 使用C语言实现,具体代码: #include<stdio.h>int main(){float sn=100.0,hn=sn/2;for(int n=2;n<=10;n++){sn=sn+2*hn;hn=hn/2;}printf("共经过%f米\n第10次反弹%f米高",

NYOJ 63 小猴子下落 二叉树之满二叉树

小猴子下落 时间限制: 3000 ms  |  内存限制: 65535 KB 难度: 3 描述 有一颗二叉树,最大深度为D,且所有叶子的深度都相同。所有结点从左到右从上到下的编号为1,2,3,·····,2的D次方减1。在结点1处放一个小猴子,它会往下跑。每个内结点上都有一个开关,初始全部关闭,当每次有小猴子跑到一个开关上时,它的状态都会改变,当到达一个内结点时,如果开

63 小猴子下落

小猴子下落 时间限制: 3000 ms  |  内存限制: 65535 KB 难度: 3 描述 有一颗二叉树,最大深度为D,且所有叶子的深度都相同。所有结点从左到右从上到下的编号为1,2,3,·····,2的D次方减1。在结点1处放一个小猴子,它会往下跑。每个内结点上都有一个开关,初始全部关闭,当每次有小猴子跑到一个开关上时,它的状态都会改变,当到达一个内结点

Flutter-自定义表情雨下落动画

简述 今天给大家分享一个Flutter的表情雨的实现,具体的效果见下图,这个效果其实是工作中的一个小小的需求,这里面单独拿出来讲讲下这个效果的实现思路。 在以前特别是新手,遇到一些动画效果都是拿到需求后,在网络上去找寻类似的效果,然后修改修改就可以了,不知道你们是不是呢?其实从chatgpt出来以后,很多时候对于这种效果我们其实直接就可以问下gpt,gpt会给我们一些思路,只要我们表达的清晰,

unity体感游戏--接钻石游戏(一)游戏物体下落

之前完成一个体感接钻石的小游戏,大体过程就是天上掉钻石,用一个物体接住,这个物体是通过kinect来控制的他的前后左右。接到不同的钻石就可以获得不同的得分。 这段代码是下落的位置,下落的游戏物体,还定义了ScoreHit()得分。主要解决海上下落问题,此脚本具有通用性。 using UnityEngine;using System.Collections.Generic;public c

three.js 物体下落动画(重力加速度)

效果: <template><div><el-container><el-main><div class="box-card-left"><div id="threejs" style="border: 1px solid red"></div><el-button @click="loopFun"> 物体下落动画(重力加速度) </el-button><el-button @click="

ANSI Escape Sequence 下落的方块

ANSI Escape Sequence 下落的方块 1. ANSI Escape 的用途 无意中发现 B站有人讲解, 完全基于终端实现俄罗斯方块。 基本想法是借助于 ANSI Escape Sequence 实现方方块的绘制、 下落动态效果等。对于只了解 ansi escape sequence 用于 log 的颜色打印的人来说, 这无疑是拓宽了认识。 这一篇简单的列一下 ansi e