poj2309
题目地址点击打开链接
主旨大意：
给出一个数，写出以它为根节点的最小数和最大数
思路：
- 给出一棵二分搜索树，再给一个节点编号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的十进制形式！
- #include <cstdio>
- #include <math.h>
- using namespace std;
- int main(){
- int nCase;
- scanf("%d",&nCase);
- while(nCase--){
- int n;
- scanf("%d",&n);
- int k=n&(-n);
- k--;
- printf("%d %dn",n-k,n+k);
- }
- return 0;
- }
普通方法：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int left(int a, int b)
{return b ? left(a - b, b >> 1) : a;}
int right(int a, int b)
{return b ? right(a + b, b >> 1) : a;}
int main()
{int T, a, b;for(scanf("%d", &T); T --; ){scanf("%d", &a);b = 1;while(a % b == 0)b <<= 1;//跳出后 b = 2 ^ ( a中2因子个数 + 1)printf("%d %dn", left(a, b >> 2), right(a, b >> 2));//b>>2是a每次要减去的数 ，b>>2 = 2 ^ (a中2因子个数 - 1)
}return 0;
}
