POJ 2309 BST

此题一看,树状数组里神奇的 n & -n 就派上用场了。

输入你,输出 n-(n&-n)+1 和 n+(n&-n)-1 即可。

当然可以用一个递归来划分区间。同样我也写了一下。。比上面的方法可慢了不少。。

# include <iostream>
using namespace std;

int t, n;

void dfs(long long root, long long min, long long max)
{
    if ( root == n )
    {
        cout << min << " " << max << endl;
        return;
    }
    if ( n < root )
        dfs((root+min)>>1, min, root-1);
    else dfs( ((root+max)>>1)+1, root+1, max );
}

int main()
{
    cin >> t;
    while ( t-- )
    {
        cin >> n;
        dfs((1<<30), 1, 2147483647);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>