一、题目核心回顾

总蛋糕数：$total = 2^{k+1}$ 初始状态：$\boldsymbol{(2^k,\ 2^k)}$（两人各一半） 目标状态：$\boldsymbol{(x,\ 2^{k+1}-x)}$

操作规则：

• 操作 $1$：Chocola 偶数时，给一半 → $\boldsymbol{(a/2,\ b+a/2)}$
• 操作 $2$：Vanilla 偶数时，给一半 → $\boldsymbol{(a+b/2,\ b/2)}$

要求：最少步数 + 输出操作序列。

二、标程核心思路：逆推法

标程采用从目标倒推回初始状态，这是本题最简单、最优的解法。

为什么逆推？

正向操作会让数字不断除以 2，难以控制； 逆推时，操作变成乘以 2，规律极强、唯一确定，每一步都没有选择 → 天然最少步数。

三、逆推操作规则（关键）

设当前状态 $(a,b)$，逆推一步的规则：

1. 若 $a > b$ → 上一步是操作 2 逆推：$a = a - b,\ b = 2b$
2. 若 $a < b$ → 上一步是操作 1 逆推：$b = b - a,\ a = 2a$

终止条件：到达 $(2^k,\ 2^k)$

最后把逆推得到的序列反转，就是答案。

四、严格数学证明（标程注释）

设状态为 $(a,b)$，满足 $a+b=2^{k+1}$。

1. 总蛋糕数不变 无论操作 1/2，总和始终为：

   $$a+b=2^{k+1}$$

2. 逆推步骤唯一

   • 若 $a > b$：说明上一步是 Vanilla 给出一半（操作 2）
   • 若 $a < b$：说明上一步是 Chocola 给出一半（操作 1） → 每一步只有一种选择，保证最少步数。

3. 步数上限 设 $a = i \cdot 2^{p_a},\ b = j \cdot 2^{p_b}$（$i,j$ 为奇数） 因为 $a+b=2^{k+1}$，所以 $p_a = p_b$。 每逆推一步，$p_a,p_b$ 恰好减 1。 因此最多 $k$ 步，远小于 $120$。

五、标程代码详细解释

完整代码（带中文注释）

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        long long k, x;
        cin >> k >> x;
        
        // kk = 2^k （初始每人蛋糕数）
        long long kk = 1LL << k;
        // 目标另一人蛋糕数 y = 2^(k+1) - x
        long long y = 2 * kk - x;
        
        vector<int> ans;
        
        // 逆推：直到回到初始状态 (kk, kk)
        while (x != kk) {
            if (x > y) {
                // 逆推操作 2（正向是操作 2）
                ans.push_back(2);
                x -= y;
                y *= 2;
            } else {
                // 逆推操作 1（正向是操作 1）
                ans.push_back(1);
                y -= x;
                x *= 2;
            }
        }
        
        // 输出答案
        cout << ans.size() << "\n";
        // 逆序输出（因为是倒着推的）
        while (!ans.empty()) {
            cout << ans.back() << " ";
            ans.pop_back();
        }
        cout << "\n";
    }
    return 0;
}

六、代码运行逻辑（样例演示）

样例 1：$k=2,\ x=3$

• $kk=4,\ y=8-3=5$
• 目标 $(3,5)$ → 逆推：
  1. $3<5$ → 记录 $1$ → $x=6,\ y=4$
  2. $6>4$ → 记录 $2$ → $x=4,\ y=4$
• 序列：$[1,2]$ → 反转 → $\boldsymbol{2\ 1}$
• 输出：

  2
  2 1
  

✅ 与样例完全一致。

七、时间复杂度

• 每组数据：最多 $k$ 步
• $t \le 1000,\ k \le 60$
• 总复杂度：$\boldsymbol{O(t \cdot k)}$ 完美通过所有数据。

八、最终总结（最重要 3 点）

1. 方法：从目标逆推到初始状态
2. 规则：
   • $x>y$ → 操作 2
   • $x<y$ → 操作 1
3. 输出：把逆推序列反转就是最少步数答案

这是本题最优、最简洁、最标准的解法。