六月算法竞赛选题——概率与期望（二）

[[ slider_text ]]

[[ item.c ]]

六月算法竞赛选题——概率与期望（二）

发布时间 2025-06-14 作者：秋千月 来源：算法小站

树上问题 期望dp gcd

## ABC 144
### F
**[F - Fork in the Road](https://atcoder.jp/contests/abc144/tasks/abc144_f)**
**问题描述**
有$$n$$个点，$$m$$条边的有向图，高桥在房间`1`，要渠道房间`n`，道路$$i$$，$$s_i \to t_i (s_i < t_i)$$
给定数据保证，除了房间`n`，其他房间都至少有一条道路能够连到其他房间
现在高桥在某个房间，会等概率选择一条道路走到下一个房间，直到他到达`n`，青木会删掉一条道路
使得高桥从`1`号房间走到`n`号房间，期望道路数最小，求这个最小值

**算法分析**
> 不删道路怎么算

```math
\displaystyle
dp(u) = \left(\dfrac{1}{deg(u)} \cdot \sum_{v \in G(u)}dp(v) \right) + 1
```

> 现在要删道路，很套路地，令$$dp(u, 0)$$表示$$u$$这个点有没有被删过

关于$$dp(u, 0)$$的转移并不难
```math
\displaystyle
dp(u, 0) = \left(\dfrac{1}{d_u} \cdot \sum_{v \in G(u)} dp(v, 0) \right) + 1
```
关于$$dp(u, 1)$$的转移，要么在$$u$$这个点删道路，要么在$$u$$后继的某个点已经删过了
枚举删的是哪个点$$v_0$$

如果在$$u$$这个点删
```math
\displaystyle
dp(u, 1) = \left( \dfrac{1}{d_u - 1} \cdot \sum_{v \neq v_0} dp(v, 0) \right) + 1
```
如果在$$u$$的后继删
```math
\displaystyle
dp(u, 1) = \left(\dfrac{1}{d_u} dp(v_0, 1) + \dfrac{1}{d_u}\sum_{v \neq v_0} dp(v, 0) \right) + 1
```
> 优化

这样在`dfs`的时候，可能还需要枚举删除哪个儿子，复杂度会到$$O(n^3)$$
首先，对于不删的情况，是很简单的，一遍`dfs`即可算出结果
那么删除呢？枚举删除的边$$(from, to)$$，实际上，我们只需要**枚举发生删除的点**$$from$$即可
因为`from`出发一定会删一条边的话，实际上，要使得期望最小，**这样的边是确定的**

比如说，我们枚举在$$u$$这个节点发生删除，那么一定是选择$$dp(v, 0)$$**最大的**那个边$$(u, v)$$删除
而这样的最大值，是可以在第一轮`dfs`的时候算出来的

自底向上记忆化，对于不会删除的点，转移仍然是$$dp(u) = \left( \dfrac{1}{d_u} \sum dp(v) \right) + 1$$

### 算法实现
```bash
void solve(int cas) {
    int n, m;
    cin >> n >> m;

vector<vector<int> > g(n+1);
    vector<int> deg(n+1, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].emplace_back(v), deg[u] += 1;
    }

vector<double> dp(n+5, inf<int>);

auto dfs = [&](auto &dfs, int u) -> double {
        auto &ans = dp[u];
        if (ans < inf<int>) return ans;

if (deg[u] == 0) return ans = 0.0;

double sum = 0.0;
        for (auto v : g[u]) {
            sum += dfs(dfs, v);
        }
        ans = 1.0 + sum / deg[u];
        return ans;
    };

double ans = dfs(dfs, 1);

auto dfs2 = [&](auto &dfs2, int u, const int del) -> double {
        auto &ans = dp[u];
        if (ans < inf<int>) return ans;

if (deg[u] == 0) return ans = 0.0;
        
        if (u == del && deg[u] > 1) {
            double sum = 0.0, mx = 0.0;
            for (auto v : g[u]) {
                auto dpv = dfs2(dfs2, v, del);

sum += dpv, chmax(mx, dpv);
            }

ans = 1.0 + (sum - mx) / (deg[u] - 1);
        }
        else {
            double sum = 0.0;
            for (auto v : g[u]) sum += dfs2(dfs2, v, del);

ans = 1.0 + sum / deg[u];
        }

return ans;
    };

for (int del = 1; del <= n; del++) {
        dp.assign(n+5, inf<int>);

chmin(ans, dfs2(dfs2, 1, del));
    }

cout << ans << "\n";
}
```

## Pinely Round 3
### D
**[D. Split Plus K](https://codeforces.com/contest/1909/problem/D)**
**问题描述**
给定$$n$$个正整数序列`a`，同时给定一个正整数$$k$$，你可以执行以下操作若干次
选择一个$$x$$，并且删掉它（如果有多个，只删除其中一个），然后再次放入两个正整数$$y, z$$
满足$$y + z = x + k$$

现在问，能否使得所有的数都相同？如果可以，输出最小操作次数

**算法分析**
对于数$$a_i$$，假设发生了$$t_i$$次拆分，最后都变成相等的数，那么有
```math
val \cdot (t_i + 1) = a_i + kt_i
```
要使得$$\displaystyle \dfrac{a_i + kt_i}{t_i + 1}$$都相等，并且最小化$$\sum t_i$$
```math
\displaystyle
\sum_{i=1}^{n} (t_i +1) = \dfrac{\sum_{i} (a_i - k) }{val - k}
```
其中$$a_i - k$$在每一个位置是确定的，要使得$$\sum t_i$$尽量小，那么$$val - k$$要尽可能大
因为$$val$$是从$$a_i$$中分裂出来的

所以有$$val - k \leqslant a_i - k$$，而右边$$\sum \dfrac{a_i - k}{val - k}$$又必须是**整数**
所以$$val - k = gcd(a_i - k)$$即可，求出最优条件下的$$val$$

> 那什么时候不合法呢？

注意到，$$\dfrac{\sum_i(a_i - k)}{val - k}$$必须要是整数，所以$$(val - k) \mid gcd(a_i - k)$$
而对于某个特定的$$i$$，$$t_i + 1 = \dfrac{a_i - k}{val - k} = ( (a_i - k)\text{的某个因子} )$$

不管$$val - k$$取$$gcd(a_i - k)$$还是取$$gcd$$的因子，都不会改变右边的**正负性**
就取$$val - k = gcd(a_i - k)$$，如果发现求出来$$t_i < 0$$，直接判不合法

## Codeforces Round 870 (Div. 2)
### D
**[D. Running Miles](https://codeforces.com/contest/1826/problem/D)**
**问题描述**
有若干个点，位于$$[1, 2, \cdots, n]$$，其中第$$i$$个点有美丽值$$b_i$$，现在你需要找到$$l, r$$
使得$$[l, r]$$中至少有 3 个景点，并且美丽值最大的 3 个景点记为$$b(i_1), b(i_2), b(i_3)$$
要求最大化$$(b(i_1) + b(i_2) + b(i_3)) - (r - l)$$

**算法分析**
> 首先有一个贪心结论

假设说最大的三个数是$$vl, mid, vr$$，那么很显然，其中两个数分别位于$$l, r$$处，恰好作为**Fence**
剩下的一个数$$\in [l+1, r-1]$$，并且必须是这个区间内最大的数

> 那么好像可以动态规划，考虑$$dp(i, 0/1/2)$$表示在$$i$$这个位置，已经选了最大的`1/2/3`个数
此时的最优解，这样做对吗？

那么不难发现，假设最大的三个数，**从左到右**分别是$$a_l, a_i, a_r$$，$$res = a_l + a_i + a_r - (r - l)$$
也就是说，$$res = (a_l + l) + (a_i) + (a_r - r)$$

那么我们每个位置可以维护$$x = a_i$$，维护三元组$$last = \\{?, ?, ?\\}$$，转移到$$dp = \\{?, ?, ?\\}$$
有几种决策

1.$$x$$要么冲掉$$last(0)$$，作为一个新的$$dp(0)$$，$$dp(0) \xleftarrow{\max} \max(last(0), x + i)$$
2.$$x$$冲掉$$last(1)$$，$$0$$这个位置沿用上个阶段的

> 值得注意的是，这个时候$$x$$是不是一定是**有贡献**的呢？如果$$x$$太小，$$x$$是构不成最大的三个元素的！
但所幸的是，上个阶段有贡献的最大三个值是$$last(0), last(1), last(2)$$，如果$$x$$能够顺利冲掉$$last(1)$$
说明$$x$$的值一定会比$$last(1)$$来的更大，$$x$$加入集合中，也一定是有贡献的

此时有转移$$dp(1) \xleftarrow{\max} last(0) + x$$

3.$$x$$冲掉$$last(2)$$，那么不妨设原来$$last(2)$$上面，对应选的元素是$$oldx$$，下标是$$r_1$$
此时的下标是$$r_2$$，那么一定有$$r_2 > r_1$$，而算贡献的时候，我们算的是$$x - r$$
能够冲掉，当且仅当$$x - r_2 \geqslant oldx - r_1$$，那么一定有$$x - oldx \geqslant r_2 - r_1 > 0$$
换句话说，新选进来的一定满足$$x > oldx$$，$$oldx$$都有贡献，那么$$x$$一定是有贡献的

此时转移$$dp(2) \xleftarrow{\max} last(1) + (x - r)$$自然也成立

## CodeTON Round 9
### D
**[D. Shohag Loves GCD](https://codeforces.com/problemset/problem/2039/D)**
**问题描述**
给你一个$$n$$和一个大小为$$m$$的集合$$S$$，其中$$S$$中的元素各不相同
你现在要找到字典序最大的序列$$a_1, a_2, \cdots a_n$$，同时满足

对于所有的$$i \in [1, n]$$，有$$a_i \in S$$，对于所有的$$1 \leqslant i < j \leqslant n$$

有$$a\_{gcd(i, j)} \neq gcd(a\_i, a\_j)$$，不满足输出`-1`

**算法分析**
题目不难，自己想出来的，类似**素数筛**的思想
首先，`a[1]`一定要填上$$mx$$，$$mx$$表示最大的元素，那么之后呢？
之后`1`的倍数，也就是所有的位置，一定不能填上$$mx$$，那么就应该填**次大元素**，假设是$$y$$

考虑$$2$$这个位置，实际上，$$2$$是一定要填上$$y$$的，于此同时，`j = (2 的倍数)`的位置，一定都不能填上$$y$$

这样算法就好想了，对于每个位置$$i$$，记一下`forbid[i] = set{...}`，表示$$i$$这个位置不能填哪些数
然后呢？对于给定的集合排个序，从大到小了填，尝试在$$i$$这个位置填上$$y$$，如果`forbid(i)`包含了$$y$$，那么就减小$$y$$
直到找到这样的$$y$$填上去
与此同时，标记$$j \in (2i, 3i, \cdots )$$所有$$i$$的倍数，`forbid(j).insert(y)`

## Codeforces Round 992
### D
**[D. Non Prime Tree](https://codeforces.com/problemset/problem/2040/D)**
**问题描述**
有一个$$n$$节点的树，给树的每个点赋权值，权值必须两两不同，并且点权值必须$$\in [1, 2n]$$
相邻的点的权值之差，必须**不是素数**

**算法分析**
看到提示，$$\in [1, 2n]$$，不难想到，偶数除了`2`之外，一定都不是素数，$$n$$个节点，配上$$2 \sim 2n$$中的偶数，好像就可以了

怎么构造呢？
可以考虑`bfs`，然后按层来对节点进行分类，相邻的点，恰好位于相邻的层中
那么奇数层，从左到右，按`2, 4, 6, ....`，依次递增放
偶数层呢？从右到左，按`2n, 2n-2, ....`，依次递减放

这样**最多就只有一个**相邻的点对$$(pa, u), |pa - u| = 2$$，不满足，并且这样的点对一定在叶子处
我们令$$u$$为叶子结点，将其权值改成$$u' = u +1$$，这样$$pa - u' = 1$$，恰好满足条件

### E
**[E. Control of Randomness](https://codeforces.com/contest/2040/problem/E)**
**问题描述**
给定$$n$$个点的树，然后你放一个机器人在$$v \neq 1$$的节点上，一开始有$$p$$枚硬币
然后执行以下步骤，第$$i$$步（从`i = 1`开始）
1.如果$$i$$是奇数，那么机器人向根节点$$v = 1$$方向移动一个单位
2.如果$$i$$是偶数，你可以支付 1 枚硬币，让机器人向$$v = 1$$方向移动一个单位
或者呢，不付钱，那么机器人移动到**相邻的，随机的点**

以上过程停止，当且仅当机器人到达顶点`1`，令$$f(v, p)$$表示最小期望移动次数（如果我们花费硬币采用最优策略）
输出`q`个询问的答案，第$$i$$个询问，你需要回答$$f(v_i, p_i)$$

**算法分析**
状态设计不难，$$dp(u, 0/1, p)$$表示当前在$$u$$这个点，并且将执行`0-偶数，1-奇数`步的方案
同时还剩下$$p$$枚硬币，此时的**最小期望移动次数**

初始状态，$$dp(1, 0/1, \forall p) = 0$$，最后的答案是$$dp(v, 1, p)$$

考虑$$(u, v)$$
1）假设说$$v$$将执行奇数步，$$dp(v, 1, p) \leftarrow dp(u, 0, p) + 1$$
2）如果$$v$$将执行偶数步，$$dp(v, 0, p) \leftarrow dp(u, 1, p-1) + 1$$，这是付钱的情况
不付钱呢？情况比较复杂了，这里用$$d$$表示点的 **deg**
```math
\displaystyle
dp(v, 0, p) \leftarrow 1 + \dfrac{1}{d(v)} \left( dp(u, 1, p) + \sum_{\forall son(v)} dp(son(v), 1, p) \right)
```
而这是一个**有后效性的递推**，但是我们有$$dp(son(v), 1, p) \leftarrow dp(v, 0, p) + 1$$
```math
\displaystyle
dp(v, 0, p) \leftarrow 1 + \dfrac{1}{d(v)} \left( dp(u, 1, p) + (d(v)-1) \cdot (dp(v, 0, p) + 1)\right) \\
\quad \\
dp(v, 0, p) = dp(u, 1, p) + 2d(v) - 1
```
这样就可以 dp 了，对每个询问，回答$$dp(v_i, 1, p_i)$$即可

上一篇：五月算法竞赛选题（一）已经是最后一篇啦

看完文章有啥想法