【期望】Kuangbin 危险的派对牛客期望专题班 increment of coins

心已赠人 2024-03-16 12:29 13阅读 0赞

[4849. 危险的迷宫 - AcWing题库][4849. _ - AcWing]

题意：

![da1a016b4ffd495f80e6b634fba638b2.png][]

思路：

本来对期望怎么想都想不通，后来看了大佬的题解，自己动手画了画，以及队友说的“拆分”，忽然间就有点懂了....

![b0c68028d61544e4823e528088070517.png][]

这个说的很对，把期望问题看作是DAG上的递推

如果是边权，递推公式是这个：

![6e71f66d6795473e88f3aff1116fb681.png][]

如果是点权，就是：

![f270a74665044aa788bc2078ee516d5a.png][]

如果还是不懂，或者觉得很奇怪，看一下画的例子应该就懂了

边权：

![bd077f9ef82f41d1a835aee437e43a8e.jpeg][]

点权：

![ad9d13047ff7468ea36b03716f258ac1.jpeg][]

如果不是DAG，而是成为了环，那么就可以直接列方程了

比如这道题：

![151ea90426b54d4da716261d8f4fdbf1.jpeg][]

Code：

#include <bits/stdc++.h>
    
    using namespace std;
    
    const int mxn=1e2+10;
    const int mxe=1e3+10;
    
    int N,idx=0;
    int x[mxn];
    
    void solve(){
        cin>>N;
        for(int i=1;i<=N;i++) cin>>x[i];
        int s1=0,s2=0,cnt=0;
        for(int i=1;i<=N;i++){
            if(x[i]<0){
                cnt++;
                s2+=(-x[i]);
            }else{
                s1+=x[i];
            }
        }
        int d1=(s1+s2);
        int d2=(N-cnt);
        int d=__gcd(d1,d2);
        d1/=d,d2/=d;
        if(cnt==N) cout<<"Case "<<++idx<<": inf"<<'\n';
        else cout<<"Case "<<++idx<<": "<<d1<<"/"<<d2<<'\n';
    }
    int main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
        while(__--)solve();return 0;
    }

知道这些之后，就可以切掉这个模板题了：

[B-increment of coins\_牛客竞赛数学专题班概率与期望习题 (nowcoder.com)][B-increment of coins_ _nowcoder.com]

题意：  
![a80c504bdf2746b4bcb975c757466a1d.png][]

思路：

点权，直接递推即可

![f270a74665044aa788bc2078ee516d5a.png][]

![a98c94685ac5431382e0b2a946dcb699.png][]

Code：

#include <bits/stdc++.h>
    
    using namespace std;
    
    const int mxn=1e2+10;
    const int mxe=1e3+10;
    
    int A,B,C;
    double dp[mxn][mxn][mxn];//背包里有A个金，B个银，C个铜的期望次数
    
    void solve(){
        cin>>A>>B>>C;
        for(int i=0;i<=100;i++){
            for(int j=0;j<=100;j++){
                dp[100][i][j]=dp[i][100][j]=dp[i][j][100]=0;
            }
        }
        for(int i=99;i>=A;i--){
            for(int j=99;j>=B;j--){
                for(int k=99;k>=C;k--){
                    dp[i][j][k]=((dp[i+1][j][k]*i*1.0+dp[i][j+1][k]*j*1.0+dp[i][j][k+1]*k*1.0)/(i+j+k)*1.0)+1.0;
                }
            }
        }
        cout<<fixed<<setprecision(9)<<dp[A][B][C]<<'\n';
    }
    int main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[4849. _ - AcWing]: https://www.acwing.com/problem/content/4852/
[da1a016b4ffd495f80e6b634fba638b2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/bb2ae0771c9f409992c694f7cd732e73.png
[b0c68028d61544e4823e528088070517.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/456c19a34ad248dab9abce3a2c83ebec.png
[6e71f66d6795473e88f3aff1116fb681.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/dd20dd636a8446dc85f8052bae0bfc2d.png
[f270a74665044aa788bc2078ee516d5a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/ff98bf5b79a04098bf938935a36cef5d.png
[bd077f9ef82f41d1a835aee437e43a8e.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/05b2df0f01af40b2a387a47107bf34ba.png
[ad9d13047ff7468ea36b03716f258ac1.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/f89f18ed26454addb16739a3736ee826.png
[151ea90426b54d4da716261d8f4fdbf1.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/bb9f4dd49dde4ea5b9fb129e04a0c7ce.png
[B-increment of coins_ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/32282/B
[a80c504bdf2746b4bcb975c757466a1d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/405d28b5247440e3a42857bc14647bea.png
[a98c94685ac5431382e0b2a946dcb699.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/86c5c80d19264fd6b2c7b4df3f4921a4.png