2026年四月算法竞赛选题（一）

[[ slider_text ]]

[[ item.c ]]

2026年四月算法竞赛选题（一）

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

线段树 hall定理

## Codeforces Global Round 31
### D
**[D. Insolvable Disks](https://codeforces.com/contest/2180/problem/D)**
在平面上给定`n`个整点$$x_1 < x_2 <\cdots < x_n$$，对于每个$$i$$，任意选择半径$$r_i > 0$$
并且$$x_i$$为圆心$$r_i$$半径画一个圆盘，要使得所有圆盘相外切的对数尽量大，求这个最大值

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

## Codeforces Round 1095 (Div. 2)
**[E. Mental Monumental (Hard Version)](https://codeforces.com/contest/2226/problem/E)**
给定一个序列$$[c_1, c_2, \cdots, c_m]$$，最大化`mex(c)`，可以进行以下操作恰好一次
选择一个序列$$[b_1, b_2, \cdots, b_m]$$，每个数任意，令$$c_i = c_i \bmod b_i$$
最大化`mex(c)`

**算法分析**
核心观察，假设说我们需要构造`tar`，而当前序列的元素是$$x$$
那么$$x \equiv tar (\bmod b_i), \quad tar < b_i$$
也就是说，$$(x - tar) \equiv 0(\bmod b_i)$$，换句话说$$(x - tar)$$是$$b_i$$的倍数

从而$$x - tar \geqslant b_i, tar < b_i$$，从而$$\exists x, x > 2tar$$，那么`tar`就可以被构造出来

现在要对每一个前缀求`mex`，容易发现`mex`是**单调不降**的
有一个**贪心**，对于一个值$$x$$，优先满足构造它自己（这很简单，令$$b_i = \infty$$或者任意一个`> x`的数即可）
如果有多余，构造$$\leqslant \lfloor \dfrac{x-1}{2} \rfloor$$

那么问题来了，$$x$$可以用来构造它自己，也可以用来构造$$\leqslant \dfrac{x-1}{2}$$的某个数
可以用来构造$$\\{y_1, y_2, \cdots\\}$$，这类问题，引入**供应和需求**，用**Hall定理**

> 贪心 + 供应/需求，维护`mex`

![](/media/content_img/cf1095E.png)

### Hall 定理视角
![](/media/content_img/CF1095E-hall.png)

## 2025-2026 ICPC, NERC
### F
**[D. Doorway](https://codeforces.com/contest/2181/problem/D)**
有`n`层，每一层有左右两个墙壁，坐标分别是$$x\_{i, 1}, x\_{i, 2}$$
现在每一层有$$k\_i$$个门，长度依次是$$l\_{i1}, l\_{i2}, \cdots, l\_{ik\_i}$$
门不能重叠，求最大的可能的窗口的大小

**算法分析**
不难发现，最优的决策，对于每一层，一定是某个前缀$$[1\cdots j]$$全部推到左边
然后剩下的后缀推到右边

注意到门的总长度是固定的，假设说第`i`个前缀$$l_i$$被推到了左边，那么窗口长度
```math
win = x_2 - (len - l_i) - (x_1 + l_i) = x_2 - x_1 - len
```
不难发现，每一层窗口的长度是确定的，是一个滑动窗口
每一层的起点定了，终点也就确定了
答案是对每一层$$i$$，最大化全局的$$minR_i - maxL_i$$

很自然的想法是
```bash
for 每一层的前缀作为 maxl
	for 其他的层，找到最大的前缀 pre(j) 使得 pre(j) <= maxl
		这些层的 pre(j) 确定，R 也就确定了
		对所有这样的 R 取一个 min 就是 minr
```
这样会超时，但是这种问题可以看作类似**二维偏序**，对所有层的$$(l, r)$$按$$l$$排序

边界状态，一开始让所有楼层`k`对应的`r`插入线段树中，此时都是`0`
（只要这个楼层未被考虑到，`0 - maxl < 0`是不会对答案有贡献的）
（也可以设置成`-1`作为哨兵，如果`query < 0`，说明还有楼层没有插入进来）

然后从小到大枚举$$maxl = l$$，这样线段树中存在的`r`，所对应的$$l'$$一定$$\leqslant l$$
你每枚举一个$$l$$，就单点修改对应的第$$k$$层，$$r = l + win$$

这样你每一层的`l`都会更新的尽量靠右，并且不会超过当前枚举的`maxl`
用全局查询最小值`minr`来更新答案

### G
**[G. Greta's Game](https://codeforces.com/contest/2181/problem/G)**
一个环，现在一轮游戏下来，每个人可以任意写上一个数，假设第$$i$$个人写上$$x\_i$$
如果满足$$x\_i > x\_{(i+1) \bmod n}$$ ，那么这两个人的得分都会同时`+1`
一开始所有人的分数都是 0，现在给出每个人最终得分序列`a[1...n]`，求游戏最小轮数

**算法分析**
首先肯定是可以二分的
最好情况，$$>$$的对数尽量多
```bash
x[1] > x[2]
         x[2] > x[3]
		          x[3] > x[4]
....但是这个过程不能无限进行下去，必须中间至少断开一个，否则前后矛盾
                                x[k-1] > x[k]
								
断开
											  x[k+1] > x[k+2]
											  		       x[k+2] > x[k+3]
														                ......
																		            x[n] > x[1]
```
所以`R`轮下来，能够获得的最高得分是$$(2n - 2)\cdot R$$
最低分呢？那么很显然$$x_1 = x_2 = \cdots = x_n$$，得分是`0`

> 每个点的约束

对$$x\_{i-1} > x\_{i}$$执行若干次，到$$a\_{i-1}$$满足要求之后，这个约束就不能有了
接下来如果要继续增大$$a\_{i}$$，只能令$$x\_{i} > x\_{i+1}$$

对于$$x\_{i-1} >x\_i$$的关系，看作$$(i-1) \to i$$连边，也就是说，对于$$i$$入边度数`+1`
而$$x\_{i} > x\_{i+1}$$，看作$$i$$的出边，出边度数`+1`
另外我们只需关注$$>$$的关系

这样对于每个点$$i$$，$$in_i + out_i = a_i$$，是不是很像**流量守恒**

其中$$out\_i = in\_{i+1}$$，那么我们有$$in\_i + in\_{i+1} = a\_{i}$$
二分轮数`R`，初始时候$$0 \leqslant in \leqslant R$$

我们迭代$$2n$$次，因为是循环流，这样下来一定会收敛
上一个点`in`假设说$$l \leqslant in \leqslant r$$
我们有`in + nxt_in = a[i], ==>  nxt_in = a[i] - in`，从而`a[i] - r <= nxt_in <= a[i] - l`

维护$$nl = a_i - r, nr = a_i - l$$，迭代$$[l, r] \to [nl, nr]$$，看一下上下界是否满足要求即可

## 贝叶斯公式
假定$$F\_1, F\_2, \cdots, F\_n$$是互斥事件，使得$$\bigcup\_{i = 1}^{n} F\_i = S$$
令$$E = \bigcup\_{i = 1}^{n} EF\_i$$，并且如果$$F\_1, F\_2, \cdots, F\_n$$**恰有一个发生**
```math
\displaystyle
P(E) = \sum_{i = 1}^{n} P(EF_i) = \sum_{i = 1}^{n} P(E \mid F_i) P(F_i)
```

**对于给定的，且有且只发生一个的事件**$$F_1, F_2, \cdots, F_n$$，导致了结果$$E$$

我们能首先通过对$$F_i$$中的**一个事件，取条件**，计算$$P(E \mid F_i)$$
最后求出来的$$P(E)$$等于$$P(E \mid F_i)$$的**加权平均**，权值对应事件的概率$$P(F_i)$$

现在假定$$E$$已经发生了，而我们关心的是确定哪一个$$F_i$$也发生了
```math
\displaystyle
P(F_j \mid E) = \dfrac{P(EF_j)}{P(E)} = \dfrac{P(E \mid F_j) P(F_j)}{\sum_{i = 1}^{n} P(E \mid F_i) P(F_i)}
```

**例 1**
假设一封信等可能地在`3`个不同文件夹的任意一个之中，若信在文件夹$$i$$中
而你对文件夹快速翻阅，发现信的概率是$$p_i$$，现在你查看文件夹`1`并且没有发现此信
问信在文件夹`1`中的概率是多少

令$$F_i$$表示事件，信在文件夹$$i$$中，$$E$$表示事件，通过文件夹`1`搜索未看到信
其中$$P(F_1) = P(F_2) = P(F_3) = \dfrac{1}{3}$$

对于$$i = 1$$，$$P(E \mid F_i) = (1 - p_i)$$
而对于$$i = 2, 3$$，$$P(E \mid F_i) = 1$$（信在文件夹`2`中，你搜文件夹`1`当然找不到信）
带入贝叶斯公式，我们要求的实际上是$$P(F_1 \mid E)$$
```math
\displaystyle
P(F_1 \mid E) = \dfrac{P(E \mid F_1)P(F_1)}{\sum_{i = 1}^{3} P(E \mid F_i) P(F_i)} = \dfrac{(1-p_1) \dfrac{1}{3} }{(1-p_1)\dfrac{1}{3} + \dfrac{1}{3} + \dfrac{1}{3}} \\
\quad 
= \dfrac{1 - p_1}{3 - p_1}
```

### 2025-2026 ICPC, NERC
#### J
**[J. Jinx or Jackpot](https://codeforces.com/contest/2181/problem/J)**
给定`p[1....n]`，现在老板等概率随机选择一个下标`i`，开了一个中彩票概率是$$\dfrac{p_i}{100}$$的赌场
（一旦选出了这个`p[i]`，之后赌场的概率就不会变了）

现在你进赌场，可以下注$$x$$元，$$x$$由你自己订，只要不超过手里的金钱就可以
现在你可以赌$$K$$次，$$K$$给定，接下来有两种事件
第一，你中奖了，概率是$$p_i / 100$$，返还$$2x$$元，净赚$$x$$元
第二，未中奖，概率是$$1 - p_i / 100$$，不会返还钱，亏损$$x$$元

求最大期望收益，最开始有钱`1000`元

**算法分析**
一个期望 dp，假设说我们游戏进行了$$k$$轮，从$$k \to k+1$$，并且在第$$k$$轮投了$$x$$元

有两种决策，一种是`win`，一种是`lose`
如果是`win`，那么这一轮我确定能过获取$$x$$，从`[k+1...`轮往后呢？能获取多少？
实际上是$$dp(k+1)$$，$$dp(k) = p_i \cdot (dp(k+1) + x)$$

如果是`lose`，那么这一轮我就是亏了，$$dp(k) = (1-p_i) \cdot (dp(k+1) - x)$$
```math
dp(k) = p_i (dp(k+1) + x) + (1-p_i)(dp(k+1) - x) \\
\Rightarrow dp(k) = dp(k+1) + x(2p_i - 1)
```
若$$p_i \leqslant 1/2$$，那么$$x = 0$$
否则$$p_i > 1/2$$，$$x$$尽可能大，直接 all in

> 问题是，选哪个$$p_i$$并不知道，不是确定的，只能舍弃遍历$$i$$，转而**整体考虑**

> 注意到题目中给出的，试验次数$$k \leqslant 30$$，可能要把$$k$$设计到状态中
另外，根据上面的分析，每一轮要么不下注，要么 all-in，所以最终的期望收益**一定是初始金钱的倍数**

另外，这个问题中，一开始老板具体选的是哪一个$$p_i$$我们不知道，在这种情况下
可以考虑**贝叶斯公式**

#### 引入贝叶斯公式
可以考虑结果，假设说下注了$$t$$次，赢了$$w$$次，并且下次还能继续赢，记为事件$$E$$
我们关心的是事件$$E$$**是由什么导致的**，肯定是由选了第$$i$$台机器导致的
这个概率记为$$P_i(t, w) = P(F_i \mid E)$$

其中$$P(F_i) = \dfrac{1}{n}$$是确定的

而$$P(E \mid F_i)$$是选择了机器$$i$$，导致产生$$(t, w)$$`（下注 t 次，赢了 w 次）`结果的概率

也比较容易求出来，符合二项分布
```math
\displaystyle
P(E \mid F_i) = \binom{t}{w} (1 - p_i)^{t - w} p_i^{w}
```
从而$$\displaystyle P(E \mid F_i) P(F_i) = \binom{t}{w} (1 - p_i)^{t-w} p_i^w \cdot \dfrac{1}{n}$$

综上所述
```math
\displaystyle
P_i(t, w) = \dfrac{\binom{t}{w} (1-p_i)^{t-w} p_i^w \cdot \dfrac{1}{n} }{\sum_{j = 1}^{n} \binom{t}{w} (1-p_j)^{t-w} p_j^w \cdot \dfrac{1}{n}} \\
\quad \\
= \dfrac{ (1 - p_i)^{t-w} p_i^w }{\sum_{j = 1}^{n} (1 - p_j)^{t-w} p_j^w }
```
这样，实际上我们可以把概率定义成，选了机器$$i$$，并且已经赢了$$w$$次，输了$$l$$次
**并且下一次一定会赢**
```math
\displaystyle
P_i(w, l) = \dfrac{ (1 - p_i)^l \cdot p_i^w   }{ \sum_{j = 1}^{n} (1 - p_j)^l \cdot p_j^w  } \cdot p_i =  \dfrac{ (1 - p_i)^l \cdot p_i^{w+1}   }{ \sum_{j = 1}^{n} (1 - p_j)^l \cdot p_j^w  }
```

那么，总的$$P(w, l) = \sum_i P_i(w, l)$$
```math
\displaystyle
P(w, l) = \sum_{i = 1}^{n} P_i(w, l) =  \dfrac{ \sum_{i = 1}^{n} (1 - p_i)^l \cdot p_i^{w+1}   }{ \sum_{j = 1}^{n} (1 - p_j)^l \cdot p_j^w  }
```

> dp 状态转移

注意到就两种策略，分别是`all-in`和不投钱，每一轮之后，都会是初始金钱$$x$$的倍数
预处理$$P(w, l)$$之后，$$dp(w, l)$$表示当前`赢了 w 轮，输了 l 轮`之后，能够拥有最多的**倍数**

如果$$w + l \geqslant k$$，很显然$$dp(w, l) = 1$$
否则，两种决策，`all-in`或者不投
```math
\displaystyle
dp(w, l) = \max(P_{w, l} \cdot 2dp(w+1, l) + 0, \quad P_{w, l} \cdot dp(w+1, l) + (1 - P_{w, l}) \cdot dp(w, l+1))
```
最后`dp(0, 0) * 1000 - 1000`就是答案

## Codeforces Round 1097
### C
**[C. Zhily and Bracket Swapping](https://codeforces.com/contest/2224/problem/C)**
给定两个括号序列`A, B`，你可以操作任意次，一次操作任选一个$$i$$，交换$$A_i, B_i$$
问能不能通过操作，使得`A, B`都是合法括号序列

**算法分析**
`(`记为`+1`，`)`记为`-1`，如果$$\sum_i (a_i + b_i) \neq 0$$，那么直接`NO`
否则我们维护前缀最大值`dpmx[i]`，前缀最小值`dpmn[i]`
如果`dpmn[i] < 0`，说明要从`dpmx[i]`匀一些`(`到`B`中

注意到`(S + 1) -> (S - 1)`，实际上，一次操作会使得`dpmx[i] -= 2`，也会使得`dpmn[i] += 2`
如果`dpmn[i] < 0`，那么找到最小的操作次数$$k$$，使得$$dpmn_i + 2k \geqslant 0$$

把这个$$k$$求出来，如果$$dpmx_i - 2k < 0$$，那么直接输出`NO`

### D
**[D. Zhily and Barknights](https://codeforces.com/contest/2224/problem/D)**
给定序列$$a$$，$$b$$也是给定的，但你可以打乱顺序，有$$1 / n!$$种不同的排列
打乱顺序后，假设说序列变成了$$b^{\prime}$$，构造新数组$$c_i = a_i \cdot b^{\prime}\_i$$
现在问$$c$$中逆序对个数的期望

**算法分析**
如果按一般的做法，$$E = \dfrac{?}{n!}$$，分母是确定的，就是$$n!$$
分子呢？分子要枚举所有可能的逆序对个数，假设是$$k$$，$$E = \sum_k (\text{逆序对个数是 } k \text{ 的方案数}) \cdot k$$

问题是，我们没有办法枚举$$k$$并且高效求出方案数
但是我们可以求出每一对下标$$(i, j)$$对逆序对个数的贡献

暴力枚举$$(i, j), i < j$$，然后在$$B$$中**不放回地选出**$$(u, v)$$，如果
```math
\dfrac{a_i}{a_j} > \dfrac{b_v}{b_u}
```
那么$$(i, j)$$就会使得逆序对对数在原来的基础上`+1`

但是`b`还有$$n - 2$$个位置没确定啊！而这$$(n - 2)$$个位置可以随便放，方案数是$$(n - 2)!$$
满足条件的，能和$$(i, j)$$配对的$$(u, v)$$，不放回的能选多少个呢？$$\dfrac{a_i}{a_j} > \dfrac{b_v}{b_u}$$
这样的对都会使得逆序对$$+1$$，假设有`cnt`个

从而$$\\{i, j\\}$$这个位置有$$\binom{cnt}{1}$$种选法，剩下位置有$$(n - 2)!$$种选法
也就是说，能让$$(i, j)$$答案`+1`的`b`序列的方案数是$$cnt \cdot (n - 2)!$$

所以此时$$(i, j)$$对答案的贡献不是`+1`了，而是$$+cnt(n - 2)!$$

> 但实际上，遇到$$(i, j)$$对期望的贡献之类的问题，可以利用期望的**线性性质**

记$$E(X)$$表示逆序对个数的期望，因为我们确定要枚举$$(i, j)$$
可以定义指示变量$$I\_{i, j} = 1 \quad (\text{当 i, j 这两个位置构成逆序对}, i < j)$$
否则$$I\_{i, j} = 0 \quad (\text{当 i, j 不构成逆序对})$$
```math
\displaystyle
E(X) = \sum_{i, j} E(I_{i, j}) = \sum_{i, j} 1 \cdot P(i, j \text{ 构成逆序对的概率})
```
而$$P(i, j)$$是比较好预处理的，$$a_i, a_j$$是确定的
问题转化成，从`b`中**不放回抽样**，抽出两个数$$(u, v)$$满足$$\dfrac{a_i}{a_j} > \dfrac{b_v}{b_u}$$的概率

这个概率分母是$$n(n - 1)$$，总共有这么多种方案

满足$$\dfrac{a_i}{a_j} > \dfrac{b_v}{b_u}$$的数有多少个，怎么做呢？把所有的$$(b_u, b_v), u \neq v$$存下来

重载`<`运算符，二分查找，或者对`a, b`排序后，用双指针，都可以求出这个`cnt`

于是特定的$$(i, j)$$，对答案的贡献`ans += cnt / n(n - 1)`

上一篇：2026年二月算法竞赛选题（二）下一篇：2026年五月算法竞赛选题（一）

看完文章有啥想法