hdu 5524 二叉树找规律，二进制相关

input

n 1<=n<=1e18

output

有n个结点的满二叉树有多少个不相同结点数的子树

做法：树有h=log2(n)层，最多有2h-2种(1除外),然后再n减去u重复的即可

 1 #include <bits/stdc++.h>
 2 #include <cstdio>
 3 #include <queue>
 4 #include <cstring>
 5 #include <iostream>
 6 #include <cstdlib>
 7 #include <algorithm>
 8 #include <vector>
 9 #include <map>
10 #include <set>
11 #include <ctime>
12 #include <cmath>
13 #include <cctype>
14 #include <string>
15 #include <bitset>
16 #define MAX 100000
17 #define LL long long
18 using namespace std;
19 LL n;
20 int highbit(LL x)
21 {
22     for(int i=63;i>=0;i--) if(x&(1LL<<i)) return i+1;
23 }
24 int lowbit(LL x)
25 {
26     for(int i=0;i<=63;i++) if(x&(1LL<<i)) return i;
27 }
28 int main()
29 {
30     freopen("in","r",stdin);
31     //scanf("%d",&T);
32     while(scanf("%lld",&n)==1)
33     {
34         int h=highbit(n);
35         LL maxn=(1LL<<h)-1;LL mid=maxn-(1LL<<(h-2>=0?h-2:0));
36 //        printf("%lld:",n);
37 //        printf("h=%d maxn=%lld mid=%lld
",h,maxn,mid);
38         if(n==maxn||n==mid) { printf("%d
",h);continue; }
39         h+=h-2;
40         if(n<=mid) h--;
41         h-=lowbit(n-(maxn>>1));
42         printf("%d
",h);
43     }
44     //printf("time=%.3lf",(double)clock()/CLOCKS_PER_SEC);
45     return 0;
46 }

View Code