BinaryTree(HDU-5573)【思维/构造】
发布时间:2020-12-14 04:39:10 所属栏目:大数据 来源:网络整理
导读:题目链接:https://vjudge.net/problem/HDU-5573 题意:一棵二叉树,编号代表对应节点的取值,可以走k步,每次走的层数递增,问能够达到N的方案。 思路:首先看一下数据范围, N ≤ 2^ K ≤ 2^ 60 , 因此,由这颗二叉树从左往右数第一二支即可得到N的最大值
题目链接:https://vjudge.net/problem/HDU-5573 题意:一棵二叉树,编号代表对应节点的取值,可以走k步,每次走的层数递增,问能够达到N的方案。 思路:首先看一下数据范围,N≤2^K≤2^60, 因此,由这颗二叉树从左往右数第一二支即可得到N的最大值。 当答案的路径在最左侧一支时,设sum=2^k-1,t为要减去的那部分数字的和,则N=sum-2*t,t能取到0-sum/2之间所有的值,则此时也可以得到所有的奇数N, 同理,当答案的路径在左数第二支时,设sum=2^k,t同上,则N=sum-2*t,t能取到0-sum/2之间所有的值,则此时可以得到所有的偶数N。 此时,设s=sum-N,若s%2==0,则可以直接求取路径,若s为奇数,则sum++后求取。 代码如下: 1 #include<cstdio> 2 3 using namespace std; 4 5 int main(){ 6 int t,n,k; 7 long long ha,tp=1; 8 scanf("%d",&t); 9 for(int i=1;i<=t;i++){ 10 scanf("%d%d",&n,&k); 11 printf("Case #%d:n",i); 12 ha=1; 13 ha<<=k; 14 ha-=1; 15 ha-=n; 16 if(ha%2==0){ 17 ha/=2; 18 for(int i=0;i<k;i++){ 19 if(ha&(1<<i)){ 20 printf("%I64d -n",(tp<<i)); 21 } 22 else printf("%I64d +n",(tp<<i)); 23 } 24 } 25 else { 26 ha++; 27 if(!(ha&(1<<(k-1)))){ 28 ha/=2; 29 for(int i=0;i<k-1;i++){ 30 if(ha&(1<<i)){ 31 printf("%I64d -n",(tp<<i)); 32 } 33 else printf("%I64d +n",(tp<<i)); 34 } 35 printf("%d +n",(1<<(k-1))+1); 36 } 37 else { 38 long long ha2=ha-2; 39 ha2/=2; 40 for(int i=0;i<(k-1);i++) 41 if(ha2&(1<<i)) 42 printf("%I64d +n",(tp<<i)); 43 else printf("%I64d +n",(tp<<i)); 44 printf("%I64d -n",(tp<<(k-1))+1); 45 } 46 } 47 } 48 return 0; 49 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |