小球下落(Dropping Balls,UVa 679)题解

╰+哭是因爲堅強的太久メ 2022-12-28 07:22 176阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入
     *  输出
 *  原题（PDF）
 *   *  算法分析
     *  解题标程

--------------------

# 题目描述 #

许多的小球一个一个的从一棵满二叉树上掉下来组成一个新满二叉树，每一时间，一个正在下降的球第一个访问的是非叶子节点。然后继续下降时，或者走右子树，或者走左子树，直到访问到叶子节点。

决定球运动方向的是每个节点的布尔值。最初，所有的节点都是 FALSE，当访问到一个节点时，如果这个节点是 FALSE，则这个球把它变成 TRUE，然后从左子树走，继续它的旅程。如果节点是TRUE，则球也会改变它为 FALSE，而接下来从右子树走。满二叉树的标记方法如下图。

因为所有的节点最初为 FALSE，所以第一个球将会访问节点 1，节点 2 和节点 4，转变节点的布尔值后在在节点 8 停止。第二个球将会访问节点 1、3、6，在节点 12 停止。明显地，第三个球在它停止之前，会访问节点 1、2、5，在节点 10 停止。

现在你的任务是，t组输入，后接t+2行，给定新满二叉树的深度 d 和下落的小球的编号 i ，可以假定I不超过给定的新满二叉树的叶子数，写一个程序求小球停止时的叶子序号p。

## 输入 ##

5
    4 2
    3 4
    10 1
    2 2
    8 128
    -1

## 输出 ##

12
    7
    512
    3
    255

--------------------

# 原题（PDF） #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]

--------------------

## 算法分析 ##

解题关键：**对于一个结点k，其左子结点、右子结点的编号分别是 2k 和 2k+1**

> **算法1:**  
> 用tree\[1<<20\]来存最大深度为20的二叉树中的所有结点，记录结点的true和false值，通过这个来判断走左还是走右，但是*这个算法如果小球数量很多，深度大，那么算法的时间就会很高，导致超时*  
> **算法2:**  
> *只用知道当前结点在什么时候会进入左子树，什么时候会进入右子树，那么就不需要去记录每个结点的bool值*  
> 例如对于第一个结点1而言，当落在结点1的小球的编号为奇数时，就进入左子树。当落在结点1的小球的编号为偶数时，就进入右子树，**同理到第二层时，也判断进入左子树还是右子树，并且规则是相同的**  
> 这里要注意：每次二分时，左右两个掉入的小球数，应该是均分的，因此当小球数为奇数时下一层小球数为 ( I = ( I + 1 ) / 2 )，当小球数为偶数时下一层小球数为 ( I = I / 2 )  
> **算法的时间复杂度就只和层数d相关，而与小球数i无关**

## 解题标程 ##

//
    //  main.cpp
    //  uva679
    //
    //  Created by 陈洋 on 2019/10/18.
    //  Copyright © 2019 陈洋. All rights reserved.
    //
    
    #include <stdio.h>
    #include <string.h>
    
    int t[1<<20];
    
    int main()
    {
        
        int t,n,m;  //多组输入t,树的深度为n,小球数为m
        
        scanf("%d",&t);
        t++;
        while(t--){
        
            scanf("%d",&n);
            if(n==-1)
                continue;
            scanf("%d",&m);
            int k=1;
                
            for(int i=0;i<n-1;i++){
        
                if(m%2){
        
                    k=k*2;
                    m=(m+1)/2;
                }
                else{
        
                    k=k*2+1;
                    m=m/2;
                }
            }
                
            printf("%d\n",k);
        }
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]: /images/20221120/0e1f6e57008140c0877f1cef2ffc9bc4.png