正文

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

Ed_Sheeran  Ed_Sheeran  2022-11-10  452

关键词：

P4284 [SHOI2014]概率充电器

链接：https://www.luogu.org/problemnew/show/P4284

题目描述

著名的电子产品品牌SHOI 刚刚发布了引领世界潮流的下一代电子产品—— 概率充电器：

“采用全新纳米级加工技术，实现元件与导线能否通电完全由真随机数决定！SHOI 概率充电器，您生活不可或缺的必需品！能充上电吗？现在就试试看吧！”

SHOI 概率充电器由n-1 条导线连通了n 个充电元件。进行充电时，每条导线是否可以导电以概率决定，每一个充电元件自身是否直接进行充电也由概率决定。随后电能可以从直接充电的元件经过通电的导线使得其他充电元件进行间接充电。

作为SHOI 公司的忠实客户，你无法抑制自己购买SHOI 产品的冲动。在排了一个星期的长队之后终于入手了最新型号的SHOI 概率充电器。你迫不及待地将SHOI 概率充电器插入电源——这时你突然想知道，进入充电状态的元件个数的期望是多少呢？

输入输出格式

输入格式：

第一行一个整数：n。概率充电器的充电元件个数。充电元件由1-n 编号。

之后的n-1 行每行三个整数a, b, p，描述了一根导线连接了编号为a 和b 的充电元件，通电概率为p%。

第n+2 行n 个整数：qi。表示i 号元件直接充电的概率为qi%。

输出格式：

输出一行一个实数，为能进入充电状态的元件个数的期望，四舍五入到小数点后6 位小数。

输入输出样例

输入样例#1：复制

输出样例#1：复制

1.000000

输入样例#2：复制

5
1 2 90
1 3 80
1 4 70
1 5 60
100 10 20 30 40

输出样例#2：复制

4.300000

说明

对于30%的数据，n≤5000。

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

题解：概率dp,正难求反，求充不上的概率

#include<bits/stdc++.h>
using namespace std;
#define eps 1e-6
#define maxn 500005
double f[maxn],g[maxn],h[maxn];
int tot,head[maxn];
struct edge
    int nxt,to;double w;
G[maxn * 2 + 10];
void add(int u, int v, double w)
    G[++tot].to = v;
    G[tot].w = w;
    G[tot].nxt = head[u];
    head[u] = tot;

void dfs1(int u, int fa)//儿子的贡献
    
    for(int i = head[u]; i; i = G[i].nxt)
        int v = G[i].to;
        if(v == fa)continue;
        dfs1(v, u);        
        h[v] = f[v] + (1 - f[v]) * (1 - G[i].w);//儿子充不上电的概率+儿子冲上电的概率*导线无电概率
        f[u] *= h[v];
    

void dfs2(int u, int fa)    //父亲的贡献    
    
    for(int i = head[u]; i; i = G[i].nxt)
        int v = G[i].to;
        if(v == fa)continue;            
        double t = (f[v] < eps) ? 0 : g[u] * f[u]/h[v];//父亲充不上电的概率，要出去他本身对父亲的贡献
        g[v] = (1 - t)*(1 - G[i].w) + t;
        dfs2(v, u);
    

/*
    t =  g[fa] * f[fa] / f[u]
    g[u] = t + (1 - t)*(1 - w[fa][u])

*/
int main()
    int n;
    double ans = 0;
    scanf("%d",&n);
    for(int i = 1; i < n; i++)
        int u, v, c;
        scanf("%d%d%d",&u,&v,&c);
        add(u, v, c/100.0);add(v, u, c/100.0);
    
    for(int i = 1; i <= n; i++)
        int c;scanf("%d",&c);
        f[i] = 1 - c/100.0;
    
    dfs1(1, 0);
    f[0] = 1; g[1] = 1;
    dfs2(1, 0);
    for(int i = 1; i <= n; i++)
        ans += (1 - f[i]*g[i]);//充上的概率=（1-父亲、儿子都让他充不上）
    printf("%.6lf\n",ans);

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

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

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]概率充电器

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

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

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

[shoi2014]概率充电器

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

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

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

bzoj3566:[shoi2014]概率充电器

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

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

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

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

bzoj3566:[shoi2014]概率充电器

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

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

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

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

luogup3830[shoi2012]随机树期望概率+动态规划+结论(代码片段)

...，直接$f[i][S]$表示$i$个叶子结点，深度之和为$j$的时候的概率，然后化前缀和化出来...）对于一个深度为$x$的点，对它操作后，深度增加了$2*(x+1)-x=x+2$现在考虑平均的情况，令查看详情