[2019.2.13]BZOJ4318 OSU!

怼烎@ 2022-01-09 05:39 127阅读 0赞

我们记\\(pw3\_i\\)表示前\\(i\\)个位置,结尾为\\(i\\)的最长全1子串的期望长度的立方。

如果我们钦定\\(p\_\{n+1\}=0\\),那么答案\\(=\\sum\_\{i=1\}^npw3\_i\\times(1-p\_\{i+1\})\\)。乘上\\((1-p\_\{i+1\})\\)意思是这一位要在下一位为\\(0\\)的时候才有贡献。

设当前位置为\\(i\\)。

这一位有\\(p\_i\\)的概率为1。那么考虑如何从\\(pw3\_\{i-1\}\\)转移到\\(pw3\_i\\)。

发现\\((x+1)^3=x^3+3x^2+3x+1\\)。

我们记\\(pw2\_i\\)表示前\\(i\\)个位置,结尾为\\(i\\)的最长全1子串的期望长度的平方,\\(pw1\_i\\)表示前\\(i\\)个位置,结尾为\\(i\\)的最长全1子串的期望长度。

那么\\(pw3\_i=(pw3\_\{i-1\}+3pw2\_\{i-1\}+3pw1\_\{i-1\}+1)\\times p\_i\\)

然后我们还要转移\\(pw2\\)和\\(pw1\\)。

同理,\\((x+1)^2=x^2+2x+1\\)。

所以\\(pw2\_i=(pw2\_\{i-1\}+2pw1\_\{i-1\}+1)\\times p\_i\\)。

剩下一个就很简单了,\\(pw1\_i=(pw1\_\{i-1\}+1)\\times p\_i\\)。

做完了。

code:

#include<bits/stdc++.h>
    using namespace std;
    int n;
    double p[100010],pw1[100010],pw2[100010],pw3[100010],ans;
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;++i)scanf("%lf",&p[i]);
        for(int i=1;i<=n;++i)pw1[i]=(pw1[i-1]+1)*p[i],pw2[i]=(pw2[i-1]+2*pw1[i-1]+1)*p[i],pw3[i]=(pw3[i-1]+3*pw2[i-1]+3*pw1[i-1]+1)*p[i],ans+=pw3[i]*(1-p[i+1]);
        printf("%.1lf",ans);
        return 0;
    }

转载于:https://www.cnblogs.com/xryjr233/p/BZOJ4318.html

发表评论取消回复

表情：

评论列表（有 0 条评论，127人围观）

还没有评论，来说两句吧...

相关阅读

相关 BZOJ2938

BZOJ2938-病毒题意： > 二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们...

偏执的太偏执、/ 2024年04月20日 10:24/ 0 赞/ 84 阅读

相关 osu! - 深入了解2021年1月pp算法更新

osu! - 深入了解2021年1月pp算法更新大家好，我是PurePeace（曾用名Rem MajiTenshi，由于osu!在2021年1月进行了一次较大的pp

灰太狼/ 2022年10月24日 11:55/ 0 赞/ 191 阅读

相关 [2019.2.13]BZOJ4318 OSU!

我们记\\(pw3\_i\\)表示前\\(i\\)个位置,结尾为\\(i\\)的最长全1子串的期望长度的立方。如果我们钦定\\(p\_\{n+1\}=0\\),那么答案\\

怼烎@/ 2022年01月09日 05:39/ 0 赞/ 128 阅读

相关 bzoj3632

裸的最大团，随机化大法好多次随机出一个选择顺序然后贪心即可 ![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

心已赠人/ 2021年12月23日 07:39/ 0 赞/ 163 阅读

相关 bzoj4042

比较好的树形dp，涉及到树上路径的题目，我们往往考虑对路径分类当我们考虑以x为根的子树，有这样几类路径 1. 起点终点都在子树内 2. 一个点延伸到子树外对于要选择

ゝ一世哀愁。/ 2021年12月23日 07:37/ 0 赞/ 142 阅读

相关 bzoj 1834

网络流的模板题首先第一问我们直接用dinic搞就行了，费用直接存为0（时间上界非常松，这道题是能过），然后第二问我们只需要在第一问的残余网络上加一个源点，源点指向1号点

灰太狼/ 2021年12月20日 14:51/ 0 赞/ 244 阅读

相关 BZOJ 2671 Calc

题目链接 [https://lydsy.com/JudgeOnline/problem.php?id=2671][https_lydsy.com_JudgeOnline_

Myth丶恋晨/ 2021年12月19日 18:39/ 0 赞/ 275 阅读

相关 BZOJ 3166

BZOJ3196: Tyvj 1730 二逼平衡树传送门：[https://www.lydsy.com/JudgeOnline/problem.php?id=3196]

太过爱你忘了你带给我的痛/ 2021年12月04日 06:59/ 0 赞/ 252 阅读

相关【BZOJ2019】nim

著名游戏设计师vfleaking，最近迷上了Nim。普通的Nim游戏为：两个人进行游戏，N堆石子，每回合可以取其中某一堆的任意多个，可以取完，但不可以不取。谁不能取谁输。...

你的名字/ 2021年03月28日 14:17/ 0 赞/ 464 阅读

相关 bzoj4407

以前写过一次线性筛发现不是很理解写了个欧拉筛的 t了其实每次推式子，都会先推出一组的

红太狼/ 2021年01月08日 13:38/ 0 赞/ 387 阅读