526互联

[Codeforces] CF1858C Yet Another Permutation Problem

发布时间 2023-11-24 20:41:17作者: ccrazy_bboy

Yet Another Permutation Problem - 洛谷

这题本来很简单，思路我也想到了，但是代码一直没写对，思路也一直换来换去（悲

然而发现最开始的思路是对的

题意

Alex 收到了一个名为 "GCD 排列" 的游戏作为生日礼物。这个游戏的每一轮进行如下操作：

  • 首先，Alex 选择一个整数序列\(a_1,a_2,…,a_n\) ，其中整数范围从 \(1\) 到 \(n\) 。
  • 然后，对于每个 i 从 1 到 n ，计算整数 \(d_i=gcd(a_i,a(i\mod n)+1)\) 。
  • 本轮的得分是 \(d_1,d_2,…,d_n\) 中不同数字的数量。

Alex 已经玩了几轮游戏，所以他决定找一个整数序列 \(a_1,a_2,…,a_n\) ，使得它的得分尽可能地大。

回顾一下，\(gcd(x,y)\) 表示 \(x\) 和 \(y\) 的 最大公约数（GCD），而 \(x\space mod\space y\) 表示将 \(x\) 除以 \(y\) 的余数。

长度为 \(n\) 的排列是一个由 \(n\) 个不同整数组成的数组，整数范围从 \(1\) 到 \(n\) 且顺序任意。例如，\([2,3,1,5,4]\) 是一个排列，但 \([1,2,2]\) 不是排列（数组中有重复的 \(2\)），\([1,3,4]\) 也不是排列（虽然 \(n=3\)，但数组中有 \(4\)）。

思路

可以发现，如果想让\(d\)里面有尽量多的不重复数字，就要让\(a\)中的每个数字都被利用。即，尽量使\(a_i=2\times a_{i-1}\)

另：不要过于参考样例，没啥用

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,cnt,f[maxn];
int run()
{
	cin>>n;
	for(int i=0;i<=n;i++) f[i]=0;
	for(int i=1;i<=n;i++)
	{
		int cnt=i;
		if(f[i]==0)
		{
			while(cnt<=n)
			{
				cout<<cnt<<" ";
				f[cnt]=1;
				cnt*=2;
			}
		}
	}
	cout<<endl;
	return 0;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		run();
	}
	return 0;
}