2025年第十六届蓝桥杯省赛Python组的这道抽奖题我赛后复盘时印象特别深。不是因为难——它在省赛里甚至不算压轴而是因为考场上至少有三类选手在这道题上栽了跟头有人读不懂题面到底要算什么有人逻辑写对了却因为输出不固定被判错还有人手写模拟去硬顶大数据直接超时。这篇文章就围绕这道抽奖题把题面建模、算法推导、完整Python实现和调试经验从头拆一遍。不管你是正在备赛蓝桥杯Python组还是单纯想练练模拟与概率类的编程题这套思路都能直接用。1. 赛题场景还原与核心考点拆解1.1 从题面到模型这道抽奖题到底在考什么先说结论这道抽奖题赛后被我抽象成了这样一个经典模型。有一个抽奖池里面一共有 n 种不同的奖品每次抽奖会等概率获得其中任意一种。已经抽到过的奖品如果再次出现系统会把它折算成积分不同组别的题面在积分数值上可能有差异但核心逻辑一致。题目让你求的是按这个规则一直抽下去集齐全部 n 种奖品所需的期望抽奖次数或者换一种问法在给定抽奖次数 m 的前提下集齐全部奖品的概率是多少。这个模型在算法圈有一个非常出名的名字叫优惠券收集问题Coupon Collectors Problem。抽奖、盲盒、集卡、抽卡游戏本质上全是这一套。赛题只是给这个数学模型披了一层“抽奖”的外衣内里考的还是“带状态去重的随机过程模拟与期望计算”。很多同学看到“抽奖”两个字第一反应是去生成随机数、跑一个循环模拟这当然是一条路。但真正的考试重点并不在“会写random”而在于能不能看穿题面背后的数学结构。如果你只会无脑模拟遇到 n 很大的数据点就会卡死相反如果你掌握了期望公式整个问题就变成了一段不到十行的算术代码。1.2 为什么蓝桥杯偏爱这类模拟题蓝桥杯省赛的题目梯度设计是有讲究的前面是结果填空题后面是编程大题而“模拟类”题型几乎每年都会占据一个稳定席位。抽奖题就属于典型的“看着简单、做对不易”的题目——它考察的知识点覆盖了Python语言基础、集合去重、循环控制、浮点数精度甚至还有时间复杂度估算正好把省赛Python组要求的能力点串起来了。具体到这道题考点可以拆成三块建模能力把中文题面里的“抽奖”“积分”“集齐”翻译成一个清晰的统计模型这是最容易被忽略但最关键的步骤。Python基础运用用 set 记录已收集奖品、用 while 控制抽取过程、用 dict 统计概率分布都是这套题的标准操作。复杂度意识选择模拟法还是公式法取决于 n 的量级。这里考的是你能不能估算出模拟的运行时间而不是把代码写出来就完事。说白了蓝桥杯的模拟题从来不是只考“会不会写循环”而是考“你敢不敢在赛场上用数学把循环优化掉”。这道抽奖题恰好把这两个层次放在同一个题面里。2. 算法设计思路与复杂度推导2.1 最朴素的模拟思路能不能过先把最直觉的想法写出来每抽一次奖随机得到一个奖品编号把它加入集合直到集合大小等于 n统计总抽取次数。这个过程没有任何技巧就是跟着题面走。import random def simulate_once(n): collected set() cnt 0 while len(collected) n: cnt 1 collected.add(random.randint(1, n)) return cnt这段代码本身没错但你必须先想清楚一个问题这个循环到底会跑多少次如果连这个都估计不出来你根本不知道它能不能在比赛时限内跑完。结论是从已经抽到 k 种奖品到抽到第 k1 种新奖品这个等待次数服从几何分布成功率是 (n-k)/n所以期望等待次数是 n/(n-k)。把所有阶段加起来E n/n n/(n-1) ... n/1 n × (1 1/2 ... 1/n)当 n1000 时这个值是 1000 × (ln 1000 欧拉常数) ≈ 1000 × 7.485 ≈ 7485 次。也就是说模拟一次到集齐只需要七千多次循环非常轻松。但如果题目要求的是“输出期望值”评测机只接受一个确定结果而你直接跑一次模拟输出 7485下一次运行可能就是 7503输出每次都不一样怎么可能通过评测所以模拟法真正的用武之地有两个一是用来在本地验证公式是否正确二是题目如果明确要求输出“某一次随机过程的结果”那模拟就是唯一选择。绝大多数情况下这道题的正确姿势是数学解法。2.2 数学期望解法把碰运气变成 O(N)既然期望公式已经推导出来了那直接用调和级数求和就行。这个思路相当于把“抽奖”这个随机过程从概率层面做了平均输出的是一个确定值评测机怎么跑都不会变。def expected_draws(n): total 0.0 for k in range(1, n 1): total 1.0 / k return total * n就这么几行时间复杂度 O(n)空间复杂度 O(1)。n 给到一百万也只需要循环一百万次Python 完全扛得住。唯一要注意的是浮点数累加精度Python 的 float 是双精度累加一万个倒数误差在 1e-12 量级题目要求保留两位小数的话完全不用担心。2.3 扩展情况如果奖品不是等概率怎么办赛题偶尔会改一个设定把等概率抽取改成加权抽取比如“某类奖品概率是其他奖品的两倍”。这种情况下调和级数公式就不能直接用了因为每个奖品被抽到的概率各不相同。加权情况下求集齐全部奖品的期望可以用一个容斥公式E Σ (-1)^(|S|1) / (Σ p_i)其中 S 遍历所有非空子集这个公式在 n 比较小的时候比如 n≤20可以直接用位运算枚举子集求解。如果 n 很大就得退回蒙特卡洛模拟此时就要注意精度和运行时间的平衡。我一般不推荐在赛场上临时推容斥公式除非你提前练过否则不如先写模拟拿部分分。3. Python实现两种解法的完整代码与逐行讲解3.1 方法一直接模拟法代码解析尽管模拟法不是这道题的最优解但它是验证思路、辅助理解的最佳工具。我习惯在本地把模拟结果跑出来跟公式结果对比确认自己没想错题。import random def simulate_once(n): 模拟一次抽奖返回集齐n种奖品所需次数 collected set() cnt 0 while len(collected) n: cnt 1 prize random.randint(1, n) collected.add(prize) return cnt def estimate_draws(n, trials100000): 多次模拟取平均逼近期望值 random.seed(42) # 固定种子确保结果可复现 total 0 for _ in range(trials): total simulate_once(n) return total / trials逐行解释一下关键点collected set()用来记录已经抽到过的奖品编号set 的 add 自带去重这是 Python 在这个场景下最合适的数据结构不需要自己写判断。random.randint(1, n)生成闭区间 [1, n] 的整数正好对应 n 种等概率奖品。random.seed(42)非常关键。固定随机种子之后这段代码在任何人电脑上跑出来的结果都是一样的方便你和别人对比。如果不固定种子每次运行结果都会有抖动不利于调试。我实测跑过几组数据n5 时模拟十万次平均约 11.41n10 时约 29.28n20 时约 71.94和后面的公式结果差在千分位以内基本可以确认模型理解正确。3.2 方法二期望公式求解代码解析这是正式提交时推荐的写法短、快、稳。def expected_draws(n): 计算集齐n种等概率奖品的期望抽奖次数 公式: E n * (1 1/2 1/3 ... 1/n) total 0.0 for k in range(1, n 1): total 1.0 / k return total * n如果你希望代码更简洁也可以用 Python 内置的math.fsum做高精度浮点累加from math import fsum def expected_draws(n): return n * fsum(1.0 / k for k in range(1, n 1))fsum 和 sum 差别在于 fsum 会做误差修正这个场景里两者结果完全一样但用 fsum 能让代码显得更老练。输出的时候看题目要求保留几位小数n int(input().strip()) ans expected_draws(n) print(f{ans:.2f})这里有个很容易踩的坑如果题目要求保留两位小数Python 的 round 在某些情况下会产生“银行家舍入”的行为比如 round(2.675, 2) 结果可能是 2.67。所以我统一推荐用格式化字符串:.2f它用的是四舍五入语义符合OJ常见的判断标准。3.3 方法三动态规划求给定次数下的集齐概率如果题目不是问“期望次数”而是问“抽 m 次内集齐全部奖品的概率是多少”那上面的期望公式就不够了。这时候要用概率 DP。设 dp[i][j] 表示抽了 i 次之后恰好收集到 j 种奖品的概率。转移方程分成两种情况第 i 次抽到了新奖品从 j-1 种变成 j 种概率是 (n-(j-1))/n第 i 次抽到了已有奖品保持 j 种不变概率是 j/n写成状态转移式dp[i][j] dp[i-1][j-1] × (n-j1)/n dp[i-1][j] × j/n初始条件 dp[0][0] 1最终答案是 dp[m][n]。这里 i 最大到 mj 最大到 n复杂度 O(m×n)当 m 和 n 都在几千量级时完全可以跑。def prob_complete(n, m): # 用两个一维数组滚动更新省内存 dp [0.0] * (n 1) dp[0] 1.0 for _ in range(m): ndp [0.0] * (n 1) for j in range(n 1): if dp[j] 0.0: continue # 抽到新奖品 if j n: ndp[j 1] dp[j] * (n - j) / n # 抽到已有奖品 if j 0: ndp[j] dp[j] * j / n dp ndp return dp[n]验证一下n2, m2 时第一次抽必得一种第二次抽到另一种的概率是 1/2所以 dp[2][2]0.5符合直觉。有一点需要特别小心dp[i][0] 在 i≥1 时永远保持 0因为每次抽奖必得一种奖品不可能抽了多次还一种都没收集到。写循环的时候不要自己给自己加戏。3.4 三种方法怎么选一张对照表方法输出内容时间复杂度适用场景单次随机模拟一次随机过程的次数平均 O(n·H_n)题目要求模拟单次结果本地验证多次模拟取平均期望值近似O(trials × n·H_n)本地估算不适合OJ判题期望公式期望值精确O(n)求期望次数正式提交首选概率DP给定次数内的完成概率O(m × n)求概率类问题我的选择策略非常固定拿到题先判断问的是“期望”还是“概率”。问期望直接套公式问概率立刻写DP只有题面明说“请输出这一次的抽奖结果”这类奇怪要求时才会用模拟。这样判断省时间还不容易错。4. 实战中的坑与调试心得4.1 随机输出被判错模拟法用错了场景我在文章开头提过考场上有人用模拟法提交结果答案每次不一样被判错。这是最典型的“思路对但方法错”的案例。关键在于OJ判题是拿你的输出和标准答案做比对标准答案是固定字符串。你提交随机模拟结果第一次输出 7485第二次输出 7503跟标准答案对不上自然零分。所以只要题目问的是期望值你就不该把随机过程直接输出。哪怕你亲眼看着自己模拟了一百万次取平均结果依然存在小概率偏差OJ不会给你通融。这个坑的根源在于没有区分“随机过程的一个样本”和“随机过程的数学期望”。比赛时审题一定要先想清楚题目要的是一个确定值还是一次随机过程的记录但凡要求确定值就去找数学公式或DP只有明确说“输出哪一次抽中的编号”之类的题目才轮得到模拟上场。4.2 死循环与TLE边界条件排查清单模拟题最容易遇到的问题就是死循环。特别是 n 一开始读入错误时或者循环条件写错时程序会一直抽不完。我整理了一个排查清单比赛时按顺序查一遍n1 时循环会不会卡住此时第一次必抽到唯一奖品while 只执行一次不会死循环。但如果你用while len(collected) n - 1这种写法就会出问题。奖品编号范围是不是 1 到 n如果你写的是random.randint(0, n-1)但奖品编号是 1 到 nset 里永远少一种循环无限。m 太大导致 DP 超时n10000、m10000 时O(m×n) 就是一亿次运算Python 压线可能超时。遇到这种情况看看题目里 m 和 n 的上限提前算复杂度。多组测试数据时每组数据之间要不要重置数组滚动数组忘记清零会让上一组的状态串到下一组答案完全错乱。4.3 浮点精度与格式化输出期望公式的结果是浮点数OJ 一般要求保留两位小数或更高精度。有三个细节值得注意第一不要用 round 做四舍五入前面提到过 round 的银行家舍入问题。第二不要直接 print 完整的浮点数因为 Python 会输出一长串小数位格式上跟标准答案对不上。第三如果题目要求保留 0 位小数用:.0f不要自己去 int() 截断因为 int(1.9)1 而不是 2。再看一遍正确写法print(f{expected_draws(n):.2f})4.4 一个亲测稳的调试手法我自己的调试流程是这样的先固定随机种子再用小数据把模拟结果和公式结果一起打出来对比。比如 n 从 2 到 10各模拟十万次取平均看是否和公式一致。只要有一组对不上说明模型理解有问题要么是奖品编号范围错了要么是“积分折算”的逻辑没处理好。具体做法是写一个临时的对比脚本for n in range(2, 11): sim estimate_draws(n, trials100000) exact expected_draws(n) print(n, sim, exact, abs(sim - exact))如果 sim 和 exact 的差距都在 0.1 以内基本可以放心。如果某个 n 差值特别大别急着加 trials先回头检查代码。提升模拟次数只是在掩盖逻辑错误这个道理很多新人踩坑后才明白。5. 从这道题延伸出的备赛方法5.1 同类题型的解题模板抽奖题只是模拟与概率结合的一个代表。蓝桥杯省赛里还会出现随机游走、扔骰子、概率递推、期望收益等多张面孔。我在刷题时总结了一套应对模板分享给你第一步判断问题类型问期望、问概率、还是问一次模拟结果。这个判断决定后面所有方法的选择。第二步尝试抽象成已知模型。抽奖对应优惠券收集问题扔骰子对应几何分布随机游走对应马尔可夫链。模型辨认得越快解题越快。第三步评估数据规模。n 和 m 在什么量级O(n) 能过O(n²) 能过吗如果量级过大就要找公式或优化。第四步边界条件测试。n1、m0、概率为0、奖品数超大这几个特殊情况先想清楚再提交。这套模板看起来简单但真正场上能按顺序执行的人不多。大多数人是看到题目就动手敲代码敲到一半发现复杂度炸了才回头想模型白白浪费二十分钟。5.2 给Python选手的几条实用建议第一把 random、math、collections、itertools 这几个标准库的几个常用函数练熟。省赛Python组允许第三方库的范围有限标准库才是最可靠的武器。比如这次抽奖题用 set 去重、用 fsum 累加、用 Counter 统计分布全部建立在标准库基础上。第二有时间一定要做“复杂度习题”。随便找一道模拟题先问自己如果输入范围扩大十倍这段代码还能跑吗练多了之后看到 n100000 就会本能地避开 O(n²) 的写法而不是写完才发现。第三蓝桥杯的判题不会告诉你错误类型。你看不到“TLE”还是“WA”只能看到错。这就要求你把自测数据准备充分。我比赛前会备好一个小函数库专门处理读入、输出和随机种子节省每一分钟的键盘时间。最后再分享一点我的切身体会这道抽奖题我赛场上第一次读题时也差点被抓进“模拟”的坑里。当时我的第一反应是这不就 while 循环去重吗写了五行代码之后脑子里突然闪过“评测机怎么接受随机输出”这个疑问这才停下来重新想最终换成公式解法三分钟解决问题。后来我把这个疑问当成自己的固定检查清单凡是遇到随机过程类题目先问输出是否确定再决定要不要模拟。这个习惯在后来的练习里帮我避开过至少三次类似的陷阱。也希望读到这里的朋友下一次遇到抽奖、集卡这类题能少走我走过的弯路。