SZTUOJ 1024.在二叉树寻求邂逅是否搞错了什么

Description

著名的zjb学长不曾说过:“邂逅一个心仪的女孩子比在二叉树上找一个节点要容易的多。”现在给你 n 个节点编号和一个完全二叉树(如图),请你求出这些节点的层数。设定根节点为第一层,其子节点为第二层,依此类推。
SZTUOJ 1024.在二叉树寻求邂逅是否搞错了什么

Input

输入的第一行为一个整数 n ,代表有 n 个节点。从第 2 行到第 n+1 行各有一个整数ai,表示待求的节点编号

Output

输出为n行,每行有一个整数,表示第 i 个节点的层数 Ci

Sample Input

5
3
5
1
8
2

Sample Output

2
3
1
4
2

Hint

1 ≤ n ≤ 106 1 ≤ ai ≤ 231-1 在输入输出时使用cin/cout可能会超时,请尽量使用scanf/printf输入输出或采用其他快读方式

Source

SZTU Monthly 2020 Oct.

Author

DOGGOD_Q

题目解析

这道题只考察了二叉树最基本的性质,就是二叉。换句话说。在完全二叉树上,编号为k的节点的子节点编号分别为 2k 和 2k+1 我们根据每个数可以除2几次来判断他所在的层数,代码实现没有太大难度

#include <bits/stdc++.h>
using namespace std;
int n;
int main()
{
    int n;
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        int num;
        scanf("%d", &num);
        int ans = 1;
        while(num >>= 1)ans++;
        printf("%d\n", ans);
    }
    return 0;
}

SZTUOJ 1024.在二叉树寻求邂逅是否搞错了什么

上一篇:记录 A表与B表中最新的一条数据关联(例子工单表与工单回访表)和 PageHelper插件丢失order by语句


下一篇:Maya script 根据 face id 获得 material list