杂言
赛时想到做法,结果调 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;
}
- 题解 Permutation Another Problem 1858Cpermutation another problem 1858c 题解permutation another problem permutation codeforces another problem 题解another problem 1870e 题解another maxflow problem 题解counting another problem 题解another algebra problem 题解minimization another problem 题解inversions another problem another problem range query