题目

解析

很神奇的一道题

显然，对于一种排列，相当于给出了数字 \(1..n\) 的对应关系，且不重复不遗漏，刚好把 \(1\) 到 \(n\) 又包含了一遍。

对，连边！

每个数向它对应的数连边，这样我们就得到了一幅图，且这幅图很有特点——全是简单环。

因为每个数的对应有且仅有一个，且不重复不遗漏，所以不存在大环套小环的情况，不存在复杂图形，而且，由于连了边，每个点是什么数字已经没有意义了。

显然，对于一个排列，最大的秩就是所有环大小的最小公倍数。

把 \(n\) 拆成几个正整数的和（正整数可以为 \(1\)），这些正整数的最小公倍数就是我们要的最大的秩，而字典序最小的拆法就是我们要输出的东西。

既然我们已经知道答案就是某个最小公倍数，那我们为什么不直接构造这个最小公倍数？

最小公倍数归根到底是很多质数的乘积，因此我们直接用质数来构造。

假设现在有三个质数 \(p_1、p_2、p_3\)，它们的和 \(\leq n\)，那么 \(p_1*p_2*p_3\) 一定是一个合法的答案。我们可以先弄一个大小为 \(p_1\) 的环，然后弄一个大小为 \(p_2\) 的环，再弄大小为 \(p_3\) 的环，如果n还有剩余，那么剩下的通通自环，这样一定是合法的。

推广：现在把三个质数变成 \(p1^{c1}、p2^{c2}、p3^{c3}\)，他们乘起来依然是合法的。跟上面其实是一样的道理。

再推广：设环的大小为 \(w\)，那么 \(w\) 可不可以包含两种或以上素数？可以，但是完全可以转化成上面的情况处理。设 \(w=p1^{c1} * p2^{c2} * p3^{c3}\)，它对最小公倍数的贡献就是 \(w\)，但是如果我把它拆成三个环来处理，使得每个环大小仅包含一种质数，效果是一样的。而且拆了之后，环的大小也变小了，显然答案的排列会更优。

因为我们的构造方式是：对于一个大小为 \(k\) 的环，我们先输出 \(k - 1\) 个顺序为 \(l+1..l+k-1\) 的数，然后再输 \(l\)。其中 \(l\) 为当前可填的最小的数

问题再次转化

现在问题变成：

现在有一堆质数（\(n\) 以内），每个质数的使用次数上限是已知的（就是上面的 \(c\) 的大小上限）。我要选择一些质数（或它的幂），使他们的和 \(\leq n\)，然后这些质数（或它的幂）的乘积要最大。

而这其实就是有限背包问题。

设 \(f_{i,j}\) 表示我们处理到第i个质数、当前和为j所能获得的最大秩。则 \(f_{i,j}=\max(f_{i-1,j-w}*w)\)。而我们要求排列的话，只需记录一下每个状态是由哪个状态转移过来的，最后还原即可。

于是我们似乎做完了

嗯，确实是似乎

因为你会发现一堆质数的最小公倍数会灰常灰常大

所以题解给了一个很牛逼的方法

那就是给 \(f\) 值转为自然对数来做。

即 \(f_{i,j} \Longleftrightarrow \ln{f_{i,j}}\)

于是转移时 \(\times w\) 变为 \(+ \ln{w}\)

\(Code\)

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

const int N = 1e4 + 5;

const double INF = 1e40;

int t , n , vis[N] , tot , pr[1300] , d[1300] , cnt , g[1300][N];

double f[1300][N] , ans;

inline void getprime(int Mx)

{

	vis[1] = 1;

	for(register int i = 2; i <= Mx; i++)

	{

		if (!vis[i]) pr[++tot] = i;

		for(register int j = 1; j <= tot && pr[j] * i <= Mx; j++)

		{

			vis[pr[j] * i] = 1;

			if (i % pr[j] == 0) break;

		}

	}

}

int main()

{

	getprime(1e4);

	scanf("%d" , &t);

	for(; t; t--)

	{

		scanf("%d" , &n);

		memset(f , 0 , sizeof f);

		f[0][0] = log(1.0);

		for(register int i = 1; i <= tot; i++)

			for(register int j = 0; j <= n; j++)

			{

				f[i][j] = f[i - 1][j];

				int w = pr[i];

				while (j - w >= 0)

				{

					if (f[i - 1][j - w] + log(1.0 * w) > f[i][j]) f[i][j] = f[i - 1][j - w] + log(1.0 * w) , g[i][j] = w;

					w *= pr[i];

				}

			}

		ans = -INF;

		int m , sum = 0;

		for(register int i = 0; i <= n; i++)

		if (f[tot][i] > ans) ans = f[tot][i] , m = i;

		cnt = 0;

		for(register int i = tot; i; i--)

		{

			if (g[i][m]) d[++cnt] = g[i][m] , sum += d[cnt];

			m -= g[i][m];

		}

		while (sum < n) d[++cnt] = 1 , sum++;

		sort(d + 1 , d + cnt + 1);

		int k = 1;

		for(register int i = 1; i <= cnt; i++)

		{

			for(register int j = 1; j < d[i]; j++)

				printf("%d " , k + j);

			printf("%d " , k) , k += d[i];

		}

		printf("\n");

	}

}

巴特西

JZOJ 3232. 【佛山市选2013】排列

题目

解析

\(Code\)

最新文章

热门文章