程序笔记
发布时间：2022-07-20 发布网站：大佬教程 code.js-code.com
大佬教程收集整理的这篇文章主要介绍了CF708E Student's Camp，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
tag:概率期望，dp
首先可以预处理出刮掉长度为 (i) 的一段的概率 (g_i)
[g_i=p^i(1-
p)^
{k-i}binom ki
]
设 (f_{i,l,r}) 表示前 (i) 层联通，且第 (i) 层保留的部分为 ([l,r])。显然有式子：
[f_
{i,l,r}=g_
{l-1}cdot g_
{m-r}cdot(sum_
{1leq l'leq r'leq m}f_
{i-1,l',r'}-sum_
{[l',r']cap[l,r]=varnothing}f_
{i-1,l',r'})
]
显然会直接做会TLE。
考虑用前缀和，设：
[sl_
{i,l}=sum_
{r=l}^mf_
{i,l,r}quadquad
sr_
{i,r}=sum_
{l=1}^rf_
{i,l,r}
]
[ssl_
{i,x}=sum_
{l=x}^msl_
{i,l}quadquad
ssr_
{i,x}=sum_
{r=1}^xsr_
{i,r}
]
直观地讲，(sl_{i,l})/(sr_{i,r}) 就是所有左/右端点为 (l)/(r) 的区间的 (dp) 值的和，(ssl_{i,x})/(ssr_{i,x}) 就是 ([x,m])/([1,x]) 的所有子区间的 (dp) 值的和。
那么原式子可以写成：
[f_
{i,l,r}=g_
{l-1}cdot g_
{m-r}cdot(ssr_
{i-1,m}-ssr_
{i-1,l-1}-ssl_
{i-1,r+1})
]
而由于这道题左右情况实际上是完全对称的，即 (ssl_{i,x}=ssr_{i,m-x+1})，于是
[f_
{i,l,r}=g_
{l-1}cdot g_
{m-r}cdot(ssr_
{i-1,m}-ssr_
{i-1,l-1}-ssr_
{i-1,m-r})
]
由于最后答案为 (sum f_{n,l,r}=ssr_{n,m})，所以我们不用具体把 (f) 全部求出来，只需要求出 (ssr) 就行了。至于求 (ssr)，则需要求出 (sr)。
[begin
{matrix}
sr_
{i,r}=sum_
{l=1}^rf_
{i,l,r}\
=sum_
{l=1}^rd_
{l-1}d_
{m-x}(ssr_
{i-1,m}-ssr_
{i-1,l-1}-ssr_
{i-1,m-x})\
=(ssr_
{i-1,m}-ssr_
{i-1,m-x})d_
{m-x}cdotsum_
{l=1}^xd_
{l-1} - d_
{m-x}sum_
{l=1}^xd_
{l-1}ssr_
{i-1,l-1}
end
{matrix}
]
于是先扫一遍求出 (S1_x=sum_{i=1}^xd_{i-1}) 和 (S2_x=sum_{i=1}^xd_{i-1}ssr_{i-1,l-1}) 即可
[sr_
{i,r}=(ssr_
{i-1,m}-ssr_
{i-1,m-x})d_
{m-x}S1_x-d_
{m-x}S2_x
]
复杂度(O(n^2))（直接少了n三方）
大佬总结
以上是大佬教程为你收集整理的CF708E Student's Camp全部内容，希望文章能够帮你解决CF708E Student's Camp所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。
