526互联

Codeforces Round 893 (Div. 2) C. Yet Another Permutation Problem

发布时间 2023-10-17 22:02:41作者: zsxuan

有一个 \(gcd\) 游戏，按以下步骤进行：

  • 选择一个 \(n\) 的排列 \(p_1, p_2, \cdots, p_n\) 。
  • 对于每个 \(i\) ，\(d_i = gcd(p_i, p_{i \% n + 1})\)
  • 排列 \(p\) 的 \(score\) 为数组 \([d_1, d_2, \cdots, d_n]\) 中不同数的个数。

给一个 \(n\) ，需要构造一个排列 \(p\) ，使得 \(score_p\) 最大。

\(key\) ：若一个数组中，任意 \(g = gcd(a_i, a_j)\) 存在，则数组中 \(2 \cdot g\) 存在。

  • 推论：\(n\) 的排列中任选两个数可构造的 \(gcd\) 范围为 \([1, \frac{n}{2}]\) 。

如何让相邻两个数的 \(gcd\) 取遍 \([1, \frac{n}{2}]\) 。

考虑一个贪心做法： \(x | y\) 可以满足的条件之一为 \(y \geq 2x\) 。于是枚举所有奇数 \(i\) ，然后构造出一组连续的 \(i \cdot 2^k \leq n\) 。程序结束后 \(1 \sim n\) 都会出现一次，且 \([\lfloor \frac{n}{2} \rfloor + 1, n]\) 会出现在每组的最后一位。于是 \(gcd\) 取遍 \(1, \lfloor \frac{n}{2} \rfloor\) 。

view 
#include <bits/stdc++.h>
typedef long long ll;
void solve(){
	int n; std::cin >> n;
	std::vector<int> ans;
	for (int i = 1; i <= n; i += 2) {
		for (int j = i; j <= n; j *= 2) {
			ans.push_back(j);
		}
	}
	for (int i = 0; i < ans.size(); i++) std::cout << ans[i] << " \n"[i == ans.size() - 1];
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) {solve();}
	return 0;
}