正文

[shoi2014]概率充电器

Mafia  Mafia  2022-09-19  274

关键词：

[SHOI2014]概率充电器

题目

著名的电子产品品牌 SHOI 刚刚发布了引领世界潮流的下一代电子产品——概率充电器:
“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI 概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!
”
SHOI 概率充电器由 n-1 条导线连通了 n 个充电元件。进行充电时,每条导线是否可以导电以概率决定,每一个充电元件自身是否直接进行充电也由概率决定。
随后电能可以从直接充电的元件经过通电的导线使得其他充电元件进行间接充电。
作为 SHOI 公司的忠实客户,你无法抑制自己购买 SHOI 产品的冲动。在排了一个星期的长队之后终于入手了最新型号的 SHOI 概率充电器。
你迫不及待地将 SHOI 概率充电器插入电源——这时你突然想知道,进入充电状态的元件个数的期望是多少呢?

INPUT

第一行一个整数:n。概率充电器的充电元件个数。充电元件由 1-n 编号。
之后的 n-1 行每行三个整数 a, b, p,描述了一根导线连接了编号为 a 和 b 的
充电元件,通电概率为 p%。
第 n+2 行 n 个整数:qi。表示 i 号元件直接充电的概率为 qi%。

OUTPUT

输出一行一个实数,为进入充电状态的元件个数的期望,四舍五入到六位小数

SAMPLE

INPUT

3

1 2 50

1 3 50

50 0 0

OUTPUT

1.000000

解题报告

mmp充个电还得看脸

首先，我们考虑，假如我们直接求每个点被充上电的期望，我们可以直接$DFS$解决，然后儿子上推？？？

还是太年轻～（too young too simple）

我们发现，这里不光是儿子影响父亲，同时父亲还会影响儿子，所以肯定不能傻傻的直接搞

那么我们咋搞呢？

我们发现，如果算每个点充上电的期望的话，需要求它自己直接充上电的和别人充上电传给他的，然后他自己又能给别人充电，这样就很迷

但是，假如我们可以求出每个点不被充上电的概率呢？

当它没有被充上电，那么，从它开始就断开了，不会继续下传下去，所以不会像刚才那么一直乱传那样迷

设$p[i]$为第$i$个点直接被充上电的概率，$w$为边权

设$f[i][0]$代表从$i$的子树没有把电传上来的概率

那么，$f[i][0]=(1-p[i]) imes prod_{jin son[i]}(f[j][0]+(1-f[j][0]) imes (1-w))$

即：该点没有从儿子那里传上来的概率=所有子树没有的概率+子树有的概率*路径没传过来的概率

设$f[i][1]$代表从$i$的父亲没有把电传下来的概率，$t$为其他点传到父亲失败的概率

$$t=frac{f[fa][0]}{f[i][0]+(1-f[i][0]) imes (1-w)} imes f[fa][1]$$

$$f[i][1]=t+(1-t) imes (1-w)$$

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 inline int read(){
 6     int sum(0);
 7     char ch(getchar());
 8     for(;ch<‘0‘||ch>‘9‘;ch=getchar());
 9     for(;ch>=‘0‘&&ch<=‘9‘;sum=sum*10+(ch^48),ch=getchar());
10     return sum;
11 }
12 struct edge{
13     int e;
14     double w;
15     edge *n;
16 }a[1000005],*pre[500005];
17 int tot;
18 inline void insert(int s,int e,int w){
19     a[++tot].e=e;
20     a[tot].w=w/100.0;
21     a[tot].n=pre[s];
22     pre[s]=&a[tot];
23 }
24 int n;
25 int fa[500005];
26 double p,f[500005][2];
27 inline void dfs1(int u){
28     for(edge *i=pre[u];i;i=i->n){
29         int e(i->e);
30         if(e!=fa[u]){
31             fa[e]=u;
32             dfs1(e);
33             f[u][0]*=f[e][0]+(1.0-f[e][0])*(1.0-i->w);
34         }
35     }
36 }
37 inline void dfs2(int u){
38     for(edge *i=pre[u];i;i=i->n){
39         int e(i->e);
40         if(e!=fa[u]){
41             double tmp(f[u][0]/(f[e][0]+(1.0-f[e][0])*(1.0-i->w))*f[u][1]);
42             f[e][1]=tmp+(1.0-tmp)*(1.0-i->w);
43             dfs2(e);
44         }
45     }
46 }
47 int main(){
48     memset(pre,NULL,sizeof(pre));
49     n=read();
50     for(int i=1;i<n;++i){
51         int x(read()),y(read()),z(read());
52         insert(x,y,z),insert(y,x,z);
53     }
54     for(int i=1;i<=n;++i){
55         p=read();
56         f[i][0]=1.0-p/100.0;
57     }
58     dfs1(1);
59     f[1][1]=1;
60     dfs2(1);
61     double ans(0);
62     for(int i=1;i<=n;++i)
63         ans+=1.0-f[i][0]*f[i][1];
64     printf("%lf",ans);
65 }

View Code

loj#2192.「shoi2014」概率充电器(代码片段)

Loj#2192.「SHOI2014」概率充电器题目描述著名的电子产品品牌SHOI刚刚发布了引领世界潮流的下一代电子产品——概率充电器：「采用全新纳米级加工技术，实现元件与导线能否通电完全由真随机数决定！SHOI概率充电器，您生活不... 查看详情

p4284[shoi2014]概率充电器(代码片段)

P4284[SHOI2014]概率充电器链接：https://www.luogu.org/problemnew/show/P4284题目描述著名的电子产品品牌SHOI刚刚发布了引领世界潮流的下一代电子产品——概率充电器：“采用全新纳米级加工技术，实现元件与导线能否通电完全由真随... 查看详情

bzoj3566:[shoi2014]概率充电器

...SHOI刚刚发布了引领世界潮流的下一代电子产品——概率充电器:“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!”SHOI概率充电器由n-... 查看详情

bzoj3566[shoi2014]概率充电器树形概率dp

...刚发布了引领世界潮流的下一代电子产品——概率充电器:“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!”SHOI概率充... 查看详情

bzoj3566:[shoi2014]概率充电器

...充电状态？【题解】引用自：【BZOJ3566】【SHOI2014】概率充电器树形DP概率DP by 空灰冰魂最大的难点在于计算每个点充电期望时，两个节点各自的期望都会影响对方的期望。所以考虑转化对象，改为求每个节点充不上电的... 查看详情

[shoi2014]概率充电器(代码片段)

...生都能看懂（大佬就是大佬啊）：题解P4284【[SHOI2014]概率充电器】，第二次dp的状态方程真的很妙啊。刚开始我总按照套路想设$dp[u]$表示$u$的子树的期望，看完题解后发现这是没有依据的，因为每一个元件可以直接充电，不... 查看详情

bzoj3566[shoi2014]概率充电器

...刚发布了引领世界潮流的下一代电子产品——概率充电器:“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数查看详情

●bzoj3566[shoi2014]概率充电器

题链：http://www.lydsy.com/JudgeOnline/problem.php?id=3566题解：概率dp，树形dp 如果求出每个点被通电的概率t，那么期望答案就是t1×1+t2×1+t3*1+...+tn×1 现在问题就是要去求每个点被通电的概率。因为是一颗树，所以每个点是否... 查看详情

shoi2014概率充电器(代码片段)

题目链接：戳我非常不好意思，因为想要排版，所以今天先只把代码贴出来，明天补题解。QAQ#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#defineeps1e-7#defineMAXN500010intn,m,t;in 查看详情

bzoj3566:[shoi2014]概率充电器树形概率dp(代码片段)

设g[u]为这个点被儿子和自己充上电的概率，f[u]为被儿子、父亲和自己充上电的概率然后根据贝叶斯公式（好像是叫这个），1.P(A+B)=P(A)+P(B)-P(A)*P(B)，2.P(A)=(P(A+B)-P(B))/(1-P(B))g的转移很好想，根据上面的1公式，g[u]=g[u]+g[e[i].to]*e[i].p-g... 查看详情

解题：shoi2014概率充电器(代码片段)

题面显然就是在求概率，因为期望乘的全是1.。。。然后就推推推啊设$fgg[i]$表示这个点父亲没给他充上电的概率，$sgg[i]$表示这个点子树(和它自己没给他充上电的概率)，然后这个点没充上电的概率就是$fgg[i]*sgg[i]$我们发现我们... 查看详情

[bzoj3566][shoi2014]概率充电器(代码片段)

传送门DescriptionSHOI概率充电器由n-1条导线连通了n个充电元件。进行充电时,每条导线是否可以导电以概率决定,每一个充电元件自身是否直接进行充电也由概率决定。随后电能可以从直接充电的元件经过通电的导线使得其他充电元... 查看详情

[题解]luogup4284[shoi2014]概率充电器(代码片段)

https://www.luogu.com.cn/problem/P4284比较套路的概率题？由期望的线性性可以把每个点拆开来，然后答案就是每个点通电的概率之和。通电的概率并不怎么好算，我们可以算点(u)不通电的概率(f[u])，然后答案就是[sumlimits_i=1^n1-f[i]]发现... 查看详情

bzoj3566

3566:[SHOI2014]概率充电器TimeLimit: 40Sec MemoryLimit: 256MBSubmit: 982 Solved: 422[Submit][Status][Discuss]Description著名的电子产品品牌SHOI刚刚发布了引领世界潮流的下一代电子产品——概率充电器:“采用全查看详情

bzoj3566概率充电器（动态规划）

【BZOJ3566】概率充电器（动态规划）题面BZOJDescription著名的电子产品品牌SHOI刚刚发布了引领世界潮流的下一代电子产品——概率充电器:“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI概率充电器,您... 查看详情

shoi2002百事世界杯之旅|概率论(代码片段)

题目：SHOI2002若当前已经有了x种，再买一个买到不一样的概率为(n-x)/n，要使这个概率变成1，则至少再买n/(n-x)瓶。1#include<cstdio>2#include<string>34longlongmax(longlongx,longlongy)5returny<x?x:y;678longlonggcd(longlongx,longlongy 查看详情

cogs1224.[shoi2002]百事世界杯之旅（期望概率）

COGS1224.[SHOI2002]百事世界杯之旅★ 输入文件：pepsi.in 输出文件：pepsi.out 简单对比时间限制：1s 内存限制：128MB 【问题描述】 “……在2002年6月之前购买的百事任何饮料的瓶盖上都... 查看详情

p1291[shoi2002]百事世界杯之旅（概率）(代码片段)

P1291[SHOI2002]百事世界杯之旅设$f(n,k)$表示共n个名字,剩下k个名字未收集到，还需购买饮料的平均次数则有：$f(n,k)=fracn-kn*f(n,k)+frackn*f(n,k+1)+1$移项整理，可得：$f(n,k)=f(n,k+1)+fracnk$根据递推式，可得：$f(n,0)=nsum_k=1^nfrac1k$蓝后g 查看详情