首页 > 代码库 > hdu 5524 Subtrees dfs
hdu 5524 Subtrees dfs
Subtrees
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Problem Description
There is a complete binary tree with N nodes.The subtree of the node i has Ai nodes.How many distinct numbers are there of Ai?
Input
There are multiple test cases, no more than 1000 cases.
For each case contains a single integer N on a line.(1≤N≤1018)
For each case contains a single integer N on a line.(1≤N≤1018)
Output
The output of each case will be a single integer on a line:the number of subtrees that contain different nodes.
Sample Input
5678
Sample Output
3435
Source
BestCoder Round #61 (div.2)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5524
题意：给你一颗n个节点的完全二叉树找出子树中个数不同的个数；
就是如果左子树和右子树相同只需要遍历一颗子树即可；
不同遍历两颗；
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<iostream>#include<cstdio>#include<cmath>#include<string>#include<queue>#include<algorithm>#include<stack>#include<cstring>#include<vector>#include<list>#include<set>#include<map>using namespace std;#define ll long long#define pi (4*atan(1.0))#define eps 1e-14#define bug(x) cout<<"bug"<<x<<endl;const int N=2e3+10,M=4e6+10,inf=2147483647;const ll INF=1e18+10,mod=1e9+7;/// 数组大小set<ll>ans;map<ll,ll>si;ll n;void dfs(ll x){ if(x>n)return; ll l=x,r=x; while(l*2<=n)l*=2; while(r*2+1<=n)r=r*2+1; if(l==x&&r==x) { si[x]=1; ans.insert(1); return; } if(l<=r) { dfs(x*2); si[x]=2*si[x*2]+1; ans.insert(si[x]); //cout<<x<<" "<<si[x]<<endl; } else { dfs(x*2); dfs(x*2+1); si[x]=si[x*2]+si[x*2+1]+1; //cout<<x<<" "<<si[x]<<" "<<si[x*2]<<" "<<si[x*2+1]<<endl; ans.insert(si[x]); }}int main(){ while(~scanf("%lld",&n)) { ans.clear(); si.clear(); dfs(1); printf("%d\n",ans.size()); } return 0;}
hdu 5524 Subtrees dfs
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。