Binary Tree HDU - 5573 （思维）
发布时间：2020-12-14 04:33:30 所属栏目：大数据 来源：网络整理
导读：题目链接： B - Binary Tree ? HDU - 5573? 题目大意： 给定一颗二叉树，根结点权值为1，左孩子权值是父节点的两倍，右孩子是两倍+1； 给定?n?和?k，让你找一条从根结点走到第k层的路径，每经过一个结点，必须加上或者减去其权值，最后得到的结果是n； 具体
题目链接：B - Binary Tree?HDU - 5573?题目大意： 给定一颗二叉树，根结点权值为1，左孩子权值是父节点的两倍，右孩子是两倍+1； 给定?n?和?k，让你找一条从根结点走到第k层的路径，每经过一个结点，必须加上或者减去其权值，最后得到的结果是n； 具体思路：因为每个点都需要用到，所以我们先假设所有的点都需要用到，这个时候就全部是"+"号，然后通过二进制的性质，能够凑齐范围内的所有数，然后我们算一下差值还有多少，然后再减去这个差值就好了。 AC代码： 1 #include<bits/stdc++.h> 2 using namespace std; 3 # define ll long long 4 # define inf 0x3f3f3f3f 5 const int maxn = 65; 6 ll a[maxn],sum[maxn]; 7 ll ans[maxn]; 8 int vis[maxn]; 9 void init() 10 { 11 a[1]=1ll; 12 sum[1]=a[1]; 13 for(int i=2; i<=60; i++) 14 { 15 a[i]=a[i-1]*2ll; 16 sum[i]=sum[i-1]+a[i]; 17 } 18 } 19 int main() 20 { 21 int T,Case=0,tt; 22 init(); 23 scanf("%d",&T); 24 while(T--) 25 { 26 ll n,k; 27 scanf("%lld %lld",&n,&k); 28 printf("Case #%d:n",++Case); 29 ll tmp=sum[k]-n; 30 if(tmp&1) 31 tmp=(tmp+1)>>1,ans[k]=a[k]+1; 32 else 33 tmp>>=1,ans[k]=a[k]; 34 vis[k]=1; 35 for(int i=k-1; i>=1; i--) 36 { 37 ans[i]=a[i]; 38 if(tmp>=a[i]) 39 { 40 tmp-=a[i]; 41 vis[i]=0; 42 } 43 else 44 vis[i]=1; 45 } 46 for(int i=1; i<=k; i++) 47 { 48 printf("%lld %cn",ans[i],vis[i]==0? ‘-‘ : ‘+‘ ); 49 } 50 } 51 return 0; 52 }
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |