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;
}