首页 > 其他分享 >Uva--679 Dropping Balls(二叉树的编号)

Uva--679 Dropping Balls(二叉树的编号)

时间:2023-04-16 23:57:18浏览次数:59  
标签:左子 Balls 679 int 小球 二叉树 TLE include

记录
23:28 2023-4-16

https://onlinejudge.org/external/6/679.pdf

reference:《算法竞赛入门经典第二版》例题6-6

二叉树,这里是完全二叉树,使用模拟的方式应该会TLE(虽然我用模拟的方式也TLE了,但不是这个原因,下面会提到原因)
不用模拟的方式,转换思路,使用递归的方式去思考。
这里是完全二叉树,使用数组模拟完全二叉树。
对于每个小球,肯定会经过根节点(先考虑D=1的时候的根节点)(在数组完全二叉树中位置为1),对于这个根节点来说,标号为奇数的小球肯定走左子树,为偶数的小球肯定走右子树。
对于走左子树的小球,此时把左边这个做为新的根节点(D=2,在数组完全二叉树中位置为2),继续对进入左边的小球进行判断,奇数继续走左子树,偶数继续走右子树。

小球编号 1 2 3 4
数组下标为1作为根 1(走1的左子树) 1(走1的右子树) 2(走1的左子树) 2(走1的右子树)
数组下标为2作为根 1(走2的左子树) 2(走2的右子树)

我TLE的原因是,书上和Uva网站上的题不是相同的。。输入就是有问题的。。还是要看原来的题的表述

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<set>
#define MAX_N 20
using namespace std;
typedef long long ll;
typedef unsigned int uint;
const int INF = 0x3f3f3f3f;
int arr[1 << MAX_N];
int N, D, I;

void solve() {
    fill(arr, arr + (1 << MAX_N), 0);
    int k = 1, n = (1 << D) - 1;
    for(int i = 0; i < I; i++) {
        k = 1;
        for(;;) {
            arr[k] = !arr[k];
            k = arr[k]? 2 * k : 2 * k + 1;
            if(k > n) break;
        }
    }
    printf("%d\n", k / 2);
}

void solve1() {
    int k = 1;
    for(int i = 0; i < D-1; i++) {
        if(I % 2 == 1) {
            k = k * 2;
            I = (I + 1) / 2;  
        } else {
            k = k * 2 + 1;
            I = I / 2;
        }
    }
    printf("%d\n", k);
}

//solve 会TLE
int main() {
    scanf("%d\n", &N);
    for(int i = 0; i < N; i++){
        scanf("%d%d", &D, &I);
        solve1();
    }
    // while (scanf("%d%d", &D, &I) == 2) {
    //     solve1();
    // }
}

标签:左子,Balls,679,int,小球,二叉树,TLE,include
From: https://www.cnblogs.com/57one/p/17324483.html

相关文章

  • 平衡二叉树——C语言描述——创建,增加结点
    平衡二叉树——C语言描述——创建,增加结点目录平衡二叉树——C语言描述——创建,增加结点0测试用例框架1定义2数据结构2增加平衡二叉树的结点(1)代码(2)测试用例0测试用例框架https://blog.csdn.net/m0_59469991/article/details/127137119?csdn_share_tail=%7B%22type%22%3A%2......
  • 数据结构-->二叉树 OJ_01
    经过前几期浴血奋战!!二叉树便要进入应用阶段了!今天,为大家带来几道OJ题的讲解!1.单值二叉树如果二叉树每个结点都具有相同的值,那么该二叉树就是单值二叉树只有给定的树是单值二叉树时,才会返回true,否则返回false下面为了方便理解,进行图解举例:>有上述的两种情况,其中还需要考虑到......
  • 算法-二叉树的构造
    namespaceBinary;publicclassBinaryTree{publicNode<char>Head{get;privateset;}privatestringcStr{get;set;}publicBinaryTree(stringconstructStr){this.cStr=constructStr;th......
  • 二叉树遍历算法分析
    二叉树遍历算法分析前/中/后序遍历算法可以发现这三种遍历算法只有一行代码,也就是输出结点数据域的位置不同前序遍历是先输出数据域再递归到左孩子和右孩子中序遍历是先递归到左孩子等返回的时候输出数据域再递归到右孩子后序遍历是指先递归到左孩子,然后递归到右孩子,最后......
  • 数据结构-->二叉树_02
    今天,接着上一期的博文,继续推进!!请看下面的的代码:>求一棵树的高度,为何需要存储起来呢?解答这个问题之前,需要稍微改动一下,上述的代码!会发现上述代码有很大的好处!//二叉树的高度intTreeHight(BTNode*root){ if(root==NULL){ return0;}returnTreeHight(root->l......
  • 二叉树的创建和中序及后序遍历
    二叉树的创建和中序及后序遍历二叉的先序创建使用#号来表示该结点为null实现代码先进行先序创建然后进行先序遍历#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<vector>#include<cstring>#include<unordered_set>#includ......
  • 【数据结构】二叉树的基本操作与遍历(C语言)
     目录定义满二叉树 完全二叉树性质应用计算二叉树结点个数 计算叶子结点的个数第 k层结点的个数查找值为x的节点遍历前序遍历中序遍历后序遍历层序遍历判断是否为完全二叉树定义......
  • 树的遍历-二叉树
    给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。输入格式:输入第一行给出一个正整数N(≤30),是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。输出格式:在一行中输出该树的层序遍......
  • 二叉树遍历(102.144.94.145)
    102.二叉树的层序遍历BPS/***Definitionforabinarytreenode.*structTreeNode{*intval;*TreeNode*left;*TreeNode*right;*TreeNode():val(0),left(nullptr),right(nullptr){}*TreeNode(intx):val(x),left(nullptr)......
  • UVA - 699 The Falling Leaves 二叉树
    题目:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=19244题意:给定一棵二叉树,把根节点标号成0,然后每往左走标号就减1,每往右走标号就加1,问相同标号的节点的值得和,按标号的大写依次输出思路:输入挺坑的,不过看了一会,可以边输入边建树,碰到其他值要接着往下递归建树,碰到-1......