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

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

题解：

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

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

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

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

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

考虑抛k次抛到正面的概率：
前(k-1)次抛的一定都是反面，而第k次恰好是正面，那么其概率为:
$$(1-\frac{1}{x}{)}^{k-1}\ast \frac{1}{x}$$
那么可以得到
$$E(m^2)=\underset{n\to \infty }{\lim }\sum _{i=1}^n{i}^2\ast (1-\frac{1}{x}{)}^{i-1}\ast \frac{1}{x}$$
由于$\frac{1}{x}$是常数可以提到求和符号的外面，那么剩下的可以通过两次
错位相减(百度百科)得到答案,化简完了之后取n为无穷，则可以得到答案。
化简得：
$$E(m^2)=2\ast x^2-x$$

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

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

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

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