2026年五月算法竞赛选题（二）

[[ slider_text ]]

[[ item.c ]]

2026年五月算法竞赛选题（二）

发布时间 2026-05-18 作者：秋千月 来源：算法小站

树链剖分 莫比乌斯反演

## Codeforces Round 1049 (Div. 2)
### D
**[D. A Cruel Segment's Thesis](https://codeforces.com/contest/2140/problem/D)**
给定`n`条线段，用$$[l_i, r_i]$$来描述，一开始都没有标记，如果目前有至少`2`条未被标记的线段
任选两条，把他们标记，并且新增一条标记线段$$[x_k, y_k]$$
必须满足$$l_i \leqslant x_k \leqslant r_i, \quad l_j \leqslant y_k \leqslant r_j$$
如果某次操作，剩下落单的，直接标记

求标记线段的长度和，线段长度定义为$$r - l$$

**算法分析**
分为两部分
```math
\text{way1: }(r_i - 2l_i) + (2r_j - l_j) \\
\text{way2: }(r_j - 2l_j) + (2r_i - l_i)
```
考虑一下什么时候`way2 >= way1`，然后决策哪些线段放左边，哪些线段放右边
放左边的贡献就是$$r_j - 2l_j$$，右边类似

偶数情况就做完了，奇数情况分两种，左边比右边多1，右边比左边多1
针对这两种情况，枚举左边落单的线段，和右边落单的线段，`-(原来的贡献) + (r - l)`来更新答案

## Codeforces Round 1048 (Div. 1)
**[C1. Maple and Tree Beauty (Easy Version)](https://codeforces.com/contest/2138/problem/C1)**
给定`n`个顶点，每个点可以填`0 or 1`，定义字符串，是从根节点到当前节点路径上的字符拼接而成
现在给定`n, K`，要求你填恰好`K`个`0`和`n - K`个`1`，求出所有叶子节点对应的字符串，它们的最长公共子序列长度（不要求连续）

**算法分析**
1）最长公共子序列，最大的长度就是`L = mindep(u)`
2）考虑分层来背包，自顶向下，越上面的，越要尽可能把`0`给消耗掉，考虑`dp`
3）同一层的，尽量填相同的，记一下第$$i$$层的节点数`cnt[i]`，$$k$$表示当前用掉了多少个`0`
用可行性`dp`，表示能不能到达这一层
```math
ndp(k) = \max(dp(k)+1, dp(k-cnt_i) + 1)
```
检查一下`放的 1 和放的 0`有没有超，另外`1, 0`的个数有上界，要设计不合法的状态`-1`

第`i`层的时候，如果`dp(k)`状态可达，那么最长公共子序列长度可以是`i`

> hard 版本，$$O(n = 10^5)$$

实际上这个问题不是一个最大值问题，而是一个**合法性判断**的问题
这样就可以用 **bitset 优化**来求解了

这可以用`bitset 背包`，$$dp(k) = 1$$，表示在当前层$$[1\cdots i-1]$$，存在一种方案，使得恰好用掉了$$k$$个`0`
并且**每一层都是填相同的数**，决策第$$i$$层填$$num_i$$个数，填`0`还是`1`

如果放`1`，那么$$ndp(k) = dp(k)$$
如果放`0`呢，那么$$ndp(k+num_i) = dp(k)$$，这可以写成$$dp(k) \ll num_i$$

只不过这个问题有限制，就是`0`的个数不能超过`K`，`1`的个数不能超过`totone`
那么假设枚举有$$k$$个`0`，当前已经考虑过的节点总数是$$sum$$
```math
\displaystyle
\begin{cases}
0 \leqslant k \leqslant \min(K, sum) \\
sum - k \leqslant totone
\end{cases}
```
这样得到$$k \in [sum - totone, \min(K, sum)]$$，在这个区间内只要找到一个合法的$$k$$
当前层`i`就满足，可以用来更新答案

```bash
for (int k = 0; k <= min(sum, K); k++) {
	ndp[k] = dp[k];
    if (dp[k] == 1)    ndp[k + num] = 1;
}

用 bitset 优化
dp |= (dp << num)
```
## Codeforces Round 1045
### D
**[D. Sliding Tree](https://codeforces.com/problemset/problem/2134/D)**
给定一棵树，一次操作，选择任意一个`deg >= 3`的点，选定`a, b, c`
以`b`为中心，把`b 中除了 a, c 的，相邻的点`拆下来，接到`c`上
问使得一棵树成为一条链的最小代价，输出你第一次选的`a, b, c`

**算法分析**
从直径考虑，抽出直径，如果直径旁有侧枝需要“修剪”，那么修去侧枝的代价是固定的
代价是`cost(u) = u 到 侧枝叶子的距离 dist[u]`，也就是说，需要`dis[u] = |u -> leaf|`这么多操作
才能消除`u`的一条侧枝

归纳，不难发现将树变成一条链的最小代价是$$n - 1 - D$$，其中`D`表示**树的直径**

## 2026“钉耙编程”中国大学生算法设计春季联赛8
### 1006
**[忠犬PARE公](https://acm.hdu.edu.cn/contest/problem?cid=1204&pid=1006)**
给定两个序列$$a, b$$，求
```math
\displaystyle
\sum_{i = 1}^{n} \sum_{j = 1}^{m} \dfrac{\text{lcm}(a_i, b_j)}{\text{gcd}(a_i, b_j)}
```
**算法分析**
比较套路的莫比乌斯反演，原式可以写成
```math
\displaystyle
\sum_i \sum_j \dfrac{a_i b_j}{\text{gcd}(a_i, b_j)^2}
```
枚举$$\text{gcd} = d$$，那么我们要求
```math
\displaystyle
\textbf{let } f(d) = \sum_i \sum_j a_i b_j \cdot [\text{gcd}(a_i, b_j) = d] \\
\sum_{d} \dfrac{f(d)}{d^2}
```
接下来就是**莫比乌斯的套路化简**
枚举$$d$$的倍数，定义
```math
\displaystyle
g(d) = \sum_{d \mid d'} f(d') = \left( \sum_{i}  a_i [d \mid a_i] \right) \left( \sum_j b_j [d\mid b_j] \right)
```
那么`for d = 1 to N`，$$g(d)$$可以预处理打表，枚举每一个`d`，枚举$$d$$的倍数
统计一下`cntA(d 的倍数)，cntB(d 的倍数)`即可

接着考虑计算$$f(d)$$
```math
\displaystyle
f(d) = \sum_{d \mid x} \mu (\dfrac{x}{d}) g(x)
```
计算$$\sum f(d) / d$$即可

### 1007
**[向后全速前进](https://acm.hdu.edu.cn/contest/problem?cid=1204&pid=1007)**
有一个长度为$$n$$的序列$$a$$，其中$$a_i$$在$$[l_i, r_i]$$中等概率生成，服从均匀分布

求$$\sum\_{i = 2}^{n} |a\_i - a\_{i-1}|$$的期望

**算法分析**
根据期望的线性，只需要对每个$$i$$，求出$$E(|a\_i - a\_{i-1}|)$$，它符合均匀分布
已知$$X$$在区间$$[A, B]$$上服从均匀分布，那么概率密度函数是
```math
\displaystyle
f_X(x) = \begin{cases} \dfrac{1}{B - A}, x \in [A, B] \\ 0 \end{cases}
```
同理
```math
\displaystyle
f_Y(y) = \begin{cases} \dfrac{1}{D - C}, y \in [C, D] \\ 0 \end{cases}
```
所以联合概率密度是
```math
f(x, y) = f_X(x) \times f_Y(y)
```
综上所述
```math
\displaystyle
E[|x - y|] = \dfrac{1}{(B-A)(D-C)} \int_{A}^{B} \int_{C}^{D} |x-y|dxdy
```
> 多重积分
```math
\displaystyle
\int_{C}^{D} |x - y|dxdy = \left[ -\dfrac{1}{2}(x-y)|x-y| \right]_{y = C}^{y = D} \\
= -\dfrac{1}{2}(x-D)|x-D| + \dfrac{1}{2}(x-C)|x-C|
```
再考虑对$$x$$积分
```math
\displaystyle
\left[-\dfrac{1}{6} (x-D)^3 + \dfrac{1}{6}(x-C)^3 \right]_{x = A}^{y = B}
```

> 特别地，如果$$A = B$$，那么就变成一重积分了
```math
\displaystyle
\dfrac{1}{D-C} \int_{A}^{B} |y - A| dy \\
\quad \\
=\dfrac{1}{D-C} \dfrac{1}{2} \left[ (y - A)|y - A| \right]_{y = C}^{y = D}
```

### 1009
**[怪演?二十面?相](https://acm.hdu.edu.cn/contest/problem?cid=1204&pid=1009)**
有`n+2`个格子，每个格子的颜色是红、黑、白，你可以从格子$$i$$跳到格子$$j$$
满足$$i \leqslant j$$，现在一轮游戏，`A, B`轮流，`A`可以跳红色和白色格子，`B`可以跳黑色和白色格子
跳到`n+1`个格子，一轮就结束了，然后开始下一轮
在一轮中，白色格子可以原地跳，红色和黑色只能经过一次
然后开启下一轮，问最少要多少轮次，可以经过所有的格子至少一次

**算法分析**
如果没有白色格子，那么一轮游戏构成`R -> B -> R -> B -> ...`这样交替的链
答案就是**最小链覆盖**

求最小链覆盖也很简单，维护`cntR, cntB`，如果遇到`B`，那么接在`R`后面，消耗掉`R`，`cntR--`
（相当于为`R`找后继）
如果没有`R`可以消耗了，要新开一条链`cntB++`，答案就是`cntB + cntR`

这样就构成了若干不相交的连通块

现在有白色节点，**轮与轮之间，可以通过原地跳`W`来把 “合并不同的连通块”**
让轮数多的连通块，“吸收”轮数小的，这样在完成“大轮”的同时，顺带完成“小轮”

### 1001
**[非凡之星](https://acm.hdu.edu.cn/contest/problem?cid=1204&pid=1001)**
给定`n`个点`m`条边的无向连通图，每条边通过时长是`1 个单位`，一开始`Alice`在节点`1`
而`Bob`在节点`n`，Alice 会从`1`号点走一条最短路到达`n`号点，同时再从`n`号点走最短路回到`1`号点
两条最短路相互独立，第一次选择走的路，不一定第二次一定要走
如果有多条最短路，走任意一条

`Bob`从`n`走到`1`，可以在原处停留`1min`或者移动到相邻节点
并且要满足，不论`Bob`怎么移动，都不会和`Alice`相遇
相遇的定义为：在同一时刻两人到达同一个结点或者同一时刻两人经过同一条边

如果`Bob`能够到达一号点，并且时间严格小于`Alice`**回到`1`号点**的总时间
输出答案，否则输出`-1`

**算法分析**
> 边权都是`1`，可以通过`bfs`找最短路

两个人同时开始动，对于每个点来说，记录一下`Alice`和`Bob`到达的**时间戳**
也就是距离编号，如果距离编号相等，说明相遇

哪些点`Alice`一定会经过呢？先一遍求出最短路`mindist`
1）从`1`开始`bfs`得到每个点的距离标号`dis1`
2）从`n`开始反向`bfs`得到每个点的距离标号`disn`

一个点$$u$$一定会被经过，当且仅当$$dis1_u + disn_u = \text{mindist}$$
这样可以标记每个点是不是关键点`key[u]`

> 接下来考虑`Bob`的策略，从`n`开始逐层扩展，维护距离标号`D`

如果`Bob`不动的话，是一定会和`Alice`相遇的
但我们发现，`Bob`最优的路径，也是沿着$$n \to 1$$**最短路**走的
贪心地，我们要在`Alice`还没有发现我们的时候，抢先把这些位置都走了

可以用**多源最短路**，什么叫**“还没有发现”**
就是满足$$\text{key}\_u = 1, \quad disn\_u < dis1\_u$$的点$$u$$
这些点应该被抢占，作为多源最短路的起点

接下去就只能**绕安全区**了，往`key = 0`的区域扩展，执行`bfs`

> 最后计算答案，枚举从安全区中哪个点出来，绕回**最短路主干道**

假设说枚举$$u$$是安全区中的点，枚举$$u \to v$$，去往主干道上的点$$v$$
如果$$D_u + 1 > dis1_v$$，那么和`Alice`一定会错开，沿着`Alice`的来时路走回去即可	
答案就是$$D_u + 1 + dis1_v$$

否则的话，强行冲过去一定会和`Alice`相遇，我们必须在`u`点等待
等待`Alice`走过去之后，我们再走，所以总时间是$$dis1_v + 1 + dis1_v$$

## Codeforces Round 1044
### E
**[E. I Yearned For The Mines](https://codeforces.com/problemset/problem/2133/E)**
小时候，Steve 渴望进入矿井！他的矿井可以表示为一棵有`n`个节点的树
不幸的是，Steve 的最大死敌 Herobrine 潜入了他的矿井！任何时刻，Herobrine 都正好藏在一个节点里；最初，他可能在任意一个节点。Steve 可以执行以下操作：

- `1 x` —— 检查 Herobrine 当前是否在节点`x`。如果在，Steve 就抓住了他。否则，Herobrine 可以选择是否移动到任意一个相邻节点（除了你刚刚检查过的那个）。
- `2 x` —— 摧毁所有与节点`x`相连的边；Herobrine 之后将无法再通过这些边移动。随后，Herobrine 可以选择是否移动到任意一个相邻节点。

请你找出一组不超过 $$\left\lfloor \frac{5}{4} \cdot n \right\rfloor$$ 次操作的方案，使得无论 Herobrine 最初藏在哪里、如何移动，Steve 都一定能抓住他。我们已经证明，在给定约束下总是存在这样的方案。

**算法分析**
> 如果是链呢？

对于链的情况，实际上不需要`2`操作了，直接从链的一端“围堵”即可

> 其他情况可以看成若干条链，**连成簇**，簇点是我们需要考虑的，即`deg >= 2`的点

用`dp(u)`表示自底向上传递过来多少条“单链”

如果$$dp(u) = 2$$，但是`u 没有父亲`，那么它在链上
如果`fa[u] != 0`，说明**这条链挂在某个父亲上**，要把这条链切下来，切父亲`fa`
（因为是一棵树，**自底向上切链**，每条链最多只可能被挂在一个父亲上，否则就成环了）

如果$$dp(u) \geqslant 3$$，那么`u 这个点由多条链`**簇拥而成**，此时直接切`u`

> 切完了之后，整个图就剩下切掉的孤立点和若干条直链

重新建图，`dfs 新图的每条直链`，注意从`deg = 1`的端点开始围堵，这样就做完了

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

看完文章有啥想法