POJ 2903 BST 解题报告

一、问题描述

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.

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³¹ - 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

 

二、解题思路

看到这个结构，我想起了树状数组里的int Lowbit(int x)函数，这个函数的计算结果是2^k，其中k是x的二进制数表示的后面连续0的个数。那么2^k就是x所管区间的元素个数。比如上图所示，以8为根的子树一共有8个元素（包括它自己）。那么以8为根的子树中最小的数是8-2^k+1，问题关键在于求2^k。可以通过位来求：

int Lowbit(int x)

{

    return x&(x^(x-1));// return x&(-x);

}

求到最小的数和求最大数就方便了，最小数加最大数的和是x的两倍。

三、代码

 

#include<iostream>
using namespace std;
int Lowbit(int x)
{
    //return x&(x^(x-1));
    return x&(-x);
}
int GetLowest(int x)
{
    return x-Lowbit(x)+1;
}
int main()
{
    int N;
    int i;
    int a;
    cin>>N;
    for(i=0;i<N;++i)
    {
        cin>>a;
        int t=GetLowest(a);
        cout<<t<<" "<<a*2-t<<endl;

    }
    return 0;
}