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

[[ slider_text ]]

[[ item.c ]]

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

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

数位dp

## 2024 百度之星
### BD202408 毛毛虫
**[毛毛虫](https://www.matiji.net/exam/brushquestion/8/4498/F16DA07A4D99E21DFFEF46BD18FF68AD)**
给定一个`n`个点的树，每个点的度数不超过`5`，给定多重集`a[1, 2, ..., k]`
要求找到$$k$$个点，使得存在边$$(d\_1, d\_2), (d\_2, d\_3), \cdots, (d\_{k-1}, d\_k)$$
并且满足删除这`k - 1`条边之后，得到的连通块，每部分的点数（连通块的大小）`b[1, 2, ..., k]`
和给定的多重集相同

**算法实现**
![](/media/content_img/bd202408-01.png)
![](/media/content_img/bd202408-02.png)
![](/media/content_img/bd202408-03.png)

## Codeforces Round 829 (Div. 2)
### D
**[D. Factorial Divisibility](https://codeforces.com/contest/1754/problem/D)**
给定`x`和`a[1...n]`，判断$$x ! \mid (a_1 ! + a_2 ! + \cdots + a_n !)$$ 是否成立

**算法分析**
令$$m = \min(a[1\cdots n])$$，那么
```math
\displaystyle
m! \left( cnt(m) + \sum(m + 1\text{作为最小值的子问题，合法与否}) \right) \\
= m! (cnt(m) + (m+1)! (m+2\text{ 的子问题})
```
实际上就是如果$$cnt(m) = q (m+1)$$，那么就可以`dfs`到`m+1`，以此类推

### E
**[C. Wish I Knew How to Sort](https://codeforces.com/problemset/problem/1753/C)**
给定`01`串，每次操作中
你等概率随机选择$$(i, j), i < j$$，如果`a[i] > a[j]`就交换（否则无事发生）
问操作次数的期望

**算法分析**
直接做的话
```math
\displaystyle
w = \binom{n}{2}, \quad 
\sum_k k \cdot \dfrac{1}{w^k} \cdot (\text{操作 k 次的方案数})
```
没法做
如果`n`比较小，考虑`dp`，二进制状态$$S$$，那么记`P`是**转移成功的概率**
```math
dp(S) = (1-P)\cdot dp(S) + P \cdot dp(nS) + 1 \\
\quad \\
dp(S) = dp(nS) + \dfrac{1}{P}
```
注意到每个数不是`0`就是`1`，必然是前`c = cnt[0]`个都必须放`0`，后`n - c`个位置必须放`1`
那我们考虑前$$c$$个位置，有$$m$$个位置**鸠占鹊巢**，那么能够转移成功的方案数就是$$m^2$$
从而$$P = \dfrac{m^2}{\binom{n}{2}}$$

再看期望表达式，$$dp(S) = dp(nS) + 1/P$$
换句话说，每归位一对$$(i, j)$$，期望步数就 $$+ 1/P$$，期望终点是`0`

`总期望 = dp(初始有多少个错位的对) = dp(错位的对数 - 1) + 1/P`

### F
**[F. The Beach](https://codeforces.com/contest/1754/problem/F)**
给定`n * m`的网格，空格标记为`.`，不可移动的障碍标记为`#`
另外有一些可移动的障碍，$$1 \times 2$$的，横着标记为`L, R`，竖着标记为`U, D`
对于可移动的障碍，旋转$$90^{\circ}$$花费`p`的代价，平移话费`q`的代价，问把网格弄出`1 * 2`的空位
最少要花费多少代价？

**算法设计**
![](/media/content_img/cf829-F1.png)

**坑点**
空格是会移动的，所以按道理说每个点，$$(x, y) \to (nx, ny)$$都要连边
但**多源 dijkstra，**只把初始时候的$$(x, y), dis(x, y) = 0$$放到初始的堆中

## Codeforces Round 860 (Div. 2)
### D
**[D. Shocking Arrangement](https://codeforces.com/contest/1798/problem/D)**
给定`a`，满足$$a_1 + a_2 + \cdots + a_n = 0$$，构造`a`的排列
```math
\displaystyle
\max_{1 \leqslant l \leqslant r \leqslant n} |a_l + a_{l+1} + \cdots + a_r| < \max(a[1\cdots n]) - \min(a[1\cdots n])
```
**算法分析**
从前缀和的角度来分析，记最大的正数是$$M$$，最小的负数是$$m$$
要求$$S(r) - S(l -1) < M - m$$

构造，可以考虑让每个$$S$$都在$$[m, M)$$**之间扰动，最好是在`0`上下扰动**

采用的策略是，正数和负数分开放，按绝对值从大到小排序
如果$$S \geqslant 0$$，那么放堆顶的负数
如果$$S < 0$$，那么放堆顶的正数

构造完了之后判断

### E
**[E. Multitest Generator](https://codeforces.com/problemset/problem/1798/E)**
定义一个序列是`test`的，当且仅当`a[1] = 序列的长度 - 1`，至于后面具体放哪些数随意
定义一个序列`b`是`multitest`的，当且仅当`b[2...m]`可以被划分成`b[1]`个非空连续子数组
并且每一个子数组都是`test`，记`f`表示将数组变成`multitest`的**最少操作次数**

**算法分析**
很容易想到`dp`，由于$$a_i$$和$$[i+1\cdots n]$$能划分成几段是有关系的
所以`dp`状态定义成$$dp(i, K)$$，但很可惜是$$O(n^2)$$的

进一步分析，**操作次数有上限**，一定**不超过`2`**，改`a[i], a[i+1]`一定可以合法
另外，如果**发生修改**，假设说修改出`m`段，那么你一定能构造出$$< m$$**的所有更小的段**
为什么呢？你要合并段的时候，只要让发生修改的位置的`a[j]`，改成满足“你要构造的段数”即可

只要发生修改了，那么你往前`dp`的时候，**可以把权限交给当前最靠前的段，对应的`a[1]`**
这样就可以构造出`[1...最大段数]`所需要的所有的段

所以只需要知道**最多能构造多少段**即可
用$$dp0(i), dp1(i)$$表示后缀`[i...n]`最多能构造多少段`multitest`
非法状态，记$$dp = -\infty$$

转移并不难
```math
\textbf{let } j = a_i + i + 1 \\
dp_0(i) = dp_0(j) + 1 \\
dp_1(i) = \max (dp_1(j) + 1), \quad dp_1(i) = \max_{j \in [i+1\sim n]} dp0(j) + 1
```
起始状态，设置哨兵节点`dp0(n + 1) = dp1(n + 1) = 0`

计算答案，只有`0, 1, 2`这三种可能
**答案是 0**，一定不能改，`if dp0[i+1] = a[i]`，输出`0`（没有修改过，只能严格相等）
**答案是 1**，修改`a[i]`，或者修改之后的值
如果修改的是`a[i]`，那么只要$$dp0(i + 1) \geqslant 0$$即可（只要合法）
否则，你`a[i]`不能改，那么你这一次的修改权限要交给$$[i+1 \sim n]$$的某一个数
也就是说，$$dp1(i + 1) \geqslant a_i$$即可
**其余情况，答案是`2`**

### F
**[F. Gifts from Grandfather Ahmed](https://codeforces.com/contest/1798/problem/F)**
有`n + 1`个学生，分为$$k$$个班级，第$$i$$个班级有$$s_i$$名学生
满足$$s_1 + s_2 + \cdots + s_k = n + 1$$

现在已经有$$n$$个盒子了，第`i`个盒子中有$$a_i$$个礼物
你需要再买一个礼物，分配给`K`个班级，满足

1）第$$i$$个班级恰好收到$$s_i$$个盒子

2）假设说这$$s\_i$$个盒子中，每个盒子的礼物数量依次是$$c\_1 , c\_2  \cdots c\_{s\_i}$$
必须满足$$s\_i \mid (c\_1 + c\_2 + \cdots + c\_{s\_i})$$

给出一个分配方案，或者报告不可能
**算法分析**
![](/media/content_img/cf860-f1.png)
![](/media/content_img/cf860-f2.png)

## Educational Codeforces Round 192
### E
**[E. Product of Closures](https://codeforces.com/contest/2242/problem/E)**
定义$$C(x)$$，构造规则如下
将`x`写成没有前导零的二进制形式，将得到的二进制字符串和自身无限次拼接
定义$$C(x) \cdot C(y)$$，是无限长的二进制串，按位`AND`的结果
现在给定`l, r, n`，需要在$$[l, r]$$中找到两个数$$x, y$$，使得`C(x) AND C(y)`字典序尽可能小
求出这个最小`AND`结果的前`n`个字符

**算法分析**
先看简单的情况，最好就是形如`x = 100...0, y = 100...0`这样
问题是，这样的值能不能取得到呢？不一定，因为有$$l \leqslant x \leqslant y \leqslant r$$的限制

> 如果`topbit(l) != topbit(r)`，也就是说，`lenr > lenl`

首先对于$$y \leqslant r$$，那么`y = 100....0  （长度和 lenr 一样）`是一定可以取得到的
也就是说，$$y$$的取值是确定的，只能是`ly = 1000....0（和 lenr 同长度）`

假设说对于`100...0, 100...0`，长度分别记为$$lx, ly$$，那么在无限循环串中
什么时候这样的`1`会**再次对齐呢？**

不难发现是$$D = \text{lcm}(lx, ly)$$，`0, D, 2D, ...`这几个位置只能是`1`
那么我们就要让`lcm`**尽可能大**，很显然$$|lx - ly| = 1$$才能满足

也就是说，此时最好的情况是`x = 100...0（长度等于 ly - 1）`
问题是能不能取到呢？在$$lenr - lenl \geqslant 2$$的情况下一定是可以的

> 如果`lenr > lenl`，并且`lenr - lenl = 1`

那么这个时候`x = 100....0`可能会跌破下界，满足不了$$x \geqslant l$$
但是构造的$$x$$的长度`= lenl`这是确定的

什么时候`C(x) AND C(y)`的结果可能变成`1`呢？
**贪心地，**只需要考虑$$0, ly, 2ly, \cdots, Kly$$这些位置，其中$$K = \text{lcm}(lx, ly)$$
其他位置放`0`放`1`无所谓

从前往后考虑这些位置，优先考虑放`0`，其他位置都放上`1`，如果不跌破下界，那么就可以
否则呢？否则就只能放`1`

检查完这些位置之后，其他位置可以都放上`1`，让$$\geqslant l$$尽可能满足

> 如果`lenl == lenr`呢，很典型的数位 dp

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

看完文章有啥想法