Subtrees

问题描述

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

输入描述

输入有多组数据，不超过1000组.

每组数据输入一行包含一个整数N.(1\leq N\leq {10}^{18})(1≤N≤1018)

输出描述

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

输入样例

输出样例

3

4

3

5

题解：  完全二叉树，。。。dfs下去分点就好了

///

#include<bits/stdc++.h>

using namespace std ;

typedef long long ll;

#define mem(a) memset(a,0,sizeof(a))

inline ll read()

{

    ll x=,f=;

    char ch=getchar();

    while(ch<''||ch>'')

    {

        if(ch=='-')f=-;

        ch=getchar();

    }

    while(ch>=''&&ch<='')

    {

        x=x*+ch-'';

        ch=getchar();

    }

    return x*f;

}

//****************************************

#define maxn 100000+5

#define mod 1000000007

ll n;

set<ll > s;

void dfs(ll x){

   if(x==)return ;

   if(s.count(x)){

       return ;

   }

   s.insert(x);

   x--;

   dfs(x/);

   dfs(x/+x%);

}

int main(){

    while(scanf("%I64d",&n)!=EOF){

    s.clear();

    dfs(n);

    cout<<s.size()<<endl;

    }

   return ;

}

代码

巴特西

BestCoder Round #61 (div.2) C.Subtrees dfs

Subtrees

最新文章

热门文章