Full Binary Tree(sdut 2882)
2024-09-04 16:27:41
Problem Description:
In computer science, a binary tree is a tree data structure in which each node has at most two children. Consider an infinite full binary tree (each node has two children except the leaf nodes) defined as follows. For a node labelled v its left child will be labelled 2 * v and its right child will be labelled 2 * v + 1. The root is labelled as 1.
You are given n queries of the form i, j. For each query, you have to print the length of the shortest path between node labelled i and node labelled j.
Input
First line contains n(1 ≤ n ≤ 10^5), the number of queries. Each query consists of two space separated integers i and j(1 ≤ i, j ≤ 10^9) in one line.
Output
For each query, print the required answer in one line.
Sample Input
5
1 2
2 3
4 3
1024 2048
3214567 9998877
题解 只要找到公共节点即可,水题一个;
#include<stdio.h>
#include<string.h>
int main()
{
long long int i,j,a,b,m,n,p;
scanf("%lld",&p);
for(int k=;k<p;k++)
{
scanf("%lld%lld",&a,&b);
m=a>b?a:b;
n=a>b?b:a;
long long int count1=,count2=;
while(m!=n)
{
if(n>m)
n/=;
if(m==n)
break;
if(m>n)
m/=;
}//找到公共节点;
while(a!=m)
{
a/=;
count1++;
}
while(b!=m)
{
b/=;
count1++;
}//统计下每一节点到公共节点的距离
printf("%lld\n",count1); }
return ;
}
最新文章
- [LeetCode] Permutations 全排列
- 取字符串拼音首字母(js)
- ios创建自定义控件必须具备的三个方法
- Firefox每次刷新时自动清空缓存的设置方法
- mysql存储图片问题
- SQLite 批量insert - 如何加速SQLite的插入操作
- DEDE的data目录名称修改方法
- git的工作流程(分支合并)
- mybatis 报错:Caused by: java.lang.NumberFormatException: For input string
- 除去内容中的HTML代码方法
- Java 异常解决之java.lang.IllegalArgumentException: Comparison method violates its general contract!
- Oracle编码
- ssl证书部署问题
- 【转】C语言中,为什么字符串可以赋值给字符指针变量
- redmine添加自定义问题状态
- set, unordered_set模板类
- IOS马甲包(诚招大量开发)
- LFS搭建第一天
- flask总结02
- div clear清除浮动产生的影响 被受影响的div加上清除浮动后 不会填充前一个div浮动后空出的位置