关键词：
https://www.zybuluo.com/ysner/note/1300315
题面
一共有(n)次操作，每次操作只有成功与失败之分，成功对应(1)，失败对应(0)，(n)次操作对应为(1)个长度为(n)的(01)串。
在这个串中连续的(X)个(1)可以贡献(X^3)的分数，这(x)个(1)不能被其他连续的(1)所包含。
现在给出(n)，以及每个操作的成功率，请你输出期望分数，输出四舍五入后保留(1)位小数。
(nleq10^5)
解析
丽洁姐姐的题目套路真多
想想如果又添一个(1)会怎么样？
贡献将变为为((x+1)^3=x^3+3x^2+3x+1)
实际增加量为(3x^2+3x+1)
这个玩意怎么求呢？
设(x1_i)表示以(i)为结尾的(1)串的期望长度。(表增量）
(x2_i)表示以(i)为结尾的(1)串期望长度的平方。（表增量）
(x3_i)表示到(i)时串的期望得分。（累计答案）
(x1[i]=(x1[i-1]+1)*p)
(x_2)的转移可以应用完全平方公式：
(x2[i]=(x2[i-1]+2*x1[i-1]+1)*p)
F3的转移就是概率乘结果：
(x3[i]=x3[i-1]*(1-p)+(x3[i-1]+3*x2[i-1]+3*x1[i-1]+1)*p)
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define pb(a) push_back(a)
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1e5+100;
int n;
double x1[N],x2[N],x3[N],p;
il int gi()
re int x=0,t=1;
re char ch=getchar();
while(ch!=‘-‘&&(ch<‘0‘||ch>‘9‘)) ch=getchar();
if(ch==‘-‘) t=-1,ch=getchar();
while(ch>=‘0‘&&ch<=‘9‘) x=x*10+ch-48,ch=getchar();
return x*t;
int main()
n=gi();
fp(i,1,n)
scanf("%lf",&p);
x1[i]=(x1[i-1]+1)*p;
x2[i]=(x2[i-1]+2*x1[i-1]+1)*p;
x3[i]=x3[i-1]+(3*x2[i-1]+3*x1[i-1]+1)*p;
printf("%.1f
",x3[n]);
return 0;
p1654osu!(代码片段)
期望DP设(g[i])表示前i个的连续1的期望长度，(h[i])表示前i个连续1的长度的平方的期望,(f[i])表示前i个的期望得分由期望的线性性质，我们可以考虑统计新增一个对答案的贡献[E((x+1)^3)-E(x^3)=E(3x^2+3x+1)]然后递推统计即可#include<cstdi... 查看详情
luogup1654osu!概率dp(代码片段)
传送门基础dp还是想了好久....维护连续区间长度的期望还是三次方考虑一次方非常好维护问题就是期望长度的和 记录一下末端1个数的期望就行有p[i]的概率继承有(1-p[i])的概率中断那么三次方是一样的f[],g[],h[]分别维护1,2,3次... 查看详情
p1654osu!（期望dp）(代码片段)
...#43;2*a[i-1]+1)*xb[i]=(1.0∗b[i−1]+2∗a[i−1]+1)∗xAC代码#include<cstdio>usingnamespacestd;intn;doublea[1000005],b[1000005],f[1000005];intmain() scanf("%d",&a 查看详情
osu!三连击(代码片段)
P1654OSU!题目背景原《产品排序》参见P2577题目描述osu是一款群众喜闻乐见的休闲软件。我们可以把osu的规则简化与改编成以下的样子:一共有n次操作，每次操作只有成功与失败之分，成功对应1，失败对应0，n次操作对应为1个长度... 查看详情
poj.1654area（计算几何）(代码片段)
Area题目传送门DescriptionYouaregoingtocomputetheareaofaspecialkindofpolygon.Onevertexofthepolygonistheoriginoftheorthogonalcoordinatesystem.Fromthisvertex,youmaygostepbysteptothefollowingvertexesofthepolyg 查看详情
zoj1654(代码片段)
各行各列连续的o和*记为一个元素。然后记录下开始和结束位置。如果横条和竖条交点为‘o‘。连线。表示两边能选一边，然后最大流。#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<vector>#inclu... 查看详情
poj1654area(代码片段)
...能用c++编译器，不能用g++。还有用abs会莫名ce，要手写。代码：#include<cmath>#include<cstdio>#incl 查看详情
osu!(代码片段)
期望的经典题总期望=所以情况期望之和期望=贡献概率期望的增量=贡献的增量概率贡献=(x^3)贡献的增量=((x+1)^3-x^3=3*x^2+3*x+1)其中(x)的增量是(1)(x^2)的增量是((x+1)^2-x^2=2*x+1)分别维护(x),(x^2),(x^3)的期望即可#include<bits/stdc++.h>usingnam... 查看详情
bzoj4318osu!(代码片段)
...这里$l(i)ot=g(i)^2$。然后dp就好了调试记录精度炸了。。。代码#include<bits/stdc++.h>usingnamespacestd;typedeflongdoubleld; 查看详情
bzoj4318osu!——期望dp(代码片段)
...改过来的：https://blog.csdn.net/Clove_unique/article/details/62422100代码如下：#include<iostream>#inclu 查看详情
bzoj4318:osu!期望dp(代码片段)
【题意】有一个长度为n的01序列，每一段极大的连续1的价值是L^3（长度L）。现在给定n个实数表示该位为1的概率，求期望总价值。n<=10^5。【算法】期望DP【题解】后缀长度是一个很关键的量，设g[i]表示前i个的期望后缀长度。... 查看详情
poj1654area(代码片段)
计算多边形面积的通式/*不规则多边形的计算通过容斥三角形得到答案*/#include<cstdio>#include<cstring>#definelllonglongusingnamespacestd;constintN=1e6+50;chars[N];intmain()intT,n;scanf("%d",&T);while(T--)scanf("%s",s+1);n=strlen(s+1);llx=0,y=0,xx=0,yy=0,ans=0... 查看详情
noip2016提高a组模拟9.15osu(代码片段)
题目分析考虑二分答案，二分小数显然是不可取的，那么我们将所有可能的答案求出来，记录在一个数组上，排个序（C++调用函数很容易超时，手打快排，时间复杂度约为\(O(>8*10^7)\),但相信梦想的力量）。剩下就简单了，将二... 查看详情
[luogu]方差(代码片段)
https://www.luogu.org/problemnew/show/P1471线段树维护区间数的平方之和与和#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;#defineDBdouble#definegcgetchar()#definelsonjd<<1#definersonjd<<1| 查看详情
[luogu]奶酪(代码片段)
https://www.luogu.org/problemnew/show/P3958连边bfs/并查集#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>usingnamespacestd;constintN=1010;#definegcgetchar()struc 查看详情
[luogu]树(代码片段)
https://www.luogu.org/problemnew/show/P4092树剖+线段树区间修改，单点查询#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;inlineintread()intret;scanf("%d",&ret);returnret;intn,T;intnow=1,head[N] 查看详情
静脉检测基于matlab手指静脉图像检测含matlab源码1654期(代码片段)
...对静脉血管类图像处理具有很好地借鉴意义。二、部分源代码%clearall;%clc;%…………………………………………………………………………………………%两种均衡化↓%………………………………………………………………………... 查看详情
[luogu4556]雨天的尾巴(代码片段)
[luogu4556]雨天的尾巴luogu发现是一顿子修改然后再询问,那么把修改树上差分一下再线段树合并但是...如果你只有35分...https://www.luogu.org/discuss/show/88259#include<bits/stdc++.h>usingnamespacestd;constint_=1e5+5;intre()intx=0,w=1;charch=get 查看详情