POJ2309 BST

POJ2309 BST

大家好,又见面了,我是全栈君。

 
Time Limit: 1000MS   Memory Limit: 65536KB   64bit IO Format: %lld & %llu

Description

Consider an infinite full binary search tree (see the figure below), the numbers in the nodes are 1, 2, 3, …. In a subtree whose root node is X, we can get the minimum number in this subtree by repeating going down the left node until the last level, and we can also find the maximum number by going down the right node. Now you are given some queries as “What are the minimum and maximum numbers in the subtree whose root node is X?” Please try to find answers for there queries. 



POJ2309 BST

Input

In the input, the first line contains an integer N, which represents the number of queries. In the next N lines, each contains a number representing a subtree with root number X (1 <= X <= 2 
31 – 1).

Output

There are N lines in total, the i-th of which contains the answer for the i-th query.

Sample Input

2
8
10

Sample Output

1 15
9 11

Source

POJ Monthly,Minkerui
 
用树状数组的lowbit处理即可。(x&-x)可以取出x二进制表示下的最后一个1,即可知x的管辖半径。
 1 /*by SilverN*/
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 using namespace std;
 8 int read(){
 9     int x=0,f=1;char ch=getchar();
10     while(ch<'0' || ch>'9'){
     
     if(ch=='-')f=-1;ch=getchar();}
11     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
12     return x*f;
13 }
14 int lowbit(int x){
     
     return x&-x;}
15 int T;
16 int n;
17 int main(){
18     T=read();
19     while(T--){
20         n=read();
21         printf("%d %d\n",n-lowbit(n)+1,n+lowbit(n)-1);
22     }
23     return 0;
24 }

 

转载于:https://www.cnblogs.com/SilverNebula/p/5889498.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/108872.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Weblogic SSRF漏洞[通俗易懂]

    Weblogic SSRF漏洞[通俗易懂]1.漏洞描述weblogic中存在SSRF漏洞,利用该漏洞可以发送任意HTTP请求,进而攻击内网中redis、fastcgi等脆弱组件。2.影响版本weblogic10.0.2–10.3.6版本3.POChttp://192.168.42.145:7001/uddiexplorer/SearchPublicRegistries.jsp?rdoSearch=name&txtSearchname=sdf&txtSearchkey=&txtSear…

  • ORM学员管理系统单表查询示例

    前期准备工作首先创建好一个项目一:必须使用MySQL创建一个库因为ORM只能对表和数据进行处理,所以库必须自己创建二:进行相关的配置一:二:三:四:五:三创建表必须注意一下俩点

  • C++Qt入门(1)—Qt简介,第一个Qt程序,Qt按钮

    C++Qt入门(1)—Qt简介,第一个Qt程序,Qt按钮文章目录一、QT简介1.什么是QT?2.Qt的发展史?二、第一个Qt程序1.路径名,文件名中不能有中文2.创建默认窗口类3.main函数4.对.pro文件的解释5.QtCreator快捷键6.QPushButton的创建7.对象树(了解)8.QT中的坐标系一、QT简介1.什么是QT?Qt是一个跨平台的C++图形用户界面应用程序框架2.Qt的发展史?1991年Qt最早由奇趣科技开发1996年进入商业领域,是目前流行的Linux桌面环境KDE的基础……(略)3.Qt支持的平台4.Qt的下载与

  • Python基础常见面试题总结[通俗易懂]

    Python基础常见面试题总结[通俗易懂]以下是总结的一些常见的Python基础面试题,帮助大家回顾基础知识,了解面试套路。会一直保持更新状态。PS:加粗为需要注意的点。基础知识题1、深拷贝和浅拷贝的区别是什么?深拷贝是将对象本身复制给另一个对象。这意味着如果对对象的副本进行更改时不会影响原对象。浅拷贝是将对象的引用复制给另一个对象。因此,如果我们在副本中进行更改,则会影响原对象。**2、能否解释一下*args和kwar…

    2022年10月21日
  • PYCHAR激活码(破解版激活)

    PYCHAR激活码(破解版激活),https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号