11 条题解

  • 1
    @ 2023-5-26 17:59:09 
    #include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long 
const int MAXN=100000;
const int INF=0x1f1f1f1f1f1f1f1f;
int n,m;
vector<pair<int,int> > e[MAXN+5];
double dp[MAXN+5];
double dfs(int u,int fa)
{
	if(u==n||dp[u])
		return dp[u];
	double res=0;
	int k=e[u].size();
	for(int i=0;i<e[u].size();i++)
	{
		int v=e[u][i].first;
		int w=e[u][i].second;
		if(v==fa)
			continue;
		res+=(dfs(v,u)+w)/k;
	}
	return dp[u]=res;
}
signed main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		e[u].push_back(make_pair(v,w));
	}
	cout<<fixed<<setprecision(2)<<dfs(1,-1)<<endl;
	return 0;
}
    • @ 2023-5-26 18:15:49

      为什么不能建无向图捏，因为无向图是环啊！！！！！！！！👎

  • 0
    @ 2023-5-27 18:04:03

    6 面骰子投出 1 的期望次数

    投出 11 的概率是 16\frac{1}{6}

    投 xx 次才投出 11 的概率 (56)x−116(\frac{5}{6})^{x-1}\frac{1}6{}

    所以期望次数为 $s = \frac{1}{6} + 2\frac{5}{6}\frac{1}{6} + 3(\frac{5}{6})^2\frac{1}{6}+\dots$

    投出 11 的概率是 16\frac{1}{6}

    投 xx 次才投出 11 的概率 (56)x−116(\frac{5}{6})^{x-1}\frac{1}6{}

    所以期望次数为 $s = \frac{1}{6} + 2\frac{5}{6}\frac{1}{6} + 3(\frac{5}{6})^2\frac{1}{6}+\dots$

    6s=1+256+3(56)2+…6s = 1 + 2\frac{5}{6}+ 3(\frac{5}{6})^2+\dots

    $\frac{5}{6}6s = \frac{5}{6} + 2(\frac{5}{6})^2+3(\frac{5}{6})^3+\dots$

    做差得到

    $\frac{1}{6}6s = 1 + \frac{5}{6} + (\frac{5}{6})^2+(\frac{5}{6})^3+\dots$

    即

    $s = 1 + \frac{5}{6} + (\frac{5}{6})^2+(\frac{5}{6})^3+\dots$

    乘以 56\frac{5}{6} 得到

    $\frac{5}{6}s = \frac{5}{6} + (\frac{5}{6})^2+(\frac{5}{6})^3+(\frac{5}{6})^4+\dots$

    做差得到

    16s=1−(56)∞=1\frac{1}{6}s = 1-(\frac{5}{6})^{\infty} = 1

    所以

    s=6s = 6

    • 0
      @ 2023-5-27 16:20:12

      P6154 游走

      与绿豆蛙归宿这道题不同的是 每个点都可以是起点和终点 并且允许从自己走到自己 细节需要处理好

      #include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 1e5 + 5;
const int MOD = 998244353;
int n, m;
int f[N], g[N]; // f表示路径长度和 g表示路径数
vector<int> e[N];
inline int QP(int a, int b, int p)
{
    int ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % p;
        b >>= 1;
        a = (a * a) % p;
    }
    return ans;
}
inline int inv(int x)
{
    return QP(x, MOD - 2, MOD);
}
void dfs(int now)
{
    if (g[now])
        return;
    g[now] = 1; // 初始每个点的路径条数都是1 这条路的长度为0 (自己走向自己)
    for (auto i : e[now])
    {
        dfs(i);
        g[now] = (g[now] + g[i]) % MOD;        // 更新这个点的路径条数
        f[now] = (f[now] + f[i] + g[i]) % MOD; // 当前这个点的长度和需要加上下一个点的长度和并且将下个点的每条边长度加1
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
    }
    for (int i = 1; i <= n; i++)
        if (!g[i])
            dfs(i); // 不知道起点终点 没有保证图是连通的 应当扫一遍都尝试搜
    int sum = 0, cnt = 0;
    for (int i = 1; i <= n; i++)
        sum = (sum + f[i]) % MOD, cnt = (cnt + g[i]) % MOD;
    // 期望 = 总路径长度和 / 总路径条数
    cout << sum * inv(cnt) % MOD << endl;
    // 题目要求给分数取模
}
      • 0
        @ 2023-5-26 18:06:22 
        #include<bits/stdc++.h>
#define int long long
#define double long double
#define endl "\n"
using namespace std;
const int MAXN=100000;
struct E
{
	int v,w;
};
vector<E> e[MAXN+5];
int n,m;
double val[MAXN+5];//每个点期望值 
double dfs(int now)
{
	if(val[now])
		return val[now];
	if(now==n)
		return val[now]=0;
	double res=0;
	for(int i=0;i<e[now].size();i++)
		res+=(dfs(e[now][i].v)+e[now][i].w);
	res/=e[now].size();
	return val[now]=res;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		e[u].push_back({v,w});
	}
	cout<<fixed<<setprecision(2)<<dfs(1)<<endl;
	return 0;
}
      • 0
        @ 2023-5-26 11:36:52

        P4316 绿豆蛙的归宿 

        #include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int MAXM = 200000;
int n, m;
// 反向图：first终点，second权值
vector<pair<int, int>> e[MAXN + 5];
int D[MAXN + 5]; // 正向图的出度
int d[MAXN + 5]; // 反向图的入度（用于拓扑排序，会修改）
queue<int> q;
vector<int> points;   // 排序后的点
double ans[MAXN + 5]; // 期望几步到终点
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[v].push_back(make_pair(u, w));
        d[u]++;
        D[u]++;
    }
    // 拓扑排序 把点按顺序放入 points
    for (int i = 1; i <= n; i++)
        if (d[i] == 0)
            q.push(i);
    for (int sid = 1; !q.empty(); sid++)
    {
        int nowSize = q.size();
        while (nowSize--)
        {
            int u = q.front();
            q.pop();
            points.push_back(u);
            for (int i = 0; i < e[u].size(); i++)
            {
                int v = e[u][i].first;
                d[v]--;
                if (d[v] == 0)
                    q.push(v);
            }
        }
    }
    // 依次求期望
    ans[n] = 0; // 所有点都能到终点
    for (int u : points)
    {
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].first;
            int w = e[u][i].second;
            ans[v] += (ans[u] + w) / D[v];
        }
    }
    cout << fixed << setprecision(2) << ans[1] << "\n";
    return 0;
}
        • 0
          @ 2023-5-26 10:55:24

          P1365 WJMZBMR打osu! / Easy 

          #include <bits/stdc++.h>
using namespace std;
const int MAXN = 300000;
int n;
string s;
// 以第i个字符结尾的，combo 长度的期望
double x[MAXN + 5];
// 前i个字符的得分
double f[MAXN + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    cin >> s;
    s = "^" + s + "$";
    x[0] = 0;
    for (int i = 1; i <= n; i++)
        if (s[i] == 'o')
            x[i] = x[i - 1] + 1;
        else if (s[i] == 'x')
            x[i] = 0;
        else if (s[i] == '?')
            x[i] = (x[i - 1] + 1) / 2;
    f[0] = 0;
    for (int i = 1; i <= n; i++)
        if (s[i] == 'o')
            f[i] = f[i - 1] + (2 * x[i - 1] + 1);
        else if (s[i] == 'x')
            f[i] = f[i - 1];
        else if (s[i] == '?')
            f[i] = (f[i - 1] + (2 * x[i - 1] + 1) + f[i - 1]) / 2;
    cout << fixed << setprecision(4) << f[n] << "\n";
    return 0;
}
          • 0
            @ 2023-5-26 10:42:59

            P1654 OSU!

            #include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n;
double p[MAXN + 5];
// x[i]: i 结尾的连续 1 的长度的期望
double x[MAXN + 5];
// xx[i]: i 结尾的连续 1 的长度平方的期望
double xx[MAXN + 5];
// xxx[i]: i 结尾的连续 1 的长度三次方的期望（用不上）
double xxx[MAXN + 5];
// f[i]: 前 i 个位置时，“sum(每段连续1长度^3)” 的期望
double f[MAXN + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> p[i];
    // (x+1)=x+1
    x[0] = 0;
    for (int i = 1; i <= n; i++)
        x[i] = (x[i - 1] + 1) * p[i];
    // (x+1)^2 == xx+2x+1
    xx[0] = 0;
    for (int i = 1; i <= n; i++)
        xx[i] = (xx[i - 1] + 2 * x[i - 1] + 1) * p[i];
    // (x+1)^3 == xxx+3xx+3x+1（用不上）
    xxx[0] = 0;
    for (int i = 1; i <= n; i++)
        xxx[i] = (xxx[i - 1] + 3 * xx[i - 1] + 3 * x[i - 1] + 1) * p[i];
    // f[i] = f[i-1] + 第i个位置的贡献（对期望的增量）
    f[0] = 0;
    for (int i = 1; i <= n; i++)
        f[i] = f[i - 1] + (3 * xx[i - 1] + 3 * x[i - 1] + 1) * p[i];
    cout << fixed << setprecision(1) << f[n] << "\n";
    return 0;
}
            • 0
              @ 2023-5-26 10:20:33

              CF280C Game on Tree

              如果点 ii 被操作的概率为 pp，那么点 ii 对期望操作次数的贡献就是 1∗p+0∗(1−p)1*p+0*(1-p)

              显然除了根节点到 ii 路径上的点之外，其他的点被选择都不影响 pp。所以先选到 ii 的概率是 1/depi1/dep_i

              #include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n;
vector<int> e[MAXN + 5];
int dep[MAXN + 5];
void dfs(int u, int fa)
{
    for (int v : e[u])
    {
        if (v == fa)
            continue;
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dep[1] = 1;
    dfs(1, 1);
    double ans = 0;
    for (int i = 1; i <= n; i++)
        ans += 1.0 / dep[i];
    cout << fixed << setprecision(8) << ans << "\n";
    return 0;
}
              • 0
                @ 2023-5-24 14:52:12

                P2111 考场奇遇 

                #include <bits/stdc++.h>
using namespace std;
int n, a, q;
string s;
const int MAXN = 50;
// 前i题对了j题的概率
double f[MAXN + 5][MAXN + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> a >> q;
    cin >> s;
    double p = a / 100.0;
    if (q == 0)
        cout << "1.000\n";
    else
    {
        f[0][0] = 1;
        f[0][1] = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= i; j++)
            {
                // f[i][j] = f[i-1][j]*第i题错误的概率+f[i-1][j-1]*第i题正确的概率
                double ac, wa;
                if (s[i - 1] == '0')
                    ac = (1 - p), wa = p;
                else
                    ac = p, wa = (1 - p);
                if (j == 0)
                    f[i][j] = f[i - 1][j] * wa;
                else
                    f[i][j] = f[i - 1][j] * wa + f[i - 1][j - 1] * ac;
            }
        double ans = 0;
        for (int i = q; i <= n; i++)
            ans += f[n][i];
        cout << fixed << setprecision(3) << ans << "\n";
    }
    return 0;
}
                • 0
                  @ 2023-5-24 14:34:54

                  P2719 搞笑世界杯 

                  #include <bits/stdc++.h>
using namespace std;
const int MAXN = 1250;
int n;
// f[i][j]：i张A类票，j张B类票时，最后两个人票一样的概率
double f[MAXN + 5][MAXN + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    n = n / 2;
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
        {
            if (i + j < 2)
            {
                // 不合法情况
                f[i][j] = 0;
                continue;
            }
            if (i == 0 || j == 0)
            {
                // 某种票没有时，一开始就不是抛硬币分票了
                f[i][j] = 1;
                continue;
            }
            // 注意：前面的人买票的类型是通过抛硬币决定的
            // 不管两种票各有多少，只要两种票都有，那么第一个人就是抛硬币买票的
            // 如果第一个人买的是 A 票（50%概率），那么最后两个人一样的概率就是 f[i-1][j]
            // 如果第一个人买的是 B 票（50%概率），那么最后两个人一样的概率就是 f[i][j-1]
            f[i][j] = (f[i - 1][j] + f[i][j - 1]) / 2;
        }
    cout << fixed << setprecision(4) << f[n][n] << "\n";
    return 0;
}
                  • 0
                    @ 2023-5-24 14:17:37

                    P2911 [USACO08OCT]Bovine Bones G 

                    #include <bits/stdc++.h>
using namespace std;
int s1, s2, s3;
int cnt[20 * 20 * 40 + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s1 >> s2 >> s3;
    for (int i = 1; i <= s1; i++)
        for (int j = 1; j <= s2; j++)
            for (int k = 1; k <= s3; k++)
                cnt[i + j + k]++;
    int ans = 1;
    for (int i = 2; i <= s1 + s2 + s3; i++)
        if (cnt[i] > cnt[ans])
            ans = i;
    cout << ans << "\n";
    return 0;
}
                    • 1

                    扩展题单 - 概率与期望

                    信息

                    ID
                    1283
                    时间
                    1000ms
                    内存
                    256MiB
                    难度
                    9
                    标签
                    递交数
                    10
                    已通过
                    10
                    上传者
                    1. 评测队列
                    2. 服务状态
                    3. 兼容模式
                    4. 主题
                    2. 陕ICP备2024054233号
                    3. Worker 0, 64ms
                    4. Powered by Hydro v4.18.1 Community, Modified by 33DAI