给出一棵二分搜索树,再给一个节点编号n,求以这个节点为根节点的子树叶子节点的最大值与最小值。若n是奇数,那么他必然是个叶子节点,最大最小都是他自己。否则求n所在的层数,他的层数就是他的因子中2的个数(规律),转化为求n的因子中2的个数。而2的个数取决于n的二进制表示中最后一个1所处的位置i,因为之前的某几个1,假设处于j(j>i),那么n可以表示为2^j+2^i+2^x(x>i且个数未定)=2^i*(1+2^(j-i)+2^(x-i)),看见米有,n必须有i个因子2.求出i的值后,即层数,可得n的左右各有num=2^i-1个儿孙(女),不信请看图,概不解释。那么最小值就是n-num,最大值就是n+num.那马怎么求num呢,这时就可以请出神奇的位运算了(以速度"嗖嗖嗖"的快而扬名ACM界),首先是确定二进制n后缀连续0的个数,这样想:怎么取出这i个0呢?其实不必考虑这个掣肘的问题,咱们直接跑到结果上考虑,就是求2^i-1,你花仙米有,这是个等差数列的前n项和:2^0+2^1+2^2+……+2^(i-1).那么这又是个什么形式呢,这就是二进制只有连续i个1的(其余都是前导0)数的十进制表示形式,OK,好办了,利用系统自动转换功能,咱们只需把这i个1罗列出来即可:把n的后i个0变成1,可采取如下形式n^(n|n-1),稍微解释下,n|n-1是将后i个0变成1,把第i+1个1变成0,然后和n抑或一下,得到什么?哈,就是2^i-1,即i个1的十进制形式,代码就不放了,上面明白了实现很简单的!
那啥,转载务必注明:Pzjay原创呃!
本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/shifuwawa/archive/2010/01/07/5153446.aspx
以下是我根据上面的描述写出来的代码,一次AC,0MS
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
while(n--)
{
int k;
cin>>k;
if(k%2!=0)
{
cout<<k<<" "<<k<<endl;
continue;
}
int num=k^(k|k-1);
cout<<k-num<<" "<<k+num<<endl;
}
return 0;
}
posted on 2010-08-19 13:13
崔佳星 阅读(1075)
评论(0) 编辑 收藏 引用 所属分类:
POJ