P2565 [SCOI2009]骰子的学问

· · 题解

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

  2. 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;
}