[USACO08OCT] Bovine Bones G

题意

有三个骰子，面数分别是 S1、S2、S3。每个骰子点数从 1 到自己的面数。问所有投掷组合中，哪个点数和出现次数最多；若有多个，输出最小的那个和。

思路

三个骰子的范围都很小，可以直接三重循环枚举所有组合：

text

1
2
3a = 1..S1
b = 1..S2
c = 1..S3

每次把 a + b + c 的出现次数加一。

统计结束后，从小到大扫描所有可能的和，只在 times > best_count 时更新答案。因为扫描顺序从小到大，次数相同的时候不更新，就会保留最小的和。

这题是枚举和计数练习，不创建额外 brute.py。

Python 知识

/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：用 s1, s2, s3 = map(int, input().split()) 读取三个整数。
/home/rainboy/mycode/hugo-blog/content/program_language/python/brute_force_validation.md：多层 range 循环可以直接枚举所有组合。
count[sum_value] += 1 是用列表做频率统计。
enumerate(count) 可以同时获得下标和次数。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18s1, s2, s3 = map(int, input().split())

count = [0] * (s1 + s2 + s3 + 1)

for a in range(1, s1 + 1):
    for b in range(1, s2 + 1):
        for c in range(1, s3 + 1):
            count[a + b + c] += 1

best_sum = 0
best_count = -1

for total, times in enumerate(count):
    if times > best_count:
        best_count = times
        best_sum = total

print(best_sum)

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

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

int cnt[85]; // cnt[s] 记录点数和 s 出现的次数（最大和 = s1+s2+s3 <= 80）
int s1, s2, s3;

int main() {
    cin >> s1 >> s2 >> s3;
    // 三重循环枚举所有骰子点数组合
    for (int a = 1; a <= s1; a++)
        for (int b = 1; b <= s2; b++)
            for (int c = 1; c <= s3; c++)
                cnt[a + b + c]++;
    // 找出现次数最多的最小和
    int best_sum = 0, best_cnt = 0;
    for (int s = 3; s <= s1 + s2 + s3; s++) {
        if (cnt[s] > best_cnt) {
            best_cnt = cnt[s];
            best_sum = s;
        }
    }
    cout << best_sum;
    return 0;
}

Pythonic 写法

用 product 枚举所有点数，Counter 统计和的出现次数，再取次数最大的最小和：

python

1
2
3
4
5
6from collections import Counter
from itertools import product

s1, s2, s3 = map(int, input().split())
count = Counter(a + b + c for a, b, c in product(range(1, s1 + 1), range(1, s2 + 1), range(1, s3 + 1)))
print(min(total for total, times in count.items() if times == max(count.values())))

复杂度

枚举组合数为 S1*S2*S3，在本题范围内很小。时间复杂度是 $O(S1S2S3)$ ，空间复杂度是 $O(S1+S2+S3)$ 。

总结

这题不用推概率公式。把所有组合枚举出来并计数，最后按从小到大的顺序找最大次数即可。

[USACO08OCT] Bovine Bones G

目录

题意

思路

Python 知识

代码

Pythonic 写法

复杂度

总结