文章目录

Min - Max 容斥 学习笔记

发布于

概述

Min - Max 容斥，又称最值反演，是一种对于特定集合，在已知最小值或最大值中的一者情况下，求另一者的算法。
例如：
$$\max\left(a, b\right) = a + b - \min\left(a, b\right)$$
$$\max\left(a, b, c\right) = a + b + c - \min\left(a, b\right) - \min\left(a, c\right) - \min\left(b, c\right) + \min\left(a, b, c\right)$$

公式

$$\max\left(S\right) = \sum\limits_{T \subseteq S, T \neq \varnothing} \left(-1\right)^{\left\lvert T \right\rvert - 1} \min\left(T\right)$$

证明

那种一大长串的推公式证明想看的可以自己搜索。
这里给出一种简单易懂的证明：
最大值贡献为 $1$，而对于每个不是最大值的数来说，有选和不选两种方案，这两种方案一一对应且系数恰为相反数，故贡献为 $0$。
所以容斥结果就是最大值。

推广

记 $\operatorname{kmax}\left(S\right)$ 表示集合 $S$ 中的第 $k$ 大值。
$$\operatorname{kmax}\left(S\right) = \sum\limits_{T \subseteq S, \left\lvert T \right\rvert \geq k} \left(-1\right)^{\left\lvert T \right\rvert - k} \binom{\left\lvert T \right\rvert - 1}{k - 1}\min\left(T\right)$$

没有证明。

应用

Min - Max 容斥常用于解决“都出现的期望时间”问题，具体来说：

  • $\max\left(S\right)$ 表示所有元素出现时间的最大值，即所有元素都出现的时间
  • $\min\left(S\right)$ 表示所有元素出现时间的最小值，即至少有一个出现的时间。

易得
$$E\left(\max\left(S\right)\right) = \sum\limits_{T \subseteq S, T \neq \varnothing} \left(-1\right)^{\left\lvert T \right\rvert - 1} E\left(\min\left(T\right)\right)$$

例题

参考

https://www.cnblogs.com/GXZlegend/p/11563330.html
https://www.luogu.com.cn/blog/341036/solution-p4707
https://blog.csdn.net/a_forever_dream/article/details/114372891

暂无评论

发表评论