手写的从前 题解

· · 题解

题意回顾

构造一个长度为 2 的非负整次幂的序列，这个序列中每个元素都要为 2 的非负整次幂，且序列的和为 m 。

要求：最小化序列长度，在此基础上最小化序列字典序。

数据范围： 1 \le m \le 10^{18} ，数据组数不超过 10^4 组。

分析

将 m 二进制拆分，这是序列长度的下限，我们还需要补一些元素。

对于这个序列若想让字典序最小则需要从小到大排序，故我们考虑让最小的元素越小越好，每次将最小的一个元素如果是 1 那么跳过并记录，否则拆分为两个一半。如果元素个数足够直接输出结果即可（注意补上记录的 1 ）。

参考实现

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int T;
long long m;
priority_queue<long long, vector<long long>, greater<long long> > pq;
bool check(long long x) {
    while(x % 2 == 0) x /= 2;
    return x == 1;
}
int main() {
    cin >> T;
    for(int ti = 1; ti <= T; ti++) {
        cin >> m;
        for(long long i = (1ll << 62); i >= 1; i >>= 1) {
            if(m >= i) m -= i, pq.push(i);
        }
        int ct1 = 0;
        while(!check(pq.size() + ct1)) {
            int num = pq.top();
            pq.pop();
            if(num == 1) ct1++;
            else {
                pq.push(num / 2);
                pq.push(num / 2);
            }
        }
        for(int i = 1; i <= ct1; i++) {
            printf("1 ");
        }
        while(!pq.empty()) {
            printf("%lld ", pq.top());
            pq.pop();
        }
        puts("");
    }
    return 0;
}