六月算法竞赛选题（四）

[[ slider_text ]]

[[ item.c ]]

六月算法竞赛选题（四）

发布时间 2025-06-30 作者：zhangminchen 来源：算法小站

树上问题 期望dp 最短路

## Codeforces Round 857 (Div. 2)
### D
**[D. Buying gifts](https://codeforces.com/contest/1802/problem/D)**
**问题描述**
有两个朋友，现在商店有$$1 \sim n$$个部门，为两个朋友买礼物，会访问每一个部门
选择两种决策之一
```bash
1. 为第一个朋友买礼物，花费 a[i] 元
2. 为第二个朋友买礼物，花费 b[i] 元
```
其中，每个朋友至少应该收到一件礼物，另$$m_1$$是第一位朋友收到的礼物最大值
而$$m_2$$是第二位朋友收到礼物的最大值，需要最小化$$|m_1 - m_2|$$

**算法分析**
和**[数形结合](https://www.ringalgo.com/article/65/)**这个问题有异曲同工之妙
对$$(a_i, b_i)$$二元组排序，枚举$$a$$的最大值是在$$x = a_i$$处取到，维护后缀最大值$$mx[n\cdots 1]$$
然后用一个`set`来维护前缀，其中，`suf = mx[i+1]`是**一定要选`B`的**，现在就看前缀了
前缀可以都选`A`，出现能够使得$$|y - x|$$减小的值$$y$$的时候，才考虑在`y`这个位置选`B`

那么$$y$$主要看两个，`lower_bound(x), --upper_bound(x)`，用这两个`y`值来更新答案，但不一定能够成功
当且仅当$$y \geqslant suf$$，即$$y$$比必须要选的`suf`更大的时候，才可以更新

### E
**[E. Music Festival](https://codeforces.com/contest/1802/problem/E)**
**问题描述**
有$$n$$张专辑，第$$i$$张专辑有$$k_i$$首曲目，分别是$$a_i(1, 2, \cdots, k_i)$$，其中$$a(i, j)$$表示第$$j$$首曲目的酷炫程度
现在你需要安排听专辑的顺序，每一张专辑必须完整听完
如果你听到的曲目，酷炫程度严格大于之前听的所有曲目，那么你的愉悦度`+1`
现在问能获得的最大愉悦度是多少？

**算法分析**
![](/media/content_img/cf857-e.png)

### F
**[F. The way home](https://codeforces.com/contest/1802/problem/F)**
**问题描述**
有$$n$$座城市，给你$$m$$条**有向边**$$(a_i, b_i, s_i)$$，意味着你必须至少有$$s_i$$的钱，才能从$$a_i \to b_i$$
现在有一个魔术师，想从$$1 \to n$$，但他只有$$p$$元钱，同时在城市$$i$$他可以表演魔术赚取$$w_i$$
现在问他能不能到达$$n$$，如果可以，他最少要表演几场魔术？

**算法分析**
![](/media/content_img/cf857f1.png)
![](/media/content_img/cf857f2.png)

## leetcode 455 场周赛
### 完全背包再理解
**[硬币面值还原](https://leetcode.cn/contest/weekly-contest-455/problems/inverse-coin-change/description/)**
**问题描述**
给定从`1`开始的`ways`，其中`ways[i]`表示使用固定面值的硬币（每一种可以使用多次），凑出金额`i`的方案数
每一种面值都是正整数，其值最多为`ways.length`
现在要求输出一个数组，返回硬币的可能面值

**算法分析**
拼凑，每一种硬币可以**选择多次**，这样的条件，应该要自然地想到**完全背包**

> 假设你把已经有的面值放在`a[...]`中，那么你能用它们拼凑出多少面值呢？这些面值的方案数，能不能**打表**？

考虑$$dp(i, x)$$表示用前$$i$$种面值，拼凑出$$x$$面值的方案数
1.不选$$i$$，那么$$dp(i, x) \leftarrow dp(i-1, x)$$
2.选了$$i$$，因为可以选多次，那么下一次还可以从$$i$$开始选
那么$$dp(i, x) \leftarrow dp(i, x - a_i)$$

> 打表完面值之后，暴力找下一个能加入`a`的，一定是`ways[x] = dp[x] + 1`的，最小的$$x$$
为什么呢？因为$$x$$不在`a`中，所以统计方案数的时候，没有算过`x = {x}`，$$x$$仅由它本身拼成的这种情况

如果$$ways(x) = dp(x) + 1$$，那么$$a \leftarrow \\{x\\}$$

> 做完之后，再来一遍 dp，看看 `ways` 和 `dp[...]` 能否对应上

### 使叶子路径成本相等的最小增量
**[使叶子路径成本相等的最小增量](https://leetcode.cn/problems/minimum-increments-to-equalize-leaf-paths/description/)**
**问题描述**
给定一棵树，要使得每一条从根节点到叶子结点路径，它们的点权和相等。你可以任意选择一些点，增加其点权
问你最少需要选择几个点来增加点权（只关心节点数，不关心具体增加了多少）

**算法分析**
因为点权只能增加，不能减少，所以最终所有的路径点权和是确定的，为`maxsum`
其中，`maxsum`是所有路径点权和的**最大值**

贪心地改，如果一定要改，那么在`LCA 甚至更远的祖先`位置去修改，是划算的，因为一次修改可以影响好几个儿子

用`dp(u)`表示节点`u`到叶子结点，所经过的路径的**最大权值和**，这个可以通过一遍`dfs`维护出来
第二遍`dfs`，用$$S$$表示从根节点到`u`（不包括`u`）所经过的路径和，那么**修改后的最终状态**
从`u`到**叶子结点**的所有路径，它们的权值和都必须是`mxrem = mxsum - S`
如果`dp(u) = mxrem`，那么$$u$$节点是不需要修改的
否则$$u$$节点应该增加相应的值，`+= mxrem - dp(u)`

> 这里是个贪心，`u`到叶子有很多路径，你应该更改**最大权值和**的路径，否则，你对较小的权值进行操作
很有可能**修改过头了**

如果修改`u`，那么`u 之后的子树都要修改`，一种是用`dfs 序`，但太麻烦，可以记忆化
记忆化每个节点的**增量**`add(u)`
```bash
dp(u) + add(u) < mxrem，那么要修改
auto d = mxrem - dp(u) - add(u)
add(u) += d

for (auto v : g[u])
	if (v == fa) continue
	add(v) += add(u)
```

> 反正都要改，那么`dfs`自顶向下，在第一个`dp(u) < mxrem`的祖先`u`处，就开始改，这样是最划算的

## 从子集的和还原数组
**[从子集的和还原数组](https://leetcode.cn/problems/find-array-given-subset-sums/description/)**
给你一个数组`nums`，由未知数组中全部的$$2^n$$个子集的和组成（子集中的元素没有特定顺序）
现在要求你构造一个长度为`n`的，这个未知的数组

**算法分析**
![](/media/content_img/lc-subset.png)

### 算法实现
**注意，枚举子集的时候**，当且仅当`a`的最后一个位置状态为`1`的时候，才被认为**状态有效**
也就是说，我们每次只考虑**在 a 的尾巴加入一个元素**

```bash
class Solution {
public:
    vector<int> recoverArray(int N, vector<int>& sums) {
        multiset<int> st;

auto calc = [&](const vector<int> &a) {
            int n = a.size();
            // for subset in a

for (int sta = 0; sta < (1<<n); sta++) if (sta >> (n-1) & 1) {
                int sum = 0;

for (int i = 0; i < n; i++) if (sta >> i & 1) sum += a[i];

st.extract(sum);
            }
        };

auto mn = *min_element(sums.begin(), sums.end());

bool hasnega = false;
        if (mn < 0) hasnega = true;

auto offset = abs(mn);
        for (auto x : sums) st.insert(x + offset);

st.extract(0);
        vector<int> a;
        a.push_back(*st.begin());

for (int i = 1; i < N; i++) {
            calc(a);    
            a.push_back(*st.begin());
        }

if (!hasnega) return a;
        
        for (int sta = 0; sta < (1 << N); sta++) {
            int sum = 0;
            for (int i = 0; i < N; i++) if (sta >> i & 1) {
                sum += a[i];
            }

if (sum == offset) {
                for (int i = 0; i < N; i++) if (sta >> i & 1) {
                    a[i] = -a[i];
                }
                break;
            }
        }

return a;
    }
};
```

## Nebius Welcome Round
### C
**[C. Pull Your Luck](https://codeforces.com/contest/1804/problem/C)**
**问题描述**
给你一个转盘，从$$0\to 1\to 2 \cdots \to n-1 \to 0$$转动，指针目前指向$$x$$
现在你可以用`f`的力拉转盘，转盘会转动`f`秒，每一秒分别前进`{f, f-1, f-2, ....., 1}`单位
问你能否选择一个合适的`f`，使得指针指向`0`，`f`有限制$$1 \leqslant f \leqslant p$$

**算法分析**
题目意思，说人话，就是找到一个$$1 \leqslant f \leqslant p$$，使得$$\left( x + \dfrac{f(f+1)}{2} \right) \bmod n = 0$$

那么枚举$$f$$，本来应该要枚举到$$O(10^9)$$，但是不需要那么多
只需要$$\left( x + \dfrac{f(f+1)}{2} \right)$$取遍$$n$$的剩余系$$\\{0, 1, \cdots, n-1\\}$$即可
令$$f(f+1)/2, \quad f = 2n$$，那么$$f(f+1) / 2 = n \cdot (2n + 1)$$一定能够取遍$$n$$的剩余系

> 为什么呢？首先$$f \in[1, 2n]$$，所有的偶数都可以取的到，$$f / 2$$就已经枚举了$$\leqslant n$$的所有偶数
奇数呢？注意到$$(f+1)$$一定是偶数，那么奇数就是`(<= n 的所有奇数) * (?)`，一定也可以取到

## AtCoder Beginner Contest 412
### E
**[E - LCM Sequence](https://atcoder.jp/contests/abc412/tasks/abc412_e)**
定义$$A_n$$是前缀$$1\cdots n$$的最小公倍数，现在问
```math
A_{L}, A_{L+1}, \cdots, A_{r}
```
有多少个不同的数

**问题描述**
什么时候，$$A\_{i-1} \to A\_{i}$$是会不变的呢？不妨设
```math
p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_i^{\alpha_i} \cdots
```
1.若$$p_i^{\alpha_i}$$是$$p_i$$这个素数**前缀中出现的最大幂指**，最大幂指就是$$\alpha_i$$
那么从$$i-1 \to i$$，`LCM`是不会变的

2.而另一方面，如果幂指$$\alpha\_i$$**增加**，那么有$$A\_i \leftarrow A\_{i-1} + 1$$

3.关于枚举$$p$$，如果$$p \cdot p > R$$，那么从$$[L, R]$$中，前缀含有$$p$$的因子，幂指数是不会变化的
前缀最多就是包含$$p$$，不可能有$$p \cdot p$$，关于$$p$$的因子，指数不变
从而最大就是$$p \in [1, \sqrt{R}]$$暴力枚举

做法其实不难
1.考虑$$\leqslant L$$出现的所有素数，当然必须满足$$p \cdot p \leqslant R$$并且$$p \leqslant L$$
这些$$p$$是$$L \to R$$幂指可能会发生变化的

分别暴力到$$L$$为止，$$p^{?} \leqslant L$$的**最大幂指**$$pwl(p)$$
以及$$p^{?} \leqslant R$$的**最大幂指**$$pwr(p)$$，那么对答案的贡献就是$$+(pwr_p - pwl_p)$$

2.区间筛，$$[L, R]$$中出现的所有素数，这部分素数一定是从幂指是`0`开始增加，增加到$$p^{?} \leqslant R$$的最大幂指$$pwr(p)$$
贡献就是$$pwr_p$$

### D
**[D - Make 2-Regular Graph](https://atcoder.jp/contests/abc412/tasks/abc412_d)**
对一个无向图，执行以下操作任意顺序，任意次
```bash
- 增加任意一条边
- 删除任意一条边
```
问要使得无向图**所有节点都是**`2`，最少要操作多少次？

#### 排列数枚举的一个方法
> 生成下一个具有相同数量 `1` 的二进制位的组合
![](/media/content_img/abc412D.png)

#### 算法分析
看数据范围，不难想到是一个**状态压缩**，所有点的度数都是`2`，最终的图是什么形态呢？
一定是若干个`size >= 2`的环，具有以下性质
恰好有$$n$$个点，$$n$$条边，同时每个点的`deg = 2`

这里操作的是边，可以**枚举所有的边集**，所有可能的边集是$$n(n-1)/2 = O(28)$$，状态数很小
对完全图的边集，压状态，$$(i, j), i < j$$，用一个位来表示这条边，所有的边集记为$$|tot|$$

这样就可以暴力$$|E| \subset |tot|$$了，其中$$|E| = n$$，那么只要用上面的**生成相同数量 1 的二进制枚举**方法即可

**枚举最终的边集**$$|E|$$，什么时候是合法的呢？
1.$$|E| = n$$，这可以通过枚举相同数量的二进制来实现
2.对每个$$|E|$$，统计`deg`，如果每个点的`deg = 2`，那么就是合法的最终边集
3.初始状态的边集假设是$$|ori|$$，$$|E| \oplus |ori|$$就是最后需要修改的答案
（删边，加边，分别算 2 次）

### F
**[F - Socks 4](https://atcoder.jp/contests/abc412/tasks/abc412_f)**
**问题描述**
抽屉里面有$$n$$种颜色的袜子，颜色$$i$$的袜子有$$a_i$$只，一开始呢，你在抽屉外有一只颜色是$$C$$的袜子
每一次操作，你要从抽屉中随机抽一只，如果抽屉外的袜子颜色相同，那么结束
否则你需要选择一只袜子将其放回，然后继续
现在求操作的**最小期望次数**

**算法分析**
![](/media/content_img/abc412-f1.png)
![](/media/content_img/abc412-f2.png)

> 还有一个坑点，因为要对$$a$$排序，那么答案就不再是$$dp(c)$$了，而应该是$$dp(toC)$$
其中，$$toC$$表示颜色$$C$$在排序后的数组中的下标

## 百度之星2025第一场
**题目大意**
如果一个节点的`deg`是奇数，那么要选择任意一个方向来切断（作为端点），剩下的不切断，
需要**两两配对**
如果一个点的`deg`是偶数，一定不能切断，直接两两配对

如果$$n = 2k$$，这些点两两配对的方案数是多少呢？
```bash
第 1 个点，找配对，方案数 2k - 1
第 2 个点，找配对（剩下一共 2k - 2 个点，能配对的不同点只有 2k - 3）方案数 2k - 3
第 3 个点，2k - 5
......
......
```
综上所述，方案数是$$(2k - 1)(2k - 3)(2k - 5) \cdots 1 = (2k - 1)!!$$

如果$$n = 2k + 1$$，那么先选一个作为断开的点，方案数是$$n$$，剩下的$$n - 1$$个点两两配对
方案数是$$n \cdot (n - 2)!! = n !!$$

上一篇：六月算法竞赛选题——概率与期望（三）已经是最后一篇啦

看完文章有啥想法