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

[[ slider_text ]]

[[ item.c ]]

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

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

DSU on Tree dp计数

## Atto Round 1
### E
**[E. Ancient Tree](https://codeforces.com/contest/2127/problem/E)**
给定一棵有`n`个顶点的树。每个顶点有一个整数权值$$w_i$$和一个颜色$$c_i$$
颜色是`1`到`k`之间的整数。然而，有些顶点失去了颜色，用$$c_i = 0$$表示。

我们称顶点$$v$$为 cutie，当且仅当**存在**两个顶点$$x$$和$$y$$，满足：
$$v = lca(x, y)，\quad c_x = c_y,   c_x \neq c_v$$
树的花费定义为所有 cutie 顶点的权值之和，求最小花费

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

#### 算法实现
**关注 DSU-On-Tree**
```bash
void solve(int cas) {
    int tot = 0;

function<void(int, int)> dfs_init = [&](int u, int fa) -> void {
        l[u] = ++tot, id[tot] = u;
        sz[u] = 1;
        hs[u] = -1;
        for (auto v : g[u]) {
            if (v == fa) continue;
            dfs_init(v, u);
            sz[u] += sz[v];
            if (hs[u] == -1 || sz[v] > sz[ hs[u] ]) {
                hs[u] = v;
            }
        }
        r[u] = tot;
    };
    dfs_init(1, 0);

vector<int> cnt(m+5, 0);

i64 base = 0;

function<void(int, int, int)> dfs = [&](int u, int fa, bool keep) -> void {
        // dfs light son
        for (auto v : g[u]) {
            if (v != fa && v != hs[u]) {
                dfs(v, u, false);
            }
        }
        // dfs heavy son
        if (hs[u] != -1) {
            dfs(hs[u], u, true);
        }
        // combine light son -> heavy son
        set<int> col;

for (auto v : g[u]) {
            if (v != fa && v != hs[u]) {
                // 如果有查询，统计子树信息
                for (int x = l[v]; x <= r[v]; x++) {
                    auto V = id[x];
                    if (c[V] != 0 and c[V] != c[u] and cnt[c[V]] >= 1) {
                        if (col.size() < 2) col.insert(c[V]);
                    }
                }
                for (int x = l[v]; x <= r[v]; x++) {
                    auto V = id[x];
                    cnt[c[V]] += 1;
                }
            }
        }
        // 如果有查询
        // query(u);
        auto query = [&]() -> void {
            if (col.size() >= 2) base += w[u];
            else if (col.size() == 1) {
                if (c[u] == 0) c[u] = *col.begin();
                else base += w[u];
            }
        };

query();

// add u
        cnt[ c[u] ] += 1;

// 维护完成之后，同时保存答案

if (!keep) {
            // clear info in node u
            for (int x = l[u]; x <= r[u]; x++) {
                auto V = id[x];
                cnt[c[V]] -= 1;
            }
        }
    };
    dfs(1, 0, false);

auto dfs2 = [&](auto &dfs2, int u, int fa) -> void {
        if (c[u] == 0) {
            c[u] = (fa > 0 ? c[fa] : 1);
        }

for (auto v : g[u]) {
            if (v == fa) continue;
            dfs2(dfs2, v, u);
        }
    };
    dfs2(dfs2, 1, 0);

cout << base << "\n";
    for (int x = 1; x <= n; x++) cout << c[x] << " ";
    cout << "\n";
}
```

### D
**[Root was Built by Love, Broken by Destiny](https://codeforces.com/problemset/problem/2127/D)**

给定`m`座桥，连接`n`个点
有多少种方式可以沿河排列这`n`座房屋（对 $$10^9+7$$ 取模），使得`m`座桥满足以下条件：

- 对于每一座桥，它连接的两座房屋必须分别位于河的两岸；
- 当桥作为直线连接两座房屋时，所有桥都不会相交。

如果存在以下任一情况，则两种排列被认为是不同的：

- 存在某座房屋在两种排列中位于不同的河岸
- 存在两座房屋`a, b`，它们在两种排列中都位于同一岸但在一种排列中是`a -> b`
	而在另一种排列中`b -> a`

**算法分析**
非二分图不行，另外，二分图，但是成环也不行（否则就在同岸有桥了）
所以符合条件的必须是一棵树

根据题目条件，桥不会交叉，所以符合条件的树比较特殊
**爪形图 + 链**，构成的**毛毛虫树**

统计方案，先考虑将原树上所有叶子节点都去掉，**导出子图**一定构成一条链
如果导出子图点的个数`> 2`，需要$$\times 2$$给链定向

对于导出子图，$$\times 2$$来决定它放在南岸还是北岸

接着对于导出子图上的每个节点，计算它**在原树中有多少叶子**，记为$$c_i$$，答案就是$$c_i !$$
每个节点乘起来，$$\prod_i c_i!$$

## Educational Codeforces Round 181
### E
**[E. Sets of Complementary Sums](https://codeforces.com/contest/2125/problem/E)**
我们称整数集合 $$Q$$ 为“互补和集合”，如果它可以通过以下操作获得：

- 选择一个由`m`个正整数组成的数组`a`（`m`可以是任意正整数）
- 计算数组`a`所有元素的和`S`

- 对于数组中的每个元素$$a_i$$，将 $$s - a_i$$ 加入集合 $$Q$$

注意，$$Q$$不是多重集，也就是说其中的每个数都是唯一的
例如，如果选择数组`a = [1, 3, 3, 7]`，那么`s = 14`，`Q = [7, 11, 13]`

你的任务是计算满足以下条件的不同“互补和集合”的数量
给定$$n, x$$，`Q`恰好包含$$n$$个元素，并且每个元素都是$$\in [1, x]$$

**算法分析**
> 形式化地，我们要关注值相同的数，出现了多少次

记$$S$$是$$a_i$$的和
```math
(c_1, a_1), (c_2, a_2), \cdots, (c_n, a_n) \\
(c_1, b_1), (c_2, b_2), \cdots, (c_n, b_n)
```
其中$$b_1 < b_2 < \cdots < b_n, \quad b_i = S - a_i$$

> 考虑限制

```math
\displaystyle
\begin{cases}
1 \leqslant a_i \\
1 \leqslant b_i \leqslant x \\
1 \leqslant c_i
\end{cases}, \quad b_1 < b_2 < \cdots < b_n
```
另外我们还有
```math
\displaystyle
\sum_{i = 1}^{n} c_i (S - b_i) = S, \quad a_i = S - b_i \geqslant 1 \\
(S-b_i)_{\min} \geqslant 1 \quad \Rightarrow S \geqslant b_n + 1
```

> 进一步推式子

```math
\displaystyle
S\left(\sum c_i \right) - \sum c_ib_i = S \\
\quad \\
S = \dfrac{\sum c_i b_i}{(\sum c_i) - 1} \geqslant b_n + 1 \\
\quad \\
\sum_{i = 1}^{n} c_i b_i \geqslant (b_n + 1)\left( (\sum_{i = 1}^n c_i) - 1 \right)
```
进一步地
```math
\displaystyle
\sum_{i = 1}^{n} c_i(b_n + 1 - b_i) \leqslant b_n + 1
```
只要存在一个合法的$$c_i$$，$$b_i$$就可以构造出来，所以$$\min \leqslant b_n + 1$$
考虑$$1 \leqslant c_i$$，令$$c_i = 1$$

```math
\displaystyle
\sum_{i = 1}^{n} (b_n - b_i) \leqslant b_n - n + 1 \leqslant x - n + 1
```
另外，$$b_1 < b_2 < \cdots < b_n$$，左边实际上是
```math
\displaystyle
\sum_{i = 1}^{n-1} (b_n - b_i) \leqslant x - n + 1
```
左边的$$\min = 1 + 2 + \cdots + n - 1 = \dfrac{n(n - 1)}{2}$$

令$$b_i = b_n - b_i$$，那么$$\sum b_i = V \in [\dfrac{n(n-1)}{2}, x-n+1]$$

问题转化成**序列划分**
将一个数$$V$$，划分成$$n-1$$段**严格单调递增**序列的方案数
这个做法就比较套路了，根据包不包含`1`，可以写出如下 dp 方程
（转移，让每个数都减去`1`）
```math
dp(V, k) \leftarrow dp(V - k, k) + dp(V - k, k)
```
写成滚动数组形式，就是`for k = 1 to n - 1`，然后枚举`V`
```math
ndp(V) = ndp(V - k) + dp(V - k)
```

> 坑点，方案数计算

最后的$$dp(M)$$求出的是，和**恰好是$$M$$**的单调递增序列划分的方案数
而实际上，$$\sum \leqslant M$$都是合法的方案，所以要对$$dp(M)$$求前缀和
然后再统计到答案中

实际上我们的表达式是
```math
\displaystyle
\sum b_i' = \sum (b_n - b_i) \leqslant b_n - n + 1
```
其中$$n$$的值是确定的，当我们枚举$$V = b_n - n + 1$$合法的时候
意味着所有$$\leqslant V$$也合法（我们可以通过构造，减小$$b_n$$的值来实现）

## Codeforces Round 1037 (Div. 3)
### G1
**[G1. Big Wins! (easy version)](https://codeforces.com/contest/2126/problem/G1)**
给定一个长度为$$n$$的整数数组$$a_1, a_2, \dots, a_n$$

你的任务是找到一个连续的子数组$$a[l, r]$$
使得表达式$$\text{med}(a[l, r]) - \min(a[l, r])$$的值最大。
`med`表示中位数

**算法分析**
> 注意到值域很小，可以枚举中位数

判断区间中位数是不是$$K$$，那么$$\geqslant K$$记为$$+1$$，$$< K$$记为$$-1$$
当且仅当区间前缀和$$S[l...r] = S(r) - S(l-1) > 0$$时，中位数可能是$$K$$

接下来要判一下到底$$K$$在不在区间中，对于$$K$$比较小的情况
直接预处理`exist(k, l, r)`，判断$$[l, r]$$区间中$$K$$的出现次数

如果$$K$$很大呢？再构造一个序列，$$\geqslant K+1$$记为$$+1$$，$$< K+1$$记为$$-1$$
对$$K+1$$的情况，需要判定对应的区间和$$> 0$$**失败**

> 数据结构做法

枚举中位数`med`

枚举$$a_i$$作为最小值`minv`，于此同时，可以单调栈预处理$$[l, r]$$
区间$$[l, r]$$都是以$$a_i = minv$$作为最小值的

那么我们目标是找到一个子区间，使得$$S(r) - S(l-1) > 0$$，于是用 ST 表维护前缀和

区间$$[l, r]$$，找到$$\max$$作为$$S(r')$$，同时呢，$$[l-1, r-1]$$找到$$\min$$作为$$S(l')$$
这样 如果`max - min > 0`就说明可能作为候选区间
加判一下`exist(med, l, r) = 1`，表示`med`这个数确实存在（这也可以预处理）

> **区间中位数重要处理技巧**
如果二分中位数猜测为$$x$$，将 $$\ge x$$ 的数记为 $$+1$$，$$ < x$$ 的数记为 $$-1$$

> 对于以 $$a_u$$ 为最小值的极大区间 $$[l, r]$$
如果在 $$[l, r]$$ 内部，必定跨越位置 $$u$$ 的最大子段和 $$> 0$$，那么说明存在一个以 $$a_u$$ 为最小值的子区间，它的中位数 $$\ge x$$。

## 2026“钉耙编程”中国大学生算法设计春季联赛（9）
### 1003
**[玉米式概率](https://acm.hdu.edu.cn/contest/problem?cid=1205&pid=1003)**
记$$f(x)$$是在$$[1, 2x]$$之间等概率随机选取一个整数的结果
一开始$$x = 1$$，不断进行$$x = f(x)$$的操作
给定$$n$$，问首次$$\geqslant n$$需要的期望操作次数

**算法分析**
不难写出状态转移方程
```math
\displaystyle
dp(x) = 1 + \dfrac{1}{2x} \sum_{i = 1}^{\min(n - 1, 2x)} dp(i)
```
不放就设$$2x \le n - 1$$，考虑到从后往前递推，所有的`dp`值的和是$$T$$
这样记**后缀和数组**是$$S(i)$$
```math
\displaystyle
\sum_{i = 1}^{2x} dp(i) = T - \sum_{i = 2x+1}^{n - 1} dp(i) = T - S(2x + 1)
```
从而 dp 方程可以写成
```math
\displaystyle
dp(x) = 1 + \dfrac{1}{2x} (T - S(2x + 1))
```
容易发现，$$dp(i)$$可以写成关于$$T$$的线性表达式，$$dp(i) = A_i \cdot T + B_i$$
从而有转移
```math
\displaystyle
dp(i) = 1 + \dfrac{1}{2x} \left( \cdot T - \left(\sum_j A_j \right) T - \sum_j B_j \right), \quad j = 2x + 1
```
记$$\sum_j A_j = AS_j, \quad \sum_j B_j = BS_j$$，那么我们有
```math
\displaystyle
dp(x) = 1 + \dfrac{1}{2x} (1 - AS_i)\cdot T - \dfrac{1}{2x} BS_i \\
\quad \\
= \dfrac{1 - AS_i}{2x}\cdot T + \left( 1 - \dfrac{BS_i}{2x} \right) \\
\quad \\
= A_i \cdot T + B_i
```
倒着遍历，那么
```math
\displaystyle
A_i = \dfrac{1 - AS_i}{2x}, \quad B_i = 1 - \dfrac{BS_i}{2x}
```
同时维护后缀和`AS[i] = AS[I+1] + A[i], BS[i] 同样`

做到最后
```math
S(1) = AS_1 \cdot T + BS_1 
```
同时$$S(1) =T$$，那么
```math
T = \dfrac{BS_1}{1 - AS_1}
```
自然$$dp(1) = A_1 \cdot T + B_1$$

## Codeforces Round 1100
### E
**[E. Deconstruction Tree](https://codeforces.com/contest/2229/problem/E)**
给定一棵树，给定空集$$S$$，如下操作
1）找到编号最大的叶子$$x$$
2）将$$x$$放入集合$$S$$中（`S`不是多重集合）
3）选择任意一个值$$< x$$的叶子删除
问能构造的多重集$$S$$的数量

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

## AtCoder Regular Contest 115
### E
**[E - LEQ and NEQ](https://atcoder.jp/contests/arc115/tasks/arc115_e)**
给定序列`A[1...n]`，求`X[1...n]`的方案数，满足
```math
\displaystyle
1 \leqslant X_i \leqslant A_i \\
X_i \neq X_{i +1} (1 \leqslant i \leqslant n - 1)
```
**算法分析**
动态规划方程
```math
\displaystyle
ndp(x) [1 \leqslant x \leqslant A_i] = \sum_{y \neq x} dp(y) [1 \leqslant y \leqslant A_{i -1}]
```
考虑用数据结构优化
1) 对于 $$x \in [1, A\_i]$$，有$$ndp(x) = (\sum\_{y = 1}^{A\_{i - 1}} dp(y)) - dp(x)$$

2) 对于 $$x > A\_i$$，$$dp(x) \to 0$$

这可以用动态开点线段树来维护`dp`数组，从第$$i - 1 \to i$$
1）求出当前线段树区间和`S`

2）区间线性变换，对于所有$$x \in [1, A_i]$$，$$x \to -x + S$$

3）清空区间$$[A\_{i+1}, +\infty)$$，所有值变成`0`

## leetcode 第 503 场周赛
### 3
**[3942. 排序排列的最少操作数](https://leetcode.cn/problems/minimum-operations-to-sort-a-permutation/description/)**
给定一个`[0...n-1]`的排列，只会进行以下操作
1）反转整个数组
2）向左循环移位`1`位
问将排列变成递增，需要的最小操作次数

**算法分析**
> 循环移位，不改变相邻元素的，**相对大小关系**
可以破环成链，复制一倍

实际上，允许的操作就只有循环移位
1）操作1，向左循环移 1 位
2）操作2，向右循环移 1 位（`反转 -> 左移 -> 反转`）

破换成链，复制一倍
当且仅当存在上升子段`[0...n-1]`或者下降子段`[n-1...0]`时候，才有解
1）如果是上升子段，找到其位置$$k$$
左移$$k$$，或者右移$$n - k$$，代价分别是$$k, n - k + 2$$

2）如果是下降子段呢？
类似地，找到位置$$k$$
左移$$k$$，然后反转，代价$$k+1$$
或者右移$$n - k$$，此时只需要反转一次即可，代价$$n - k + 1$$

针对以上情况，取最小值即可

## 2026“钉耙编程”中国大学生算法设计春季联赛（10）
### 1009
**[大户爱的蚂蚁题](https://acm.hdu.edu.cn/contest/problem?cid=1206&pid=1009)**
长度为`1 单位`的环上有$$n$$只蚂蚁，每只蚂蚁的初始位置不会重叠
现在每只蚂蚁进行速度相同的匀速圆周运动，`1 单位`时间走完`1 圈`
每只蚂蚁初始时候，会等概率随机选择一个方向匀速走`1`个单位，然后停下
任意两只蚂蚁相遇时候，都会立刻转向，问每只蚂蚁**都能**在`1`单位时间内回到自己起点的概率

**算法分析**
> 不考虑碰撞，而是看成**“擦肩而过，编号互换”**

这样，最终有蚂蚁的位置集合，和初始时候的位置集合是一样的
只是每个位置上，住着的蚂蚁编号有可能乱

> 但实际上，编号也不会乱，因为实际上，蚂蚁是不会擦肩而过的
所以，蚂蚁编号的**相对顺序不变**，又因为`初始位置集合 = 最终位置集合`
从而每只蚂蚁的**相对位置**也不会变

记第$$i$$只蚂蚁初始位置是$$i$$，终点位置是$$end_i$$，所有蚂蚁$$end_i - i$$都是定值

枚举$$m = end_i - i$$，也就是说，所有**位移的总和**必须等于$$m$$
（因为相对位置不变，蚂蚁肯定是**整体平移**的）

假设说有$$k$$只蚂蚁顺时针，单位步长是`+1`，$$n - k$$只逆时针，单位步长是`-1`
那么$$k - (n - k) = 2k - n = m$$

现在要求所有蚂蚁最终都必须回到初始位置，那么 $$m \equiv 0 (\bmod n)$$
即$$2k \equiv 0 (\bmod n)$$，$$2k$$是$$n$$的倍数

1）如果$$n$$是奇数，$$k = \\{0, n\\}$$，所有都顺时针/逆时针，方案数是$$2$$
概率是$$\dfrac{2}{2^n}$$

2）否则的话，$$k$$还可以是$$n / 2$$，也就是说，任选$$n / 2$$个走顺时针
方案数是$$\displaystyle \binom{n}{n/2}$$

概率是$$\dfrac{2 + \binom{n}{n/2}}{2^n}$$

## Educational Codeforces Round 191
### C
**[C. Cost of a Bracket Sequence](https://codeforces.com/contest/2233/problem/C)**
定义括号序列的价值是，最长合法括号子序列的长度（子序列不要求连续，但必须是合法括号序列）
你可以删`K`次，删什么位置任意，要求使得括号序列的价值最小

**算法分析**
> 尽可能破坏成对的括号

用栈维护所有成对的括号下标$$(j, i)$$`= (....)`，我们尝试破坏
如果`(.( ..( ) ....`，`j`左边仍然有`未配对的 (`，删去`(`不一定是最划算的，因为备胎`(`会顶替

这里贪心地看，两个`set`，一个`set`维护`(l, r)`，另一个维护`(r, l)`
我们考虑`l`最小的对`(l1, r1)`和`r`最大的对`(r2, l2)`

如果此时`[1..l1-1]`全部都没有`(`，那么`l1 对应的 (`删掉，并且破坏了这个括号对
否则的话，如果`[r2+1...n]`全部都没有`)`，那么删掉`r2 对应的 )`删掉，并且破坏了这个括号对
其他情况呢？我们贪心地，找到`[1...l1-1] findLast ( 的位置 p1`，以及`[r2+1...n] findLast ) 的位置 p2`
`|p1- l1|, |p2 - r2|`哪个离得近就删谁，这样贪心地删，比如删掉`p1 -> 0`（单点修改）

以上都可以用线段树，单点修改，线段树二分来维护，用两棵线段树，分别维护未匹配的`(`和`)`

> 进一步优化

因为我们把所有配对的`()`全部都抽出来了，也就是说，形如`((..()`，如果$$(j, i)$$
`j`左边有多出来的，未匹配的`(`，那么意味着$$i$$右边一定什么都没有（没有多出来的`)`）
否则多出来的位置`(..)`应该继续在匹配栈中，而不会是未配对的状态

> **结论**

找到匹配括号对$$(j, i)$$之后，如果`[1...j-1]`有多余的未匹配`(`，那么`[i+1...n]`一定没有多余的`)`
反过来，`[i+1...n]`有多余的`)`，意味着`[1...j-1]`一定没有多余的未匹配的`(`

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

看完文章有啥想法