当前位置: 首页 > news >正文

P4550 收集邮票

难度 算法s 日期 题目链接
提高+/省选− 数学期望、递推、倒推 2025-07-21 https://luogu.com.cn/problem/P4550

这道题,巧妙之处在于如何推出期望的递推式。太妙了,回味无穷。慢慢消化吧。

题意简述

总共有 \(n\) 种邮票,我们希望每种邮票至少买到一张。每次购买时,买到任意一种邮票是等可能的。而且我们第 \(k\) 次购买时,需要花费 \(k\) 元钱。

求:花费的期望。

Part I

\(99\%\) 是老师讲解才懂的)

如果直接求 “要买到 \(k\) 种邮票,期望的购买次数”,很难推。不妨先求出:已经买到 \(k\) 种邮票,期望还要买几次,我们记为 \(f_k\)。体会这里的妙处,前者从前往后考虑(正推),后者从后往前考虑(倒推)。正难则反。 为什么倒推能成呢?因为边界条件 \(f_n=0\),我们是知道的。

在已经买到 \(k\) 种邮票的情况下,我们再买一张,有两种可能:

  • 买到的邮票已经在这 \(k\) 种中,概率为 \(k/n\);这种情况下,状态不会转移,所以期望还要买的次数\((k/n)\times f_k\)
  • 买到了新的邮票,概率为 \((n-k)/n\);这种情况下,状态发生转移,期望还要买的次数\([(n-k)/n]\times f_{k+1}\)

于是得出了递推式:

\[f_k=(\frac{k}{n}\times f_k+\frac{n-k}{n}\times f_{k+1})+1. \]

(末尾的 \(+1\) 是当前消耗一个次数,前面那串是之后消耗的次数。)当然这不是真正的递推式。我们分离出 \(f_k\)

\[(1-\frac{k}{n})f_k=\frac{n-k}{n}f_{k+1}+1\\ \Rightarrow f_k=f_{k+1}+\frac{n}{n-k}. \]

注意我们假设在求 \(f_k\) 时已求出 \(f_{k+1}\)

是不是感觉很神奇?我们在列式子的时候,明明没有求出 \(f_k\),但是式子右边却出现了 \(f_k\) 相当于我们也假设了已知 \(f_k\)(?)。但是看了看题解区似乎没人觉得这里有什么奇怪的。总之那个式子恒成立,能用,就用来递推吧。我称之为 “递归推式法”

聪明的你可能会想,那我们移项——

\[f_{k+1}=f_k-\frac{n}{n-k}, \]

如何呢?可不可以正推?很可惜不行。这个式子理论上是成立的,但是我们不知道边界条件 \(f_0\)。事实上我们想求的就是 \(f_0\) 啊。

Part II

注意:期望花费 = \((1+f_0)\times f_0\div2\) 不成立。

现在考虑怎么求花费的期望。类似地,我们定义 \(g_k\) 表示:已经买到 \(k\) 种邮票,期望还要花的钱。同样考虑倒推:

\[g_k=\frac{k}{n}(g_k+f_k+1)+\frac{n-k}{n}(g_{k+1}+f_{k+1}+1). \]

这里为什么会有 \(f\) 项让我困惑了很久。这样理解:

  • 我们从后往前递推,每次我们记录的是 “从当前” 买到达到目标要花的钱。但是 “当前” 再买一次,要花多少钱和 “当前是第几次购买” 相关,我们不知道 “当前” 确切地要花多少。所以我们不妨设 “当前” 要花 \(1\) 元。

  • 然后我们在递推式中 “弥补”:每次向前推一步,相当于后面的购买每次花费都 \(+1\)。所以就有 \(+f_k\)\(+f_{k+1}\) 的说法了。

把上面的式子分理出 \(g_k\),就得到了真正的递推式:

\[g_k=\frac{k}{n-k}(f_k+1)+g_{k+1}+f_{k+1}+1. \]

同样地,边界条件是 \(g_n=0\)\(g_0\) 就是题目要求的终极答案。

Part Final

所以我们就用一个 for()k=n 递推到 k=0。因为 g[] 的计算依赖于 f[],所以每次我们先推出 f[k],再推 g[k]

http://www.hskmm.com/?act=detail&tid=25217

相关文章:

  • P8110 [Cnoi2021] 矩阵
  • P9751 [CSP-J 2023] 旅游巴士
  • P9234 [蓝桥杯 2023 省 A] 买瓜
  • P1044 [NOIP 2003 普及组] 栈
  • P1080 [NOIP 2012 提高组] 国王游戏
  • 音响没声音
  • P1654 OSU!
  • DynamoDB十年演进:云原生数据库的技术革新
  • 完整教程:MySQL全量、增量备份与恢复
  • 10/5
  • 10/4
  • 嵌入式MCU
  • porting perf性能观测工具
  • Windows常用快捷指令
  • Python 在金融中的应用- Part 1 - 教程
  • QBXT2025S刷题 Day4
  • java学习日记9.25
  • porting 开源memtester
  • 计算机的组成
  • 完整教程:用mediamtx搭建简易rtmp,rtsp视频服务器
  • oppoR9m MTK 6755 开启VCOM的9008模式
  • 关于电脑息屏后自动亮屏的的原因排查及解决方式
  • 机器人世界杯工业联赛技术解析
  • Squarepoint Challenge (Codeforces Round 1055, Div. 1 + Div. 2) A~E
  • k8s之基础概念
  • 251005
  • Java基础 Day26 - 详解
  • 14_mklink创建符号链接
  • 7_如何构建知识图谱
  • 点双连通分量例题:矿场搭建