1. 洛谷 P2911 的题意拆解三只骰子最可能的和做洛谷的过程中P2911 这种带 USACO 前缀的题特别适合拿来打基础。题目名 Bovine Bones G 翻译过来是“牛骨头”看起来像一道生物题实际上是一个掷骰子统计概率的入门题。你不需要先学会组合数学也不需要会概率 DP只要会 for 循环和数组就能把它顺利做出来。真正让这道题成为“必刷题”的不是算法本身难而是它把一个很直观的生活场景包装成了竞赛题。你会不会把文字描述转化成循环逻辑会不会处理平局会不会自己设计测试数据这些能力都能在 P2911 上得到一次很完整的锻炼。对刚接触 OI 或者刚开始刷洛谷的选手来说这道题是一个非常标准的“模拟 枚举”样例。1.1 原题故事与输入输出格式题意大致是这样的农场里的奶牛拿到三只骨头做成的骰子每只骰子分别有 s1、s2、s3 个面面上数字从 1 开始连续编号。比如 s13就是这只骰子的三个面上写着 1、2、3。三只骰子同时掷出来把点数相加得到一个总和。贝茜想知道哪个总和出现的可能性最大如果多个和出现的次数一样多就输出最小的那个和。输入格式非常简单一行三个整数依次是 s1、s2、s3。输出也只有一个整数表示最终答案。洛谷上的评测系统从标准输入读数据向标准输出写答案所以直接在代码里用 cin 或者 input() 就可以。这个设计对新手很友好不需要考虑文件读写。1.2 数据范围对解法的限制遇到这种题第一反应应该是能不能枚举所有组合s1、s2、s3 都表示骰子的面数枚举时每只骰子的取值都要从 1 走到对应上限。假设三只骰子都只有 20 个面那一共有 20×20×208000 种组合一次循环就能全部算完。哪怕面数放大到 80也只是 80×80×80512000 次对现代评测机来说完全不是压力。这也是这道题不需要想复杂公式的原因。很多人一看到“最可能出现的和”就想到概率分布、卷积、生成函数实际上对于这么小的数据范围直接暴力反而最稳、最容易验证。枚举代码写完之后正确性和可读性都比数学推导要直观得多。做题也应该讲究“复杂度匹配数据范围”不会一上来就上重型武器。1.3 一个样例看懂判断规则洛谷给的常见样例是3 2 3期望输出是5。我建议把三只骰子的所有组合手动列一遍。s13、s22、s33 时一共有 3×2×318 种组合。把每个组合的和统计出来后会得到下面这张频率表和出现次数314355657381最大出现次数是 5同时出现在和 5、和 6 两个位置上。按照题目要求出现次数一样多时输出最小的和所以答案是 5不是 6。这个细节特别关键因为很多第一次写的代码会用去更新答案结果把平局情况里的较大和当成答案换一组数据就会 WA。判断“更大”时必须用严格大于这样才能保证多个峰值同时存在时取到最靠前的那一个。2. 暴力枚举与桶计数P2911 的解题思路和复杂度2.1 把“概率最大”翻译成“出现次数最多”如果三只骰子的每一面都是等概率出现的那么某个和“概率最大”就等价于“在所有可能的组合中这个和出现的组数最多”。这给了我们一个很朴素的切入点不需要算分数也不需要算精确概率值只需要统计整数和的个数。举个例子你不需要知道和为 5 出现的概率是 5/18只需要知道 5 这个和会被多少个三元组 (d1, d2, d3) 命中。命中次数越多概率自然越大。这个转化在离散均匀分布的题目里很常见也是 P2911 这类“模拟 枚举”题的核心思想。想通了这一点后面的代码其实就是照做。2.2 桶计数数组的设计下标就是和值是次数实现时需要一个“桶数组”。所谓桶就是用一个数组 cnt把“和”当作下标把“这个和出现过几次”当作值。比如 cnt[5]5意思是总和为 5 的组合一共有 5 组。具体流程如下读入 s1、s2、s3。定义一个计数数组大小至少是 s1s2s31因为最大和不会超过三只骰子面数之和。用三重 for 循环枚举三只骰子的点数i 从 1 到 s1j 从 1 到 s2k 从 1 到 s3。每得到一组点数就执行 cnt[ijk]。枚举所有可能的和从 3 到 s1s2s3找出 cnt 值最大的下标。如果多个下标值相同保留更小的下标。这里最容易忽略的是骰子点数从 1 开始不是从 0 开始。如果循环写成for (int i 0; i s1; i)那么所有组合的和都会往小偏移样例也许碰巧能过换一组数据就会 WA。写循环的时候把循环变量想成“骰子实际显示的数字”而不是“数组下标”这样更不容易错。2.3 时间复杂度和空间复杂度枚举部分有三层循环所以时间复杂度是 O(s1×s2×s3)。找答案的时候要再扫一遍所有可能的和复杂度是 O(s1s2s3)。当数据范围比较小时后者通常可以忽略不计。空间上只需要一个长度为 s1s2s31 的整数数组是 O(s1s2s3)。也就是说这道题的耗时完全取决于三只骰子面数的乘积。对洛谷这题的常见数据范围来说这个复杂度绝对够用。不过在面试题或扩展题里如果面数被放大到 10^6这个三重循环就会彻底超时到那个时候才需要考虑 DP 或卷积优化。P2911 本身还不需要这么复杂但理解复杂度能防止以后乱用暴力。3. P2911 完整代码实现C、Python、Java 三种写法3.1 C 写法直接模板化提交C 是洛谷上最常见的提交语言。下面这段代码可以直接作为模板提交数组大小用 vector 动态计算不写死成固定数字这样即使以后遇到更大的面数也不需要改结构。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int s1, s2, s3; cin s1 s2 s3; vectorint cnt(s1 s2 s3 1, 0); for (int i 1; i s1; i) { for (int j 1; j s2; j) { for (int k 1; k s3; k) { cnt[i j k]; } } } int ans 3; int best 0; for (int sum 3; sum s1 s2 s3; sum) { if (cnt[sum] best) { best cnt[sum]; ans sum; } } cout ans \n; return 0; }如果你不想用bits/stdc.h换成#include iostream也可以。加上ios::sync_with_stdio(false)和cin.tie(nullptr)是为了让 cin/cout 更快虽然这道题数据量小不加也能过但养成这个习惯对后续刷题有好处。3.2 Python 写法注意 list 初始化和循环区间Python 写起来很简洁但 range 边界容易踩坑。range(1, s1 1)会从 1 取到 s1如果写成range(1, s1)就会漏掉 s1 这个面。代码里用s1 s2 s3 1初始化列表保证最大下标存在。import sys def main(): s1, s2, s3 map(int, sys.stdin.readline().split()) cnt [0] * (s1 s2 s3 1) for i in range(1, s1 1): for j in range(1, s2 1): for k in range(1, s3 1): cnt[i j k] 1 ans 3 best 0 for s in range(3, len(cnt)): if cnt[s] best: best cnt[s] ans s print(ans) if __name__ __main__: main()Python 版的三重循环虽然直观但嵌套循环本身比 C 慢。如果面数到几百量级可能要担心性能本题数据范围很小完全能过。以后遇到类似但数据更大的题建议优先用 C或者改用 DP。3.3 Java 写法类名必须是 MainJava 选手在洛谷提交时最容易踩的坑是类名。洛谷的 Java 评测要求主类名必须是Main否则会编译错误。本题的 Java 写法和 C 几乎一一对应import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in new Scanner(System.in); int s1 in.nextInt(); int s2 in.nextInt(); int s3 in.nextInt(); int[] cnt new int[s1 s2 s3 1]; for (int i 1; i s1; i) { for (int j 1; j s2; j) { for (int k 1; k s3; k) { cnt[i j k]; } } } int ans 3; int best 0; for (int sum 3; sum s1 s2 s3; sum) { if (cnt[sum] best) { best cnt[sum]; ans sum; } } System.out.println(ans); } }Java 的数组默认初始化为 0所以不需要手动清零。读入用 Scanner输出用 println。数据量不大时这种写法在洛谷上可以正常 AC。4. P2911 提交常见错误排查从 WA 到 AC 的避坑记录4.1 样例过了却 WA多半是平局处理反了这道题最容易出现的情况是用题目的样例3 2 3测试输出确实是 5看起来没什么问题但换一组数据之后 WA 了。最常见的原因就是平局处理。如果在找最大值时写的是那么当两个和的次数相同时会保留后出现的那个。这正好违反了“输出最小和”的要求。比如2 2 2三只骰子都是两面所有 8 种组合的和分布是3 出现 1 次4 出现 3 次5 出现 3 次6 出现 1 次。正确答案是 4。如果更新条件写成循环到 5 时会因为次数相等而把答案改成 5自然 WA。改成严格大于后4 会先被记录后面 5 的次数相等但不更新答案就对了。4.2 数组越界cnt 大小写成固定数字有些选手看到数据范围小直接定义int cnt[100]。如果 s1、s2、s3 的最大值分别是 20三者和最大是 60100 确实够。但如果你把这个习惯带到其他题目里一旦面数变大cnt[i j k]就可能越界。更规范的做法是使用vectorint cnt(s1 s2 s3 1)让数组长度跟着数据走。另外统计结束后找答案时循环上界也要对应写成s1 s2 s3。这样即使换一组边界数据代码也不会因为没有覆盖到最大值而漏判。不要看到样例只有一个就只验证样例边界数据才是最容易暴露问题的地方。4.3 USACO 原题和洛谷的差异P2911 来自 USACO 2008 年 10 月的题目。USACO 老题通常要求从文件读入、往文件输出而洛谷上的版本统一改成标准输入输出。如果你看到别人代码里有freopen(bones.in, r, stdin)或者bones.out这类文件操作在洛谷提交时要把它们去掉。这个差异不算算法层面的坑但确实会让第一次从 USACO 官网转过来刷洛谷的人摸不着头脑。做题时以题目页的输入输出说明为准不要照搬来源平台的文件读写模板。如果以后去 USACO 官网原题练习再补上对应的文件操作也不迟。4.4 一组自测用例与检查清单手工验证代码时除了样例之外可以多试几个边界值输入期望输出解释1 1 13只有一种组合和是 32 2 24次数最多的是 4 和 5平局取小1 2 24骰子面数不对称时的经典情况20 20 2031对称分布时两个中间值平局取小的那个如果这几个用例都能过代码基本没有问题。提交前再对照检查一遍三重循环是不是都从 1 开始数组下标是否覆盖最大和更新最大值时用的是不是严格大于输出的是不是和而不是出现次数。把这一套检查流程固定下来以后做类似题也能少走弯路。5. 从 P2911 延伸思考骰子数量变成 n 个还能怎么做5.1 三重循环推广成 DPP2911 固定是三只骰子所以三重循环最简单。如果题目改成有 n 只骰子每只骰子的面数还不一样再去写 n 重循环就不现实了。这时候可以用一个滚动数组 DPdp[x] 表示当前若干只骰子掷出的总和为 x 的组合数。初始时 dp[0]1。每加入一只面数为 s 的骰子就用上一层 dp 更新新的 dp对于当前所有可能的和 x新的和 xv 会累加上 dp[x]其中 v 从 1 到 s。这个过程本质上是连续做卷积复杂度大约是 O(n×maxSum×maxSide)。当骰子数量在几千以内时这种写法可以解决很多变体题也是从“暴力枚举”走向“动态规划”的天然一步。5.2 用生成函数看“出现次数”如果接触过一点组合数学会发现整个问题其实是一个多项式乘法三只骰子的点数分布分别对应生成函数 (xx^2...x^s1)、(xx^2...x^s2) 和 (xx^2...x^s3)。把三个多项式乘起来结果里每一项 x^sum 的系数就是总和为 sum 的组合数。这个视角不只是概念好看。当数据范围变大时用 FFT 或 NTT 优化多项式乘法可以把很多类似的“多个数相加计数”问题从 O(n^2) 降到 O(n log n)。P2911 本身完全不需要这一步但理解这个模型能帮你看清暴力枚举背后的数学结构。以后遇到“给你一堆取值范围求某个和出现多少次”的题目你会知道方向在哪里。5.3 概率视角和个人体会从概率角度看三只骰子的和的分布就是三个均匀分布做卷积。众数不一定是期望值尤其是在骰子面数不相等时可能出现多个峰值。所以 P2911 真正想考察的并不是你会不会算期望而是你有没有把“概率最大”翻译成“组合计数”的能力。这种翻译能力比背模板重要得多。我自己的做题习惯是遇到这种小范围计数题第一反应永远是“能不能枚举”而不是急着推公式。推公式容易在边界和枚举方式上出错而枚举虽然看起来笨却往往更容易验证。等确认数据范围不允许暴力再考虑 DP、卷积这些进阶做法。对初学者来说这比一开始就在算法复杂度里挣扎要舒服得多。后面再做 USACO 系列的题你会发现很多题目并不是考高深算法而是考你能不能把题目描述踏踏实实地翻译成代码。