Codeforces Round #688(Div 2) D. Checkpoints

题目链接:https://codeforces.com/contest/1453/problem/D

思路

第一步,先推导1,0,0,……,0,就是1后面跟了n-1个0的时候
所需要的期望步数

封闭式推导

\(f_n\)代表从n关开始直接通关需要的步数的期望
n为1的情况,即就只有一个1
\(f_1=\cfrac{1}{2} \times 1+\cfrac{1}{2} \times (f_1+1)\)
整理得\(f_1=2\)
第一关时,你有一半的概率通关,有一半的概率回到自身重新开始
n为2的情况,1,0
\(f_1=\cfrac{1}{2} \times(f_1+1)+\cfrac{1}{2} \times (f_2+1)\)
\(f_2=\cfrac{1}{2} \times 1+\cfrac{1}{2} \times (f_1+1)\)
整理得\(f_1=6\)
第一关时,你有一半的概率到达第二关,有一半的概率回到自身重新开始
第二关时,你有一半的概率通关,有一半的概率回到第一关重新开始
这样我们就可以进行归纳总结
把每个式子化简一下
\(f_1=\cfrac{1}{2} f_1+\cfrac{1}{2} f_2+1\)
\(f_2=\cfrac{1}{2} f_1+\cfrac{1}{2} f_3+1\)
\(f_3=\cfrac{1}{2} f_1+\cfrac{1}{2} f_4+1\)
……
\(f_i=\cfrac{1}{2} f_1+\cfrac{1}{2} f_{i+1}+1\)
……
\(f_n=\cfrac{1}{2} f_1+1\)
然后自己整理一下,就是两个等比数列的和
就得到了\(f_1\)的封闭式
对于任意情况的n时,\(f_1=2^{n+1}-2\)

思路推进

推导出1,……,0,0的期望公式之后,我们如果再后面继续添加1,0,……,0这样一个序列
那么他的期望是直接相加的,因为他是一个复活点(检查点),跟你前面的序列一点关系都没有
所以你无论怎么增加都是一个2的倍数,这样也就得到奇数的时候是无解的

代码实现

上一篇:等差等比数列综合


下一篇:Educational Codeforces Round 104 (Rated for Div. 2) A~E题解