手写的从前题解

题意回顾

构造一个长度为

2

的非负整次幂的序列，这个序列中每个元素都要为

2

的非负整次幂，且序列的和为

m

。

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

数据范围：

1 \le m \le 10^{18}

，数据组数不超过

10^4

组。

分析

将

m

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

对于这个序列若想让字典序最小则需要从小到大排序，故我们考虑让最小的元素越小越好，每次将最小的一个元素如果是

1

那么跳过并记录，否则拆分为两个一半。如果元素个数足够直接输出结果即可（注意补上记录的

1

）。

参考实现

CPP

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

文章操作

题意回顾

分析

参考实现

相关推荐

评论

手写的从前题解