好的，这是一份针对题目 P2911 [USACO08OCT] Bovine Bones G 的简易题解和代码注释。
简易题解
题目大意
给定三个骰子的面数 \(S_1, S_2, S_3\)。每个骰子有 \(1\) 到对应面数的整数点数。我们需要掷这三个骰子，统计所有可能的点数和中，哪个和出现的次数最多。如果有多个和出现的次数都最多，则输出其中最小的那个和。
思路分析
由于骰子的面数范围不大 (\(S_1, S_2 \le 20, S_3 \le 40\))，这意味着所有可能的点数和的范围也不会太大。
最小和是 \(1+1+1=3\)。最大和是 \(S_1+S_2+S_3\)，最大为 \(20+20+40 = 80\)。
这个范围允许我们直接模拟所有可能的掷骰子组合，并统计每个和出现的频率。
具体步骤如下：
-
确定和的范围：
- 最小和：当三个骰子都掷出 1 时，和为 \(1+1+1=3\)。
- 最大和：当三个骰子都掷出各自的最大点数时，和为 \(S_1+S_2+S_3\)。
- 因此，我们可以用一个数组
count_sum来存储每个和出现的次数，数组大小大约需要 \(80+1\) 甚至 \(100+1\) 以覆盖所有可能的和。
-
枚举所有组合并统计：
- 使用三层嵌套循环，分别代表三个骰子的点数。
- 外层循环
i从 \(1\) 到 \(S_1\) (第一个骰子)。 - 中层循环
j从 \(1\) 到 \(S_2\) (第二个骰子)。 - 内层循环
k从 \(1\) 到 \(S_3\) (第三个骰子)。 - 在最内层循环中，计算当前组合
(i, j, k)的和current_sum = i + j + k。 - 然后将
count_sum[current_sum]加 \(1\)。
-
找出出现次数最多的最小和：
- 遍历
count_sum数组，从可能的最小和（3）开始，到最大和。 - 维护两个变量：
max_frequency(当前找到的最大出现次数) 和result_sum(对应max_frequency的最小和)。 - 初始化
max_frequency = 0，result_sum可以任意初始化，或者在第一次找到最大频率时设置。 - 在遍历过程中，如果当前和
s的count_sum[s]大于max_frequency：- 更新
max_frequency = count_sum[s]。 - 更新
result_sum = s。
- 更新
- 由于我们是从小到大遍历和的，如果遇到一个和的频率与
max_frequency相等，但这个和比result_sum大，我们不需要更新result_sum，因为题目要求输出最小的那个和。所以只有当count_sum[s]严格大于max_frequency时才更新。
- 遍历
示例说明
输入：3 2 3
\(S_1=3, S_2=2, S_3=3\)
可能的和的范围：\(1+1+1=3\) 到 \(3+2+3=8\)。
a 数组 (用于统计频率) 大小至少为 9。
-
统计频率：
i=1, j=1, k=1: sum=3,a[3]++i=1, j=1, k=2: sum=4,a[4]++i=1, j=1, k=3: sum=5,a[5]++i=1, j=2, k=1: sum=4,a[4]++i=1, j=2, k=2: sum=5,a[5]++i=1, j=2, k=3: sum=6,a[6]++i=2, j=1, k=1: sum=4,a[4]++i=2, j=1, k=2: sum=5,a[5]++i=2, j=1, k=3: sum=6,a[6]++i=2, j=2, k=1: sum=5,a[5]++i=2, j=2, k=2: sum=6,a[6]++i=2, j=2, k=3: sum=7,a[7]++i=3, j=1, k=1: sum=5,a[5]++i=3, j=1, k=2: sum=6,a[6]++i=3, j=1, k=3: sum=7,a[7]++i=3, j=2, k=1: sum=6,a[6]++i=3, j=2, k=2: sum=7,a[7]++i=3, j=2, k=3: sum=8,a[8]++
最终
a数组计数：
a[3]=1
a[4]=3
a[5]=5
a[6]=5
a[7]=3
a[8]=1 -
找出最大频率的最小和：
mx=0, sum=0i=1,2:a[i]=0，跳过i=3:a[3]=1.1 > 0.mx=1, sum=3.i=4:a[4]=3.3 > 1.mx=3, sum=4.i=5:a[5]=5.5 > 3.mx=5, sum=5.i=6:a[6]=5.5不大于mx=5。不更新sum。i=7:a[7]=3.3不大于mx=5。i=8:a[8]=1.1不大于mx=5。
最终输出 sum = 5。
代码注释
#include<bits/stdc++.h> // 包含所有标准库，方便快速编程 (例如iostream用于输入输出)
using namespace std; // 使用标准命名空间// 定义一个大小为105的整型数组a，用于存储每个和出现的次数（频率）。
// 三个骰子最大点数和为 20+20+40=80。所以数组大小开到81或更大（如105）足够。
int a[105];
int s1,s2,s3; // 定义三个整型变量，存储三个骰子的面数。int main()
{cin>>s1>>s2>>s3; // 从标准输入读取三个骰子的面数。// 三层嵌套循环，模拟掷出三个骰子的所有可能组合。// i代表第一个骰子的点数 (1到s1)// j代表第二个骰子的点数 (1到s2)// k代表第三个骰子的点数 (1到s3)for(int i=1;i<=s1;i++)for(int j=1;j<=s2;j++)for(int k=1;k<=s3;k++)a[i+j+k]++; // 计算当前点数和 (i+j+k)，并将其对应的频率计数器加1。// 例如，如果和是5，则a[5]++。int mx=0; // mx用于存储当前找到的最大出现频率（最大次数）。int sum=0; // sum用于存储出现频率最高的那个和（如果频率相同，则取最小的和）。// 遍历所有可能的点数和，从最小和（理论上是3，但循环从1开始更通用，虽然1,2的a[i]会是0）// 到最大和（s1+s2+s3，最大80）。for(int i=1;i<=80;i++) // 循环上限80，因为最大和是80。{// 如果当前和i的出现频率a[i]大于目前记录的最大频率mxif(a[i]>mx) {mx=a[i]; // 更新最大频率为a[i]。sum=i; // 更新出现频率最高的和为当前和i。// 因为是从小到大遍历i，所以即使后面有频率相同的和，// 也不会更新sum，从而保证sum是最小的那个。}}cout<<sum<<endl; // 输出最终找到的出现频率最高的最小和。return 0; // 程序正常结束。
}