题解：P13669 [GCPC 2023] DnD Dice

· · 题解

很高兴我做过类似的研究（虽然比较浅层）。

暴力思路

如果有 x 个相同的骰子，每个骰子有 y 个面。
那么这个骰子能得到的点数就是：

在每一层搜索中，从点数 x 到 xy 分别进入下一层搜索。

这种思路时间复杂度太高，显然不是正解。
然而，自测输出中有多个点数概率相同，不方便我们观察规律，所以可以使用 dfs 或者简单的多层循环嵌套观察各个点数出现的次数（概率）。

小数据找规律

对于 1 1 1 0 0 这组输入数据，可以写如下代码。

#include<bits/stdc++.h>
using namespace std;

map <int, int> p;

void go(){
    for(int a1=1; a1<=4; a1++)
    for(int a2=1; a2<=6; a2++)
    for(int a3=1; a3<=8; a3++)
        p[a1+a2+a3]++;
}

int main(){
    go();
    for(int i=1+1+1; i<=4+6+8; i++)
        cout << i << ' ' << p[i] << '\n';
}

得到输出（左边是点数，右边是出现次数）：

3 1
4 3
5 6
6 10
7 14
8 18
9 21
10 23
11 23
12 21
13 18
14 14
15 10
16 6
17 3
18 1

可以发现：

即，中位数出现概率最大，两端依次次之。

这个规律同样可以应用到更多的数据中，可使用代码自行验证，此处不过多赘述。

证明

接下来用数学证明这个规律的正确性。

首先，求一个 x 面骰子的单次点数的数学期望值。

\frac{1+2+\dots+x}{x}=\frac{x+1}{2}

接下来，求一共 N 个骰子（分别有 x_1,x_2,\dots,x_N）个面，其点数之和的数学期望值：

\frac{x_1+1}{2}+\frac{x_2+1}{2}+\dots+\frac{x_N+1}{2} =\frac{N+(x_1+x_2+\dots+x_N)}{2}=P

一共 N 个骰子，每个骰子最小得到 1 点，总和最小就是 N；
总和最大显然为 x_1+x_2+\dots+x_N。

所以最后的式子 P 就是 N 个骰子所能得到的最小、最大值的中位数。

最后，根据单个骰子点数的分布的对称性，可知 N 个骰子各个点数出现的概率也呈对称分布。

输出答案

题目只是要求我们按照概率排序，并不要求我们输出每种点数的出现次数。所以找到大小规律即可，不需要再求概率。

代码

#include<bits/stdc++.h>
using namespace std;
int a[] = {4, 6, 8, 12, 20},
    ans[505], cnt;
int main(){
    int L = 0, R = 0;
    for(int i=0; i<5; i++){
        int x; cin >> x;
        // 更新最小值, 最大值 
        L += x, R += x * a[i];
    }

    int num = R + L + 1;
    // 求中间值 
    int mid = num / 2;
    // 从中心开始输出 
    int l = mid-1, r = mid;
    // 奇数特殊处理 
    if(num % 2){
        cout << mid << ' ';
        r++;
    }

    // 从中心向两端输出 
    while(l >= L)
        cout << l-- << ' ' << r++ << ' ';
}