题解：P2911 [USACO08OCT] Bovine Bones G

题解区的思路大都是暴力枚举，看完后我突然想起来有一个

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$ （~其实是我不想证了~）。

代码实现

这里提供两种做法。

O(1)

做法：

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 更加详细地修改了一下保证更好的阅读体验。

题解：P2911 [USACO08OCT] Bovine Bones G

文章操作

题目分析

解决思路

数学原理

简短证明

核心思路

情况分析

代码实现

相关推荐

评论

题解：P2911 [USACO08OCT] Bovine Bones G