CF1858C Yet Another Permutation Problem 题解

杂言

赛时想到做法，结果调 code 把自己心态调炸了，所以来写一篇题解（恼）。

另：此题与 P9345 夕阳西下几时回 几乎相同，可以此练手。

另另：本题多测，多测不清空，爆零两行泪。

题意翻译

\(a_1,a_2, \dots ,a_n\) 是 \(1\) 至 \(n\) 的一个排列，记 \(d_i=\gcd(a_i,a_{i\bmod n+1})\)。构造一个 \(\{a\}\)，使 \(\{d\}\) 中不同元素的个数最大。

知识点

数论，贪心，构造。

做法

显然，首先显然有 \(\max\{d_i\}=\frac{n}{2}\)，因为如果 $d_i > n/2 $，则必有另一个 \(d_i > n\)，而这是不可能的。

所以我们可以尝试构造出一个 \(\{d\}\)，使其中不同元素个数为 \(\frac{n}{2}\)，这样就能使 \(\{d\}\) 中不同元素的个数最大。

贪心地想，我们从小到大枚举，对于每一个未插入的数 \(a_i\) 且 \(a_i \le \frac{n}{2}\)，直接把 \(2a_i\) 插入 \(a_i\) 的后面，直到 \(2a_i > n\),。接着继续枚举。

通过此方式枚举，显然对于每个 \(a_i \le \frac{n}{2}\) 都能成为 \(\{d\}\) 中的某个数，这么做就是最优的。

时间复杂度 \(O(n)=\sum n\)。

Code

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int t;
int vis[N],ans[N];//vis数组为标记数组，ans数组即为答案序列
int main(){
	t=read();
	while(t--){
		int n=read(),cnt=0;
		memset(vis,0,sizeof(vis));
		memset(ans,0,sizeof(ans));
		for(int i=1;i<=n/2;i++){//只枚到 n/2
			int j=i;
			if(vis[j]) continue;
			while(j<=n){
				ans[++cnt]=j;
				vis[j]=1;//标记，防止重复枚举
				j*=2;
			}
			
		}
		for(int i=n/2+1;i<=n;i++){//剩下的没标记过的直接填上去即可
			if(!vis[i]) ans[++cnt]=i;
		}
		for(int i=1;i<=n;i++) printf("%d ",ans[i]);
		printf("\n");
	}
	return 0;
}