【BZOJ 4318】OSU!

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4318
神犇题解:https://oi.men.ci/bzoj-4318/

解题报告

设$p_i$为第$i$个操作成功的概率
设$E_{(i,x^3)}$为以第$i$个位置为结尾,$($极长$1$的长度$x)^3$的期望
$E_{(i,x^2)},E_{(i,x)}$分别表示$x^2,x$的期望

那么根据全期望公式,我们有如下结论:

$E_{(i,x^3)}=p_i \times E_{(i-1,(x+1)^3)}$
$E_{(i,x^2)}=p_i \times E_{(i-1,(x+1)^2)}$
$E_{(i,x)}=p_i \times (E_{(i-1,x)} + 1)$

不难发现只有第三个式子可以直接算
但我们还知道一个东西叫期望的线性,于是我们可以将前两个式子化为:

$E_{(i,x^3)}=p_i \times (E_{(i-1,x^3)} + 3E_{(i-1,x^2)} + 3E_{(i-1,x)} + 1)$
$E_{(i,x^2)}=p_i \times (E_{(i-1,x^2)} + 2E_{(i-1,x)} + 1)$

然后就可以直接维护,然后再根据期望的线性加入答案就可以辣!
时间复杂度:$O(n)$

另外,似乎直接算贡献也可以?
可以参考:http://blog.csdn.net/PoPoQQQ/article/details/49512533

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	int n=read(); 
	double e1=0,e2=0,e3=0,ans=0,p;
	for (int i=1;i<=n;i++) {
		scanf("%lf",&p);
		ans += e3 * (1 - p);
		e3 = p * (e3 + 3 * e2 + 3 * e1 + 1);
		e2 = p * (e2 + 2 * e1 + 1);
		e1 = p * (e1 + 1);
	} 
	printf("%.1lf\n",ans+e3);
	return 0;
}

99 thoughts to “【BZOJ 4318】OSU!”

  1. I must thank you for the efforts you’ve put in penning this website. I am hoping to see the same high-grade content by you later on as well. In truth, your creative writing abilities has encouraged me to get my very own blog now 😉

  2. Hi there, I found your website via Google while looking for a related topic, your web site came up, it looks great. I’ve bookmarked it in my google bookmarks.

  3. I absolutely love your blog and find almost all of your post’s
    to be what precisely I’m looking for. can you offer guest writers to write content in your case?
    I wouldn’t mind writing a post or elaborating on most of the subjects you write related to here.
    Again, awesome web site!

  4. After I initially left a comment I appear to have clicked on the -Notify me when new comments are added- checkbox and from now on whenever a comment is added I get 4 emails with the same comment.
    Perhaps there is an easy method you can remove me from that
    service? Thanks a lot!

  5. Hey I know this is off topic but I was wondering if you knew of any widgets I could add to my
    blog that automatically tweet my newest twitter updates.
    I’ve been looking for a plug-in like this for quite some time and was hoping maybe
    you would have some experience with something
    like this. Please let me know if you run into anything.
    I truly enjoy reading your blog and I look forward to your new
    updates.

  6. First of all I want to say excellent blog! I had a quick question that I’d
    like to ask if you don’t mind. I was curious to find out how you
    center yourself and clear your thoughts before writing.
    I have had trouble clearing my thoughts in getting my thoughts out.
    I do enjoy writing however it just seems like the first
    10 to 15 minutes are usually wasted just trying
    to figure out how to begin. Any suggestions or tips?
    Appreciate it!

  7. After going over a few of the blog articles on your
    web page, I really like your technique of writing a blog.
    I book marked it to my bookmark website list and will be checking
    back soon. Please check out my website as well and let me know what you think.

发表评论

电子邮件地址不会被公开。 必填项已用*标注