【佛山市选2013】2020年8月7日T4 排列

题目

描述
一个关于n个元素的排列是指一个从{1, 2, …, n}到{1, 2, …, n}的一一映射的函数。这个排列p的秩是指最小的k，使得对于所有的i = 1, 2, …, n，都有p(p(…p(i)…)) = i（其中，p一共出现了k次）。
例如，对于一个三个元素的排列p(1) = 3, p(2) = 2, p(3) = 1，它的秩是2，因为p(p(1)) = 1, p(p(2)) = 2, p(p(3)) = 3。
给定一个n，我们希望从n!个排列中，找出一个拥有最大秩的排列。例如，对于n=5，它能达到最大秩为6，这个排列是p(1) = 4, p(2) = 5, p(3) = 2, p(4) = 1, p(5) = 3。
当我们有多个排列能得到这个最大的秩的时候，我们希望你求出字典序最小的那个排列。对于n个元素的排列，排列p的字典序比排列r小的意思是：存在一个整数i，使得对于所有j < i，都有p(j) = r(j)，同时p(i) < r(i)。对于5来说，秩最大而且字典序最小的排列为：p(1) = 2, p(2) = 1, p(3) = 4, p(4) = 5, p(5) = 3。
数据
对于40%的数据，有1≤N≤100。
对于所有的数据，有1≤N≤10000。

题解

题意
简化一下
给出$n$
让你生成一些环
要求环的总大小是$n$并使每个环的大小的最小公倍数最大
多组数据
分析
最小公倍数最大
那么每个环的大小两两互质肯定是最优的
最小公倍数即可表示成 p 1 x 1 ∗ p 2 x 2 ∗ … … ∗ p n x n p1^{x1}*p2^{x2}*……*pn^{xn} p1x1∗p2x2∗……∗pnxn
那么呢
设$f[i][j]$表示选了$i$个质数和为$j$的最大秩
然后对于第$i$个质数暴力枚举取多少次方
记个前驱来生成序列
完事

Code

#include
#include
#include
#include
using namespace std;
int t,n,i,j,ii,mx,num,x,sum,ansnum,last,p[2005],a[10005],g[2005][10005],ans1[10005],ss[10005];
bool b[10005];
double add,m,lg,f[2005][10005];
int main()
{freopen("T4.in","r",stdin);freopen("T4.out","w",stdout);scanf("%d",&t);for (i=1;i<=t;i++){scanf("%d",&a[i]);mx=max(mx,a[i]);}for (i=2;i<=mx;i++)for (j=2;i*j<=mx;j++)b[i*j]=true;for (i=2;i<=mx;i++)if (b[i]==false){num++;p[num]=i;}for (i=0;i<num;i++)for (j=0;j<=mx;j++){if (f[i][j]>f[i+1][j]){f[i+1][j]=f[i][j];g[i+1][j]=j;}x=p[i+1];lg=log(x);for (add=lg;x+j<=mx;x*=p[i+1],add+=lg){if (f[i][j]+add>=f[i+1][x+j]){f[i+1][x+j]=f[i][j]+add;g[i+1][x+j]=j;}}}for (ii=1;ii<=t;ii++){n=a[ii];if (n==1) {printf("1\n");continue;}m=0;sum=n;ansnum=0;for (i=1;i<=n;i++){if (f[num][i]>m){m=f[num][i];x=i;}}for (i=1;i<=n-x;i++){ansnum++;ans1[ansnum]=1;}i=num;while (i){ansnum++;ans1[ansnum]=x-g[i][x];x=g[i][x];i--;}sort(ans1+1,ans1+ansnum+1);last=0;x=1;while (ans1[x]==0&&x<=num) x++;for (i=1;i<=n;i++){if (i==last+ans1[x]){ss[i]=last+1;last+=ans1[x];x++;}else ss[i]=i+1;}for (i=1;i<=n;i++)printf("%d ",ss[i]);printf("\n");}fclose(stdin);fclose(stdout);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！