JZTXT

CF1858C Yet Another Permutation Problem 题解

发布时间 2023-08-16 13:29:19作者: SunnyYuan

思路

这个题是一个简单的构造题。竟然比 T2 简单，也是少见

我们可以首先从 \(1\) 开始不断乘以 \(2\)，像这样：\(1, 2, 4, 8, 16\cdots,2^x\)，直到什么时候超过 \(n\) 就停止。

这样相邻两个数字就可以凑出 \(1, 2, 4, 6, \cdots,2^{x- 1}\)，保证两两不同。

然后我们可以从 \(3\) 开始不断乘以 \(2\)，像这样：\(3, 6, 9, \dots, 3 \times 2^x\)，知道什么时候超过 \(n\) 就停止。

这样相邻的连个数字就可以凑出 \(3, 6, 9, \cdots, 3\times 2^{x - 1}\)，也保证两两不同。

剩下的，您应该也明白了，从 \(5\) 开始继续造，然后是 \(7\)，因为 \(9\) 已经在 \(3\) 的序列里了，所以 \(7\) 后面的是 \(11\)。

最后把剩下的按任意顺序输出就可以了。

\(1\) 分钟出思路系列

代码

#include <bits/stdc++.h>

using namespace std;

void solve() {
	int n;
	cin >> n;
	vector<bool> a(n + 1, 0);
	for (int i = 1; i <= n; i++) {
		if (a[i]) continue;
		int j = i;
		while (j <= n) {
			cout << j << ' ';
			a[j] = 1;
			j <<= 1;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (a[i]) continue;
		cout << i << ' ';
	}
	cout << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int T;
	cin >> T;
	while (T--) solve();
	
	return 0;
}