CF1348D Phoenix and Science

Autream · 2025-08-28 16:16:50 · 题解

转换题意得：给定一个整数 n，初始时 sum = x = 1，每次操作可以将 sum 加上 [x, 2x] 中的任意数字 x'，操作被记录为 x' - x，求最小的操作次数以及方案。

题意翻译完了就是一个简单贪心，照最大的选就行，在 \{A_n\} 记录每次加了多少，如果最后有剩的不用管它，加入 \{A_n\} 里面然后排序就行了，可以证明它一定能被 \{A_n\} 中某个数选到（因为它前面都是选的最大值，所以前面的数的取值区间是连续的，而 x 一定小于前面的数中最大的一个）。最后输出 \{A_n\} 的差分数组。

代码

int T, n;
std::vector<int> v;
signed main() {
    T = read();
    while(T --) {
        n = read() - 1, v.clear();
        int x = 1;
        v.p_b(x);
        while(n) n >= 2 * x ? (void)(v.p_b(2 * x), n -= 2 * x, x = 2 * x) : (void)(v.p_b(n), n = 0);
        std::sort(all(v));
        printl(v.size() - 1);
        rep(i, 1, v.size() - 1) printk(v[i] - v[i - 1]); puts("");
    }
    return 0;
}