自动搬运

查看原文

来自洛谷，原作者为

	nomonick 愿乘长风破万里浪

搬运于2025-08-24 21:39:08，当前版本为作者最后更新于2021-11-02 09:26:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P2565 [SCOI2009]骰子的学问

题面解析

题面 link : P2565

给定一个大小为 $n$ 的数组 $\{ a_i \}$ ，你要用整数 $1$ 到 $n \times m$ 填 $n$ 个 $m$ 面的骰子，宝成每个数字只出现一次，使得第 $i$ 个骰子大于第 $a_i$ 个骰子，且对于每个骰子掷出任意一个面的概率相等。

对于骰子 $x$ 大于骰子 $y$ 的定义，当且仅当骰子 $x$ 掷出的点数大于骰子 $y$ 掷出的点数的概率大于 $\frac{1}{2}$。

该题的全部样例如下（对解题有所帮助）：

算法分析

将骰子按照骰子 $x$ 大于骰子 $y$ 的关系建立有向图。而这张图，就构成了一个基环内向树森林。

此时整张图可以被拆分成为两个部分，分别是环内与环外。对于任意的处于环外的点，它应当保证所有的父亲均大于它。那么可以形成一种在环外的构造方法：

对于环外的每一个点，保证保证它的父亲的每一面的点数都比它的最大点数大。显然环外的骰子直接分配极大值就行了。

这样问题就缩小成了运用 $q \times m$ 个数填出一个合法的环。 很明显此时满足 $q > 2, m > 2$

而对于在环内的骰子。选择一个，向父亲方向依次放下 $(1,n)$ 的值，再选择一个，向父亲方向依次放下 $(n+1,2n)$ 。如此重复直到填满。

证明：

两个骰子可以等概率的投出 $m^2$ 种组合。因此对于一个合法的填法，任意一个点与它的后继形成的组合中应至少有 $\left \lceil \frac{m^2 + 1}{2} \right \rceil$ 种满足前者较大。

对于任意的 $i > j$ ，在这种构造下都满足了任何一个骰子的第 $i$ 面一定比另一个骰子的第 $j$ 面大，所以相邻的骰子一定存在 $\frac{m \cdot (m- 1)}{2}$ 种情况是保证了前驱大于后继的。

对于填在第 $i$ 个骰子上的 $q$ 个数除了最大的一个数所在的骰子的前驱，所有的数都大于自己的后继。那么实际上就相当于给每个骰子都增加的 $m$ 种可行情况。而同时会进行 $m$ 次选择，选择哪一个骰子为起点。每次选择会将这个骰子大于后继的数量减一。

而对于任意的一个骰子，被选出的次数最多应该为 $\frac{m \cdot (m+1)}{2} - \left \lceil \frac{m^2 + 1}{2} \right \rceil $ ，而总选择次数应该乘以一个 $q$

1. $m$ 为奇数，总选择次数可表示为 $\frac{qm-q}{2}$ ， 当 $\frac{q(m-1)}{2} \geq m$ 是成立。故满足 $(q - 2) (m - 1) \geq 2$ ，该等式和成立
2. $m$ 为奇偶数，总选择次数可表示为 $\frac{qm-2q}{2}$ ， 当 $\frac{qm-2q}{2} \geq m$ 是成立。故满足 $(q - 2) (m - 2) \geq 4$ ，当且只有一组情况不合法，即 $\left\{\begin{matrix} q = 3 & \\ m = 4 & \end{matrix}\right.$

出现的不合法情况特判即可。

算法实现

为了方便实现可将原有环内操作修改为如下：

选择一个点，向父亲方向依次放下 $(1,n)$ 的值，再选择它的父亲，向父亲方向依次放下 $(n+1,2n)$ 。如此重复直到填满。

这样显然与原有结论并不矛盾，同时又方便实践。

最后拓扑排序即可

code

#include <bits/stdc++.h>
const int SIZE = (int)2e2 + 50;
const int Sample[4][5] = {{},{0,1,3,10,11},{0,2,7,8,9},{0,4,5,6,12}};
int n,m,tot,head,tail;
int son[SIZE],indegree[SIZE],que[SIZE];
int ans[SIZE][SIZE];
inline void toposort()
{
	for (int i = 1; i <= n; ++i) if (!indegree[i]) que[++tail] = i;
	while (head <= tail)
	{
		int u = que[head++]; --indegree[son[u]];
		for (int i = 1; i <= m; ++i) ans[u][i] = tot--;
		if (!indegree[son[u]]) que[++tail] = son[u];
	}
	for (int i = 1; i <= n; ++i)
	{
		if (!indegree[i]) continue; tail = 0;
		for (int u = i; indegree[u]; u = son[u]) indegree[que[++tail] = u] = 0;
		if (tail < 3) {printf("0\n"); exit(0);}
		tot -= tail * m;
		if (tail == 3 && m == 4)
		{
			ans[que[1]][1] = Sample[1][1] + tot; ans[que[1]][2] = Sample[1][2] + tot;
			ans[que[1]][3] = Sample[1][3] + tot; ans[que[1]][4] = Sample[1][4] + tot;
			ans[que[2]][1] = Sample[2][1] + tot; ans[que[2]][2] = Sample[2][2] + tot;
			ans[que[2]][3] = Sample[2][3] + tot; ans[que[2]][4] = Sample[2][4] + tot;
			ans[que[3]][1] = Sample[3][1] + tot; ans[que[3]][2] = Sample[3][2] + tot;
			ans[que[3]][3] = Sample[3][3] + tot; ans[que[3]][4] = Sample[3][4] + tot;
			continue;
		}
		for (int j = 1,now = 1; now <= m; j = (j == 1 ?  tail : j - 1), ++now)
		{
			ans[que[j]][now] = ++tot;
			for (int k = (j == 1 ? tail : j - 1); k ^ j; k = (k == 1 ?  tail : k - 1)) 
				ans[que[k]][now] = ++tot;
		}
		tot -= tail * m;
	}
}
signed main()
{
	cin >> n >> m; tot = n * m; head = 1;
	for (int i = 1; i <= n; ++i) cin >> son[i],indegree[son[i]]++;
	for (int i = 1; i <= n; ++i) if (son[i] == i) return printf("0\n"),0;
	toposort();
	for (int i = 1; i <= n; ++i,printf("\n"))
		for (int j = 1; j <= m; ++j)
			printf("%d ",ans[i][j]);
	return 0;
}