Subtrees

 

 Accepts: 60

 

 Submissions: 170

 Time Limit: 2000/1000 MS (Java/Others)

 

 Memory Limit: 131072/131072 K (Java/Others)

问题描述

一棵有N个节点的完全二叉树，问有多少种子树所包含的节点数量不同。

输入描述

输入有多组数据，不超过1000组.每组数据输入一行包含一个整数N.(1\leq N\leq {10}^{18})(1≤N≤1018)

输出描述

对于每组数据输出一行，表示不同节点数的子树有多少种.

输入样例

5678

输出样例

3435

一颗完全二叉树，左右子树都会为完全二叉树，其中必然有一个最后一层是满的。对于最后一层是满的完全二叉树，每一层的节点的子树形态都是相同的，只统计logN种，然后递归处理另一颗子树。最后对记录下的所有子树根据节点数判重.

这道题想了很久，果然递归真的是省事啊。。。

网上的题解完全看不懂什么意思，之前也一直不敢写递归，总怕出错。这次敲完爽翻了。我真是太弱了。。。这道题兴奋半天。。。

具体解释见代码：

#pragma warning(disable:4996)  #include 
    
       #include 
     
        #include 
      
         #include 
       
          #include 
        
           #include 
         
          #include 
          
           using namespace std;typedef long long ll;ll n;set
           
            an;void solve(ll x){ if (x <= 0) return; if (x == 1) { an.insert(0); return; } int i; ll num, k, nn, nk; for (i = 0; i <= 60; i++) { num = (1LL << i); if ((num - 1) == x)//中奖了，是满二叉树(其实早晚会中奖......) { k = 0; nn = 2; while (k + 1 <= x) { an.insert(k); k = k + nn; nn = nn << 1; } return; } if (num >= x) { break; } } an.insert(x - 1); i--; nn = (1LL << i) - 1;//除去最后一层的节点数 k = x - nn;//最后一层的节点数 nk = ((1LL << i) >> 1);//最后一层应该有的一半节点数 ll temp = (nn - 1) >> 1; ll le, ri; if (k <= nk) { le = temp + k;//搜索左子树节点 ri = temp;//搜索右子树节点 } else { le = temp + nk; ri = temp + k - nk; } solve(le); solve(ri);}int main(){ //freopen("i.txt", "r", stdin); //freopen("o.txt", "w", stdout); while (cin >> n) { an.clear(); solve(n); cout << an.size() << endl; } //system("pause"); return 0;}