题解：P2911 [USACO08OCT] Bovine Bones G
2011hym
·
·
题解
更好的阅读体验。
题解区的思路大都是暴力枚举，看完后我突然想起来有一个 O(1) 的做法。
我有一计！
题目分析
找出三个骰子所有可能的和中出现次数最高的那个，如果有多个和出现次数相同，则输出字典序最小的那个。
解决思路
我们可以通过分析骰子面数之间的关系，直接计算最可能出现的和，而不需要枚举所有可能的组合。
三个骰子的和最可能出现在中间区域，具体位置取决于三个骰子面数的相对大小。
数学原理
本题解的知识点牵扯到概率论，读者自重。
这玩意基于概率分布的性质：
- 三个独立均匀分布的离散随机变量之和的概率分布呈近似正态分布。
- 当最小两个骰子的面数之和不超过最大骰子面数加 1 时，峰值出现在 1+b+c。
- 否则峰值出现在更复杂的位置，即：
\left\lfloor\frac{b+c-a-1}{2}\right\rfloor+2+a
读者若想了解，可以在 OI Wiki 上搜索，这包含了概率论与组合数学离散差分。
简短证明
核心思路
三个独立均匀分布随机变量之和的众数出现在分布的中心区域，具体位置取决于三个面数的相对大小。
情况分析
情况1：最大骰子足够大 (Z+Y\le X+1)
- 此时 X 的面数足够多，不会限制另外两个骰子的组合。
- 众数出现在 Y+Z 的最大可能值加 1 的位置。
- 公式: 1+Z+Y。
情况2：三个骰子面数相近 (Z+Y>X+1)
- 公式: 2+X+\left\lfloor\frac{Z+Y-X-1}{2}\right\rfloor（~其实是我不想证了~）。
代码实现
这里提供两种做法。
```cpp
#include <bits/stdc++.h>
using namespace std;
int a,b,c;
int main(){
cin>>a>>b>>c;
//排序使 a>=b>=c。
if(a<b)swap(a,b);
if(b<c)swap(b,c);
if(a<b)swap(a,b);
if(b<=a-c+1){
cout<<1+b+c;
}else{
cout<<2+a+(b-a+c-1)/2;
}
return 0;
}
```
$O(n^3)$ 做法（即暴力，不解释）：
```cpp
#include <bits/stdc++.h>
using namespace std;
int freq[110],ans,cnt,s1,s2,s3;//统计和出现的频率。
int main(){
cin>>s1>>s2>>s3;
//枚举所有可能的骰子组。
for(int i=1;i<=s1;i++){
for(int j=1;j<=s2;j++){
for(int k=1;k<=s3;k++){
int sum=i+j+k;
freq[sum]++;
}
}
}
//找出出现频率最高的最小和。
for(int sum=3;sum<=s1+s2+s3;sum++){
if(freq[sum]>cnt){
cnt=freq[sum];
ans=sum;
}
}
cout<<ans;
return 0;
}
```
**update**：2025.7.22 修正了两处小错误。
**update**：2025.9.19 更加详细地修改了一下保证更好的阅读体验。