算法小站
首页
wiki
新鲜事
文章搜索
网站导航
回忆录
首页
wiki
新鲜事
文章搜索
网站导航
回忆录
登录
注册
算法基础
搜索
数据结构
字符串
数学
图论
动态规划
计算几何
杂项
2026年四月算法竞赛选题(一)
贝叶斯公式,期望dp,期望,线性,条件概率,二分图
[[ slider_text ]]
[[ item.c ]]
0
0
2026年四月算法竞赛选题(一)
发布时间
2026-05-07
作者:
秋千月
来源:
算法小站
## 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$$半径画一个圆盘,要使得所有圆盘相外切的对数尽量大,求这个最大值 **算法分析**  ## 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`  ## 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)`
0
0
上一篇:2026年二月算法竞赛选题(二)
已经是最后一篇啦
看完文章有啥想法
发布评论
8 人参与,0 条评论