题解：P13669 [GCPC 2023] DnD Dice

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

暴力思路

如果有

x

个相同的骰子，每个骰子有

y

个面。
那么这个骰子能得到的点数就是：

最少情况下，都骰到 $1$ ，总共 $x$ 。
最多情况下，都骰到 $y$ ，总共 $xy$ 。

在每一层搜索中，从点数

x

到

xy

分别进入下一层搜索。

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

小数据找规律

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

CPP

#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';
}

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

CPP

可以发现：

越靠近上下两端的数，出现次数越小；
越靠近中间的数，出现次数越大。

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

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

证明

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

首先，求一个

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$ 个骰子各个点数出现的概率也呈对称分布。

输出答案

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

代码

CPP

#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++ << ' ';
}

题解：P13669 [GCPC 2023] DnD Dice

文章操作

暴力思路

小数据找规律

证明

输出答案

代码

相关推荐

评论

题解：P13669 [GCPC 2023] DnD Dice