题解 P1654 【OSU!】
2024-10-08 15:30:01
题面
一序列\(a\), 对于每一个\(i\)均有\(a_i\)有\(p_i\)的几率为1, 否则为\(0\)
求: \(a\)中极长全\(1\)子序列长度三次方之和的期望
前置知识
- 基本期望(期望的概念总得会吧...
- 脑子
解法
可以设\(f(x)\)表示 操作是否成功序列 (以下简称序列\(a\))前\(x\)位以\(x\)结尾极长全\(1\)子序列长度的期望, \(g(x)\)表示\(a\)前\(x\)位以\(x\)结尾极长全\(1\)子序列长度平方的期望, \(r(x)\)表示\(a\)前\(x\)位以\(x\)结尾极长全\(1\)子序列长度三次方的期望(以下简称"期望"), \(h(x)\)表示\(a\)前\(x\)位极长全\(1\)子序列长度三次方之和的期望(即原题所求量)
为了叙述方便以下称原题给出的序列为\(p\)
由期望的定义\(E(x) = \sum v_ip_i\), 有
\[f(x) = (f(x-1)+1) \times p_i + 0 \times (1-p_i) = (f(x-1)+1) \times p_i
\]
\]
同样有:
\[g(x) = (\sqrt{g(x-1)}+1)^2 \times p_i + 0 \times (1-p_i) \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;
\]
\]
\[ = (g(x-1)+2f(x)+1)\times p_i(\text{由定义易知}g(x)=f^2(x))
\]
\]
以及
\[r(x) = (r(x-1)+3g(x)+3f(x)+1)\times p_i
\]
\]
然后有
\[h(x) = h(x-1) \times (1-p_i) + (h(x-1)+r(x)-r(x-1)) \times p_i
\]
\]
这里稍微解释一下, 因为\(h(x)+r(x)\)包括了以\(x-1\)结尾的期望两次(\(h(x)\)包括了\([1, n-1]\)的期望, \(r(x)\)包括了\([lst, n]\)的期望(此处\(lst\)为以\(x-1\)(即\(x\), 因为开头不变)结尾的极长全\(1\)子序列的开头的期望)), 所以要减去\([lst, n-1]\)的期望, 即\(r(x-1)\)
展开原式得
\[h(x) = h(x-1) + (3g(x-1)+3f(x-1)+1) \times p_i
\]
\]
(发现\(p\)完全没有用呢)
接下来暴力扫一遍序列\(p\)求出\(f, g, h\)即可, 时间复杂度为\(O(n)\)
萌新求通过qwq
Code
/*code by tyqtyq*/
#include<bits/stdc++.h>
#define f(i,x,y) for(register int i=x, i##end=y; i<=i##end; ++i)
#define d(i,x,y) for(register int i=y, i##end=x; i>=i##end; --i)
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
using namespace std;
int read(int& x){x=0; int f=1, ch=getchar(); while(!isdigit(ch)) f=ch=='-'?-1:f, ch=getchar(); while(isdigit(ch)) x=x*10+ch-'0', ch=getchar(); return x*=f;}
int read(){int x=0, f=1, ch=getchar(); while(!isdigit(ch)) f=ch=='-'?-1:f, ch=getchar(); while(isdigit(ch)) x=x*10+ch-'0', ch=getchar(); return x*f;}
int max(int x, int y){return x>y?x:y;} int min(int x, int y){return x<y?x:y;}
#define _ 100005
#define read(X) scanf("%lf", &X)
#define print(X) printf("%.1lf\n", X)
double px1[_], px2[_], ans[_], a[_];
int n;
int main(){
scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%lf", &a[i]);
for(int i=1;i<=n;++i) {
px1[i]=(px1[i-1]+1)*a[i];
px2[i]=(px2[i-1]+2*px1[i-1]+1)*a[i];
ans[i]=ans[i-1]+(3*px2[i-1]+3*px1[i-1]+1)*a[i];
}
print(ans[n]);
return 0; //拜拜程序~
}
最新文章
- Pushlet浏览器长连接通讯
- POJ 1947 Rebuilding Roads (树dp + 背包思想)
- postgres数据库中的数据转换
- Spring 创建bean的模式
- atol字符串转换函数应用实例
- Apache配置rewrite
- zepto.js 源码注释备份
- 1.1 java学习网站
- .NET MVC 二级域名路由的实现
- Linux终端下 dstat 监控工具
- C++对C的函数拓展 - 默认参数
- 华途软件受控XML转EXCEL
- GNU C 与 ANSI C(下)
- operator <;<;”不明确
- C#利用CDO.Message发送邮件
- 利用privoxy劫持http网站数据,插入广告,获取用户名,密码
- ASP.NET MVC提交LIST列表到后台接收不到数据
- infobright系列三:数据导入乱码
- RxJava/RxAndroid 使用实例实践
- Java中Io流操作-File类的常用操作-创建文件,创建文件夹