正文

bzoj3566[shoi2014]概率充电器

SilverNebula  SilverNebula  2022-08-27  434

关键词：

Time Limit: 40 Sec Memory Limit: 256 MB
Submit: 999 Solved: 428

Description

著名的电子产品品牌 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

Sample Output

1.000000

HINT

对于 100%的数据,n≤500000,0≤p,qi≤100。

Source

By 佚名提供

我们推出全新史诗级卡池，实现抽到稀有卡的概率无限趋近于0！Bang Dream Idol Festival 限定限时卡池，您抽卡不可错失的良机！能抽到UR吗？现在就试试看吧！

↑做题的时候突然脑洞出这么一句，莫名喜感

数学问题数学期望DP 树形DP

正着求好像有各种精度问题，于是选择求每个结点不能充上电的概率，最后用概率算期望。

一遍DP从下面上来，求出每个点由子树或者自身不能充电的概率

一遍PD从上面下去，求出每个点由父亲不能充电的概率。

算贡献即可。

难得流畅地推出了dp公式，然而日常犯蠢。第35行的g是要在当前节点的f[u]都算完以后才能算的，被我扔到第28行后面，WA了四五次还不明就里

 1 /*by SilverN*/
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 #include<vector>
 8 using namespace std;
 9 const int mxn=500010;
10 int read(){
11     int x=0,f=1;char ch=getchar();
12     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
13     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
14     return x*f;
15 }
16 struct edge{
17     int v,nxt;
18     double w;
19 }e[mxn<<1];
20 int hd[mxn],mct=0;
21 int w[mxn];
22 double f[mxn],g[mxn];//不从子树充电的概率,不向上贡献的概率 
23 double dp[mxn];//不从父亲充电的概率 
24 void add_edge(int u,int v,double w){
25     e[++mct].nxt=hd[u];e[mct].v=v;e[mct].w=w;hd[u]=mct;return;
26 }
27 void DP(int u,int fa,int id){//自底向上的贡献 
28     f[u]=1-w[u]/(double)100.0;//自己没电的概率 
29     for(int i=hd[u],v;i;i=e[i].nxt){
30         if(e[i].v==fa)continue;
31         v=e[i].v;
32         DP(v,u,i);
33         f[u]*=g[v];
34     }
35     g[u]=f[u]+(1.0-f[u])*(1.0-e[id].w);
36 //  printf("f[%d]:%.3f  g[%d]:%.3f
",u,f[u],u,g[u]);
37     return;
38 }
39 void PD(int u,int fa){//自顶向下的贡献 
40     for(int i=hd[u],v;i;i=e[i].nxt){
41         if(e[i].v==fa)continue;
42         v=e[i].v;
43         double x;
44         if(g[v]<1e-6)x=0;
45         else x=f[u]*dp[u]/g[v];
46         dp[v]=x+(1-x)*(1-e[i].w);
47         PD(v,u);
48     }
49     return;
50 }
51 int n;
52 double ans=0;
53 int main(){
54     int i,j;
55     n=read();
56     int a,b,p;
57     for(i=1;i<n;i++){
58         a=read();b=read();p=read();
59         add_edge(a,b,p/(double)100.0);
60         add_edge(b,a,p/(double)100.0);
61     }
62     for(i=1;i<=n;i++)w[i]=read();
63     DP(1,0,0);
64     dp[1]=1;
65     PD(1,0);
66     for(i=1;i<=n;i++)ans+=1-f[i]*dp[i];
67     printf("%.6lf
",ans);
68     return 0;
69 }

bzoj3566[shoi2014]概率充电器

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

●bzoj3566[shoi2014]概率充电器

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

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

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

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... 查看详情

bzoj3566

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

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

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

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

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

bzoj3566概率充电器概率dp

哼我就要正着推链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3566 题意：节点有没有电看脸，线好不好看脸，问一个正常的亚洲人会给几个东西充上电。我就正着推了怎么地首先，我们定义一下数组含义，$f[x]$表示这个点有电... 查看详情

[shoi2014]概率充电器

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

[shoi2014]概率充电器

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

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

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

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

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

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

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

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

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

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

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

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

bzoj3564[shoi2014]信号增幅仪

3564:[SHOI2014]信号增幅仪TimeLimit: 40Sec MemoryLimit: 256MBSubmit: 738 Solved: 290[Submit][Status][Discuss]Description无线网络基站在理想状况下有效信号覆盖范围是个圆形。而无线基站的功耗与圆的半径的平方成正比查看详情

bzoj3562:[shoi2014]神奇化合物(代码片段)

又是玄学的一天~首先，这题做法就很玄学，考虑到点和询问都很少，那么很多边都是没有改动的，那么可以离线用并查集缩点，然后爆搜求解。假如只是这样还好吧，尴尬就在于我跑数据前面3个点挂了？？黑人问号然后一怒之... 查看详情