C. 蛋糕分配

---

一、题意理解

• 初始状态：两人各有 $2^k$ 个蛋糕，总蛋糕数为 $2^{k+1}$。
• 目标状态：Chocola 有 $x$ 个蛋糕，Vanilla 有 $2^{k+1} - x$ 个蛋糕。
• 操作：
  1. Chocola 给出一半蛋糕（要求 Chocola 有偶数个）。
  2. Vanilla 给出一半蛋糕（要求 Vanilla 有偶数个）。
• 求最少步数和操作序列。

---

二、核心观察

2.1 操作的本质

设 Chocola 有 $a$ 个蛋糕，Vanilla 有 $b$ 个蛋糕。总蛋糕数 $S = a + b = 2^{k+1}$。

操作 1：Chocola 给出 $\frac{a}{2}$ 个蛋糕。

$$(a, b) \rightarrow \left(\frac{a}{2},\ b + \frac{a}{2}\right) $$

操作 2：Vanilla 给出 $\frac{b}{2}$ 个蛋糕。

$$(a, b) \rightarrow \left(a + \frac{b}{2},\ \frac{b}{2}\right) $$

2.2 转化为二进制

因为总数为 $2^{k+1}$，而 $a$ 和 $b$ 始终是整数，且 $a + b = 2^{k+1}$。

观察操作对 $a$ 的影响：

• 操作 1：$a \rightarrow \frac{a}{2}$
• 操作 2：$a \rightarrow a + \frac{2^{k+1} - a}{2} = a + 2^k - \frac{a}{2} = 2^k + \frac{a}{2}$

类似地，如果用二进制表示 $a$，操作相当于对二进制进行移位和取反。

2.3 等价转化

设 $a$ 为 Chocola 的蛋糕数。$a$ 始终在 $[1, 2^{k+1}-1]$ 之间。

将 $a$ 写成 $k+1$ 位二进制数（高位在前）。

• 操作 1：$a \rightarrow a / 2$（右移一位，低位丢弃）
• 操作 2：$a \rightarrow 2^k + a/2$（右移一位，最高位变 $1$）

这等价于：每次操作相当于将 $a$ 的二进制表示循环右移一位，且操作类型决定了移入最高位的是 $0$ 还是 $1$。

证明：

设 $a$ 的二进制表示为 $b_k b_{k-1} \dots b_1 b_0$（共 $k+1$ 位）。

• 操作 1：$a/2 = 0\ b_k b_{k-1} \dots b_1$（最高位补 $0$，即移入 $0$）
• 操作 2：$2^k + a/2 = 1\ b_k b_{k-1} \dots b_1$（最高位补 $1$，即移入 $1$）

因此，每一次操作对应于将 $a$ 循环右移一位，并选择新最高位是 $0$（操作 1）还是 $1$（操作 2）。

---

三、问题转化

初始时 $a = 2^k$，二进制为 $1\underbrace{00\dots0}_{k \text{ 个 } 0}$。

目标：通过若干次"循环右移并选择最高位"操作，将 $a$ 变为目标值 $x$。

每次操作在循环右移的同时，我们可以自由选择新的最高位。

最少操作次数 = 使得 $a$ 的二进制表示通过循环移位能变成 $x$ 的最短序列长度。

---

四、解法

4.1 寻找匹配

$k+1$ 位的二进制数，我们想从 $2^k$ 变到 $x$。

每次操作后，$a$ 的低 $k$ 位变成原来 $a$ 的高 $k$ 位，最高位由操作类型决定。

算法：

从初始 $a = 2^k$ 开始，尝试匹配目标 $x$。

在每一步：

• 检查当前 $a$ 是否等于 $x$。若是，结束。
• 否则，我们需要决定执行操作 1 还是操作 2。

由于我们希望最少步数，且 $k \leq 60$，可以尝试 BFS 或直接贪心构造。

4.2 贪心构造

实际上，我们可以利用以下方法：

考虑 $x$ 的二进制表示（$k+1$ 位）和 $2^k$ 的二进制表示。

设目标二进制为 $t_k t_{k-1} \dots t_1 t_0$。

初始 $a = 1\underbrace{00\dots0}_{k}$。

我们逐步构建目标：每一步选择一个操作（$0$ 或 $1$ 移入最高位），使得 $a$ 的二进制循环移位逼近目标。

最少步数：找到最短的序列，使得通过循环移位和选择最高位，能从初始值到达目标值。

---

五、代码实现

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

void solve() {
    int k;
    ll x;
    cin >> k >> x;
    
    ll total = 1LL << (k + 1);  // 2^{k+1}
    ll start = 1LL << k;         // 初始 a = 2^k
    
    if (start == x) {
        cout << "0\n\n";
        return;
    }
    
    // 尝试 BFS 找最短路径（状态数最多 2^{k+1}，但 k <= 60 太大）
    // 改用贪心：枚举循环移位的次数
    
    vector<int> ops;
    ll current = start;
    
    // 最多尝试 2(k+1) 步
    while (current != x && ops.size() < 130) {
        // 检查哪种操作更接近目标
        // 操作1：当前为偶数时可用，current -> current/2
        // 操作2：Vanilla有偶数时可用，即 total - current 为偶数
        //        current -> total/2 + current/2 = 2^k + current/2
        
        bool can1 = (current % 2 == 0);
        bool can2 = ((total - current) % 2 == 0);
        
        // 贪心选择：选能使 current 更接近 x 的操作
        ll nxt1 = can1 ? current / 2 : -1;
        ll nxt2 = can2 ? (1LL << k) + current / 2 : -1;
        
        if (can1 && nxt1 == x) {
            ops.push_back(1);
            break;
        }
        if (can2 && nxt2 == x) {
            ops.push_back(2);
            break;
        }
        
        // 启发式：选择操作后，与目标的二进制差异更小
        if (can1 && can2) {
            // 比较哪种操作后循环移位更容易到达目标
            int d1 = __builtin_popcountll(nxt1 ^ x);
            int d2 = __builtin_popcountll(nxt2 ^ x);
            if (d1 <= d2) {
                ops.push_back(1);
                current = nxt1;
            } else {
                ops.push_back(2);
                current = nxt2;
            }
        } else if (can1) {
            ops.push_back(1);
            current = nxt1;
        } else if (can2) {
            ops.push_back(2);
            current = nxt2;
        } else {
            break;  // 不应发生
        }
    }
    
    cout << ops.size() << "\n";
    for (int o : ops) {
        cout << o << " ";
    }
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

---

六、更简洁的解法

实际上，可以证明最优解可以通过以下方式获得：

将 $x$ 的 $k+1$ 位二进制与初始值对齐，找到最小循环移位次数。

由于循环移位的性质，最少操作次数 $\leq k+1$，最多不超过 $2k+2$。题目保证不超过 $120$。

确定性构造：

从初始值开始，反复执行以下操作直到达到目标：

• 如果当前值已经是目标，停止。
• 否则，查看目标值的二进制表示，决定下一步操作类型，使得当前值的二进制模式逐步逼近目标。

通过 BFS 或直接模拟（因为 $k \leq 60$，状态数受限，但每个测试用例独立）可以找到最短路径。

---

七、复杂度分析

• 每个测试用例最多尝试 $O(k)$ 步，$k \leq 60$。
• 总测试用例 $t \leq 1000$。
• 总体复杂度 $O(t \cdot k)$，完全可行。