欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Codeforces Round #688 (Div. 2) D. Checkpoints gym 102881 L. The Expected Square A. Sticker Album

程序员文章站 2024-01-10 08:08:16
原题地址大致题意:有n个关卡,若干个存档点,闯关成功就进入下一关,否则回到之前最近的存档点。成功的概率为12\frac{1}{2}21​,现在给你走的步数的期望,要求构造一图满足这个期望。题解:显然各个存档点之间的期望是独立的,可以直接相加。......

原题地址
大致题意:有n个关卡,若干个存档点,闯关成功就进入下一关,否则回到之前最近的存档点。成功的概率为 1 2 \frac{1}{2} 21,现在给你走的步数的期望,要求构造一图满足这个期望。

题解:

显然各个存档点之间的期望是独立的,可以直接相加。只需要考虑一个存档点下有n个关卡通关所需的期望。
那么就等价于下面这个子问题。

子问题:抛硬币,如果连续n次正面则游戏结束,否则就一直抛,求抛的次数的期望。

考虑:如果抛到反面就相当于回到了起点,如下图:

设E(n)为该子问题的解,那么考虑递推式:
对于E(n-1)有 1 2 \frac{1}{2} 21的概率抛到正面从而变到E(n),还有 1 2 \frac{1}{2} 21的概率回到原点那么再走到第n个点的概率就是E(n):
E ( n ) = 1 2 ( E ( n − 1 ) + 1 ) + 1 2 ( E ( n − 1 ) + 1 + E ( n ) ) E(n)=\frac{1}{2}(E(n-1)+1)+\frac{1}{2}(E(n-1)+1+E(n)) E(n)=21(E(n1)+1)+21(E(n1)+1+E(n))
解得:
E ( n ) = 2 ∗ E ( n − 1 ) + 2 E(n)=2*E(n-1)+2 E(n)=2E(n1)+2
用上面的思维考虑递推起点E(1):
E ( 1 ) = 1 2 + 1 2 ( 1 + E ( 1 ) ) E(1)=\frac{1}{2}+\frac{1}{2}(1+E(1)) E(1)=21+21(1+E(1))
解得:E(1)=2;
由递推式可得:
E ( n ) + 2 = 2 ∗ ( E ( n − 1 ) + 2 ) E(n)+2=2*(E(n-1)+2) E(n)+2=2(E(n1)+2)
E ( n ) = 2 n + 1 − 2 E(n)= 2^{n+1}-2 E(n)=2n+12
解决该子问题后原问题可以得到轻松解决。
相似的题目::https://codeforces.com/gym/102881/problem/L

子问题扩展:抛一枚硬币,抛到正面的概率是 1 x \frac{1}{x} x1,如果抛到正面则游戏结束,否则就一直抛,求抛的次数的平方的期望,即如果抛的次数是m,则求E( m 2 m^2 m2).

考虑抛k次抛到正面的概率:
前(k-1)次抛的一定都是反面,而第k次恰好是正面,那么其概率为:
( 1 − 1 x ) k − 1 ∗ 1 x (1-\frac{1}{x})^{k-1}*\frac{1}{x} (1x1)k1x1
那么可以得到
E ( m 2 ) = lim ⁡ n → ∞ ∑ i = 1 n i 2 ∗ ( 1 − 1 x ) i − 1 ∗ 1 x E(m^2)=\lim_{n\rightarrow\infty}\sum_{i=1}^{n}i^2*(1-\frac{1}{x})^{i-1}*\frac{1}{x} E(m2)=nlimi=1ni2(1x1)i1x1
由于 1 x \frac{1}{x} x1是常数可以提到求和符号的外面,那么剩下的可以通过两次
错位相减(百度百科)得到答案,化简完了之后取n为无穷,则可以得到答案。
化简得:
E ( m 2 ) = 2 ∗ x 2 − x E(m^2)=2*x^2-x E(m2)=2x2x

相似的题目:https://codeforces.com/gym/102861/problem/A

子问题扩展:每次从[A,B]内取一个整数,使得取的所有数的加和恰好等于n,求所取次数的期望E(n)。

显然E(n)可以由B-A+1种状态转移而来,而且由这些状态转移而来是等概率的。设L=B-A+1有:
E ( n ) = E ( n − A ) L + E ( n − A − 1 ) L + . . . . . . + E ( n − B ) L + 1 E(n)=\frac{E(n-A)}{L}+\frac{E(n-A-1)}{L}+......+\frac{E(n-B)}{L}+1 E(n)=LE(nA)+LE(nA1)+......+LE(nB)+1
特别地如果A=0,那么解方程即可:
E ( n ) = E ( n ) L + E ( n − 1 ) L + . . . . . . + E ( n − B ) L + 1 E(n)=\frac{E(n)}{L}+\frac{E(n-1)}{L}+......+\frac{E(n-B)}{L}+1 E(n)=LE(n)+LE(n1)+......+LE(nB)+1
E ( n ) = L L − 1 ∗ ( E ( n − 1 ) L + . . . . . . + E ( n − B ) L + 1 ) E(n)=\frac{L}{L-1}*(\frac{E(n-1)}{L}+......+\frac{E(n-B)}{L}+1) E(n)=L1L(LE(n1)+......+LE(nB)+1)
对于以上两个方程,递推的时候利用E(n)的前缀和即可在O(n)的时间复杂度内递推出答案。
注意这里最好不要写成:
E ( n ) = E ( n ) + 1 L + E ( n − 1 ) + 1 L + . . . . . . + E ( n − B ) + 1 L E(n)=\frac{E(n)+1}{L}+\frac{E(n-1)+1}{L}+......+\frac{E(n-B)+1}{L} E(n)=LE(n)+1+LE(n1)+1+......+LE(nB)+1
上面的那种写法,当某个结点不存在时(比如E(-2))依然满足(直接作为0处理就行),而这种写法从意义上就会出错。
这种不会回到之前状态的步数期望问题,直接列方程:当前点的期望于能转移到当前状态的期望的平均值加一,如果含有当前点本身解方程即可。

本文地址:https://blog.csdn.net/qq_45622214/article/details/110844232