min-max容斥
2024-03-30 02:45:20
这玩意儿一般都是跟概率期望结合的吧，就是下面这个式子（\(max(S)\)代表集合\(S\)中的最大值，\(min(S)\)同理）：
\[max(S)=\sum\limits_{T\subseteq S}(-1)^{\left | T \right |-1}min(T)\]
证明的话就考虑第\(k\)大的元素对\(max(S)\)的贡献就行了，把式子列出来之后你会发现它的贡献只有在\(k=1\)时才为\(1\)，在\(k>1\)全部为\(0\)
能用它做的期望题一般都是这样的：每次操作把集合中的一个数从\(0\)变为\(1\)，求全部的数都变为\(1\)的期望次数。
我们就令\(max(S)\)表示\(S\)中的元素全部变为\(1\)的期望次数，\(min(T)\)表示\(T\)中的元素至少有一个变为\(1\)的期望次数，那么它们也满足上面的那个式子（貌似是因为期望的线性性？）
给一道例题：HDU4336 Card Collector
不就是个板子吗。。。
还有一道[HAOI2015]按位或需要和\(FWT\)一起搞
最新文章
- ORACLE建表练习
- RMAN-06059: expected archived log not found, loss of archived log compromises recoverability
- Velocity语法大全
- JQuery，UIbootstrap风格弹出层
- 获得Radio选中的后面文本框的值
- 图的深度优先遍历的实现 c/c++ DFS
- OAuth2.0认证介绍
- mybatis-generator 代码自动生成工具（maven方式）
- java 每间隔一段时间执行一段代码
- htmlUnit加持，网络小蜘蛛的超级进化
- Java集合：ArrayList的实现原理
- jQuery empty() vs remove()
- Hbase记录-client访问zookeeper大量断开以及参数调优分析（转载）
- day01-h1字体大小和文本居中
- VS没办法调试，直接退出，报错：1. 使用调试生成配置或禁用调试选项“启用‘仅我的代码’”。。。
- 使用python读写CSV文件
- 软件架构设计学习总结（3）：QQ空间技术架构之详解
- Flink源码分析
- c++中带返回值函数没写return能通过编译但运行时会出现奇怪问题
- vue项目中使用mockjs模拟接口返回数据