题解：P14607 [NWRRC 2025] High Score

stripe_python · 2026-03-12 08:24:05 · 题解

你需要玩一个 2048 游戏，具体地，你持有一个多重集，每次选择如下两种操作之一：

1. 加入一个 2 或 4。
2. 选择两个相同数 x，将其删除并加入它们的和 2x，你的得分增加 2x。

给定 k，要求在操作过程中，多重集大小始终不超过 k。给你一个数 x，你需要构造一个使得最终得分为 x 的最终多重集，或报告无解。

多测，T \le 10^4，k \le 16，2 秒，1024 MB。

首先有一个观察，最小能选的数就是 2，而 2+2=4，所以得分一定是 4 的倍数，不是的话直接无解。

假设在集合中留下一个数 2^i，我们希望求出合成 2^i 的得分上下界，可以如下分析：

• 最低分通过全部用 4 来合成，得分为 (i-2) 2^i。
• 最高分通过全部用 2 来合成，得分为 (i-1) 2^i。

只要通过把两次加入的 2 换成一个 4，就能让得分减少 4 分，从而使得得分覆盖 [(i-2) 2^i, (i-1) 2^i] 中所有 4 的倍数。

上述过程忽略了空位的限制。设当前有 s 个空位，全 2 合成显然可以得到 2^s，而如果使用全 2 合成 2^{s+1}，空间就不够用了，所以只能将两个 2 用一个 4 代替，最大得分变成 2^{s+1}-4。

理清上述思路后贪心即可，求出当前情况所能得到的最大得分，将最大幂次加入答案集合，然后继续求解。

复杂度 O(T k^2)。

#define int long long
int n, k, x;

void _main() {
    cin >> n >> k;
    while (n--) {
        cin >> x;
        if (x % 4) {cout << -1 << '\n'; continue;}
        int s = k;
        vector<int> res;
        while (x > 0) {
            if (s == 0) break;
            int p = 2;
            for (int i = 2; i <= s + 1; i++) {
                if ((i - 2) * (1LL << i) <= x) p = i;
            }
            int val = (p - 1) * (1LL << p);
            if (p == s + 1) val -= 4;
            x -= min(x, val), res.emplace_back(1LL << p), s--;
        }
        if (x != 0) {
            cout << -1 << '\n';
        } else {
            cout << res.size() << ' ';
            for (int i : res) cout << i << ' ';
            cout << '\n';
        }
    }
}