hdu5573 Binary Tree 题解

题意：

老青蛙国王住在一棵无限大树的根部。根据法律，每个节点应该连接到下一级的确切两个节点，形成一棵完全二叉树。

由于国王精通数学，他为每个节点设置了一个数字。具体来说，树的根部，国王所在的地方，是 $1$ ，称 $f_{\text{root}} = 1$。

对于每个节点 $u$，标记为 $f_u$，左孩子是 $f_u \times 2$，右孩子是 $f_u \times 2+1$。国王看着他的树王国，感到满意。

时间飞逝，青蛙国王生病了。根据古老的黑暗魔法，国王可以通过收集 $N$ 个灵魂宝石来延续 $N$ 年寿命。

最初国王没有灵魂宝石，现在他在根部。他将向下走，选择左孩子或右孩子继续前行。每次到达节点 $x$ 时，节点上的数字为 $f_x$（记住 $f_{\text{root}}=1$ ），他可以选择增加灵魂宝石的数量 $f_x$，或者减少 $f_x$。

他将从根部开始，访问确切 $K$ 个节点（包括根部），并按照指示进行增加或减少。如果最后的数字是 $N$，那么他将成功。

需要注意的是，灵魂宝石是一种魔法，国王拥有的灵魂宝石数量可能是负数。

给定 $N, K$，帮助国王找到一种方法，通过访问确切 $K$ 个节点，收集确切 $N$ 个灵魂宝石。

输入格式：

多组询问，每组给出 $N,K$ 。

输出格式：

对于每组数据，第一行输出询问编号，接下来 $K$ 行输出经过的节点和选择增加或减小。

数据范围：

$1 \le T \le 100,~1\le n \le 10^9,~n \le 2^K\le 2^{60}$

忘了第一层是 $2^0=1$ ，然后卡题了（

考虑一个有解的奇数 $a$ ，记它在树上最后选的点为 $p$ ，

那么 $a+1$ 也合法，因为我们最后可以选择 $p+1$ ，所以我们只需要考虑奇数的情况。

注意数据范围中 $n \le 2^{K}$ ，其中最大的奇数为 $2^K-1$ ，而它可以通过一路走最左侧的节点得到。

接着考虑一个点选减法会对结果有什么变化，例如 $K=5$ 时

$1 + 2 + 4 + 8 + 16$

我们让 $4$ 作减法，就等价于在原式基础上减 $8$

$1 + 2 + 4 + 8 + 16 - 8$

等等，这不就意味着，我们可以在 $2^K-1$ 的基础上，减去任何一个 $2^i(1\le i < K)$ 吗？

换句话说，我们其实已经可以表示小于等于 $2^K-1$ 的任何一个奇数了，并且路径甚至没有变化！

那么偶数就更简单了，我们只需要让最后一个节点选他兄弟就可以了，即 $2^{K-1} + 1$

时间复杂度 $\mathcal{O}(TK)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

int pwd[65];
void solve()
{
    int n,k,odd, i = 0; cin >> n >> k;
    if(n & 1) { odd = 0; } else { odd = 1; --n; }
    int mx = pwd[k] - 1, d = mx - (mx - n) / 2; // d 是路径上的加减的二进制表示
    for(; d > 1; d >>= 1) cout << pwd[i++] << ' ' << "-+"[d & 1] << '\n';
    cout << pwd[i] + odd  << ' ' << "-+"[d & 1] << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    pwd[0] = 1; int Q; cin >> Q;
    for(int i = 1; i <= 60; i++) pwd[i] = pwd[i - 1] << 1;
    for(int i = 1; i <= Q; i++)
        cout << "Case #" << i << ":\n", solve();
    return 0;
}