Binary Tree （构造）

Binary Tree （构造）

The Old Frog King lives on the root of an infinite tree. According to the law, each node should connect to exactly two nodes on the next level, forming a full binary tree. Since the king is professional in math, he sets a number to each node. Specifically, the root of the tree, where the King lives, is 1. Say froot = 1. And for each node u, labels as fu, the left child is fu × 2 and right child is fu × 2 + 1. The king looks at his tree kingdom, and feels satisfied. Time flies, and the frog king gets sick. According to the old dark magic, there is a way for the king to live for another N years, only if he could collect exactly N soul gems. Initially the king has zero soul gems, and he is now at the root. He will walk down, choosing left or right child to continue. Each time at node x, the number at the node is fx (remember froot = 1), he can choose to increase his number of soul gem by fx, or decrease it by fx. He will walk from the root, visit exactly K nodes (including the root), and do the increasement or decreasement as told. If at last the number is N, then he will succeed. Noting as the soul gem is some kind of magic, the number of soul gems the king has could be negative. Given N, K, help the King find a way to collect exactly N soul gems by visiting exactly K nodes. Input First line contains an integer T, which indicates the number of test cases. Every test case contains two integers N and K, which indicates soul gems the frog king want to collect and number of nodes he can visit. Restrictions: • 1 ≤ T ≤ 100. • 1 ≤ N ≤ 109 . • N ≤ 2 K ≤ 2 60 . Output For every test case, you should output ‘Case #x:’ first, where x indicates the case number and counts from 1. Then K lines follows, each line is formated as ‘a b’, where a is node label of the node the frog visited, and b is either ‘+’ or ‘-’ which means he increases / decreases his number by a. It’s guaranteed that there are at least one solution and if there are more than one solutions, you can output any of them. Sample Input 2 5 3 10 4 Sample Output Case #1: 1 + 3 - 7 + Case #2: 1 + 3 + 6 - 12 +

题目大概：

给你一棵二叉树，二叉树按行标号，然后标号就是二叉树的权值，给你一个数n，一个数k，让你用k层二叉树来构造出一个数n，必须一直向深处走，不能回头走，每到一个节点，可以加权值，也可以减权值。给出一种构造方案。

思路：

看到构造数n，然后二叉树的最左边又都是二进制数，很容易想到二进制数可以构造任何一个数。然后，这里不是能选和不能选，而是加和减，这就和我们的期望不一样了。

这样就想要让这些二进制数来加减抵消，来凑出这个n。然后可以先把最左边的二进制数求和为sum，然后sum-n。就得到了需要加减抵消的数，然后除2，就是需要是负数的数，直接从大到小暴力构造这个负数就行了。这样就只需要用左边这一样就能构造出n，但是当sum-n是奇数的时候，就需要+1，来使得刚好抵消，这样最后一个数就不能选择最左边的数，就需要右移一位。

代码：

#includeusing namespace std;#define ll long longconst int maxn=1e5+10;const int INF=0x3f3f3f3f;const int mod=1e9+7;int n,k;ll p[100];int ans=0;void init(){ ll sum_1=1; p[ans++]=sum_1; for(int i=1;i<=60;i++) { sum_1*=2; p[ans++]=sum_1; }}int vis[100];int main(){ int t; int tem=1; init(); scanf("%d",&t); while(t--) { scanf("%d%d",&n,&k); memset(vis,0,sizeof(vis)); ll sum=p[k]-1; sum-=n; int flag=0; if(sum%2==1) { sum++; flag=1; } sum/=2; for(int i=k-1;i>=0;i--) { if(sum>=p[i]) { sum-=p[i]; vis[i]=1; } } printf("Case #%d:\n",tem++); for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。