正文

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

hchhch233  hchhch233  2022-12-02  205

关键词：

Loj #2192. 「SHOI2014」概率充电器

题目描述

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

「采用全新纳米级加工技术，实现元件与导线能否通电完全由真随机数决定！SHOI 概率充电器，您生

活不可或缺的必需品！能充上电吗？现在就试试看吧！」

SHOI 概率充电器由 $n-1$ 条导线连通了 $n$ 个充电元件。进行充电时，每条导线是否可以导电以

概率决定，每一个充电元件自身是否直接进行充电也由概率决定。随后电能可以从直接充电的元件经过

通电的导线使得其他充电元件进行间接充电。

作为 SHOI 公司的忠实客户，你无法抑制自己购买 SHOI 产品的冲动。在排了一个星期的长队之后终

于入手了最新型号的 SHOI 概率充电器。你迫不及待地将 SHOI 概率充电器插入电源——这时你突然想

知道，进入充电状态的元件个数的期望是多少呢？

输入格式

第一行一个整数 $n$，概率充电器的充电元件个数，充电元件由 $1 \sim n$ 编号。

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

件，通电概率为 $p\, \%$。

第 $n+2$ 行 $n$ 个整数 $q_1,\ldots,q_n$。表示 $i$ 号元件直接充电的概率为 $q_i\, \%$。

输出格式

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

数据范围与提示

对于 $100\%$ 的数据，$n \leq 500000,\ 0 \leq p,q_i \leq 100$。

$\\$

根据期望的线性性，我们统计每个点通电出现的概率。发现统计每个点不通电的概率好统计些，也就是该点所在联通块一个点都不通电。

上下两次树形$DP$就搞定了。

代码：

#include<bits/stdc++.h>
#define ll long long
#define N 500005

using namespace std;
inline int Get() int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') if(ch=='-') f=-1;ch=getchar();while('0'<=ch&&ch<='9') x=(x<<1)+(x<<3)+ch-'0';ch=getchar();return x*f;

int n;
struct road 
    int to,nxt;
    double p;
s[N<<1];

int h[N],cnt;
void add(int i,int j,double p) 
    s[++cnt]=(road) j,h[i],p;h[i]=cnt;


double f[N];
double up[N];
double q[N];

void dfs(int v,int fr) 
    f[v]=1-q[v];
    for(int i=h[v];i;i=s[i].nxt) 
        int to=s[i].to;
        if(to==fr) continue ;
        dfs(to,v);
        f[v]=f[v]*(s[i].p*f[to]+(1.0-s[i].p));
    


double pre[N],suf[N];
double ans;
void dfs2(int v,int fr) 
    ans+=1.0-f[v]*up[v];
    vector<int>tem;
    vector<double>E;
    tem.clear();
    E.clear();
    for(int i=h[v];i;i=s[i].nxt) 
        int to=s[i].to;
        if(to==fr) continue ;
        tem.push_back(to);
        E.push_back(s[i].p);
        suf[to]=pre[to]=s[i].p*f[to]+(1.0-s[i].p);
    
    for(int i=1;i<tem.size();i++) pre[tem[i]]=pre[tem[i]]*pre[tem[i-1]];
    for(int i=tem.size()-2;i>=0;i--) suf[tem[i]]=suf[tem[i]]*suf[tem[i+1]];
    for(int i=0;i<tem.size();i++) 
        int to=tem[i];
        double now=1;
        if(i>0) now=now*pre[tem[i-1]];
        if(i<tem.size()-1) now=now*suf[tem[i+1]];
        up[to]=up[v]*now*(1.0-q[v])*E[i]+(1.0-E[i]);
        dfs2(to,v);
    


int main() 
    n=Get();
    int a,b,p;
    for(int i=1;i<n;i++) 
        a=Get(),b=Get(),p=Get();
        add(a,b,1.0*p/100);
        add(b,a,1.0*p/100);
    
    for(int i=1;i<=n;i++) q[i]=1.0*Get()/100;
    dfs(1,0);
    up[1]=1;
    dfs2(1,0);
    cout<<fixed<<setprecision(6)<<ans;
    return 0;

[shoi2014]概率充电器

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

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

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

bzoj3566:[shoi2014]概率充电器

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

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

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概率充电器,您... 查看详情

loj#2036.「shoi2015」自动刷题机

link: https://loj.ac/problem/2036 这个显然具有单调性，N小的话更容易A题，不仅因为A一次题减少的代码，并且A题的下限也低。所以直接上二分就行了，注意上限一定不要设小，不然容易gg。 #include<bits/stdc++.h>#definelllongl... 查看详情

loj#2037.「shoi2015」脑洞治疗仪

#2037.「SHOI2015」脑洞治疗仪题目描述曾经发明了自动刷题机的发明家SHTSC又公开了他的新发明：脑洞治疗仪——一种可以治疗他查看详情

loj#2145.「shoi2017」分手是祝愿

题目链接LOJ#2145题解一道画风正常的……期望DP？首先考虑如何以最小步数熄灭所有灯：贪心地从大到小枚举灯，如果它亮着则修改它。可以求出总的最小步数，设为(cnt)。然后开始期望DP。设(dp[i])为当前最小步数是(i)，总最小步... 查看详情