专栏文章

CF1348D Phoenix and Science

AAutream
CF1348D题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio39khi
此快照首次捕获于
2025/12/02 12:39
3 个月前
此快照最后确认于
2025/12/02 12:39
3 个月前
查看原文
转换题意得：给定一个整数 nn，初始时 sum=x=1sum = x = 1，每次操作可以将 sumsum 加上 [x,2x][x, 2x] 中的任意数字 x′x'，操作被记录为 x′−xx' - x，求最小的操作次数以及方案。
题意翻译完了就是一个简单贪心，照最大的选就行，在 {An}\{A_n\} 记录每次加了多少，如果最后有剩的不用管它，加入 {An}\{A_n\} 里面然后排序就行了，可以证明它一定能被 {An}\{A_n\} 中某个数选到（因为它前面都是选的最大值，所以前面的数的取值区间是连续的，而 xx 一定小于前面的数中最大的一个）。最后输出 {An}\{A_n\} 的差分数组。

代码

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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...