HDU 5573 – Binary Tree [构造法]

Link

点击打开hdu题目链接

Problem

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 nodex, 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.

Mean

就是有一个完全二叉树,按照编号标好,根节点为1,左儿子编号是2×i,右儿子编号是2×i+1。然后给你一个数字N,从树根节点1走K补,每到一个节点可以加也可以减,让你凑出N来。题目保证一定有解。

Analyse

2015ACM/ICPC上海站的铜牌题,很遗憾最后没有时间了,没有做出来(就算有时间也不一定做出来……我当时一直在二进制上想,思路很乱…)。

这道题其实看数据范围有一个关键点就是N<=2^K,这样可以打表一下,走K步能够凑出哪些数来。顺着树左边走可以发现,走K步能凑出2^K以内的所有奇数。而且凑的方法可以是:第K个取正,上面的K-1个从下往上根据当前值与N的关系凑出即可。

对于偶数的情况,第K个取原来的兄弟节点,取正,这样就比原来奇数情况大1了。

C++ Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll n, k;
list<ll> res;

int main() {
    ll T, kase = 0; scanf("%lld", &T);
    while(T--) {
        scanf("%lld%lld", &n, &k);
        res.clear();
        if(n % 2) {
            ll cur = 1LL << (k-1), sum = 1LL << (k-1);
            res.push_front(cur);
            while(sum != n) {
                cur >>= 1;
                if(sum < n) {
                    res.push_front(cur);
                    sum += cur;
                } else {
                    res.push_front(-cur);
                    sum -= cur;
                }
            }
        } else {
            n -= 1;
            ll cur = 1LL << (k-1), sum = 1LL << (k-1);
            res.push_front(cur+1);
            while(sum != n) {
                cur >>= 1;
                if(sum < n) {
                    res.push_front(cur);
                    sum += cur;
                } else {
                    res.push_front(-cur);
                    sum -= cur;
                }
            }
        }
        printf("Case #%lld:\n", ++kase);
        for(auto i : res) {
            if(i > 0) printf("%lld +\n", i);
            else printf("%lld -\n", -i);
        }
    }
    return 0;
}

欢迎留言