时间戳

首页 > 技术文章 > 【学习笔记】Min-max 容斥

【学习笔记】Min-max 容斥

Midoria7 2020-09-18 10:03 原文

经常和概率期望题相结合。

对于全序集合 \(S\)，有：

\[\max S=\sum\limits_{T\subseteq S,T\not=\varnothing}(-1)^{\vert T\vert -1}\min T \]

\[\min S=\sum\limits_{T\subseteq S,T\not=\varnothing}(-1)^{\vert T\vert -1}\max T \]

证明

对于 \(x\in S\)，假设 \(x\) 是 \(S\) 中第 \(k\) 大的元素，则建立映射\(f:x\rightarrow \{1,2,\dots,k\}\)。

可以得到对于 \(x,y\in S\)，有：

\[f(\min (x,y))=f(x)\cap f(y) \]

\[f(\max (x,y))=f(x)\cup f(y) \]

因此得到：

\[\begin{aligned} \vert f(\max S)\vert&=\bigg\vert \bigcup\limits_{x\in S}f(x)\bigg\vert \\ &=\sum\limits_{T\subseteq S}(-1)^{\vert T\vert -1}\bigg\vert \bigcap\limits_{x\in T}f(x)\bigg\vert\\ &=\sum\limits_{T\subseteq S}(-1)^{\vert T\vert -1}\ \vert f(\min T)\vert\\ \end{aligned}\]

将 \(\vert f(\max S)\vert\) 映射回原式，从而得证。

通俗的说，就是对于除本身集合的其他的集合取最小值时，集合大小为奇数时加上，大小为偶数时减掉，而选奇数个和选偶数个的方案数又是一样的，于是抵消掉了，最后只剩下 \(f(\max\limits_{x\in S} x)\)的贡献。

拓展

\[\max_k S=\sum\limits_{T\subseteq S,\vert T\vert\geq k}(-1)^{\vert T\vert -k}{\vert T\vert-1\choose k-1}\min T \]

背他就完了

应用

常见的应用：有 \(n\) 个变量，每个变量出现的概率为 \(p\)。问每一个变量都出现的期望时间。

根据期望的线性性质，可以得到

\[E(\max S)=\sum\limits_{T\subseteq S,T\not=\varnothing}(-1)^{\vert T\vert -1}E(\min T) \]

其中 \(E(\min T)\) 显然就是 \(\cfrac{1}{\sum\limits_{i\in T}p_i}\)。

例题：礼物

夏川的生日就要到了。作为夏川形式上的男朋友，季堂打算给夏川买一些生日礼物。

商店里一共有种礼物。夏川每得到一种礼物，就会获得相应喜悦值 $ W_i$（每种礼物的喜悦值不能重复获得）。

每次，店员会按照一定的概率 \(P_i\)（或者不拿出礼物），将第i种礼物拿出来。 季堂每次都会将店员拿出来的礼物买下来。没有拿出来视为什么都没有买到，也 算一次购买。

众所周知，白毛切开都是黑的。所以季堂希望最后夏川的喜悦值尽可能地高。

求夏川最后最大的喜悦值是多少，并求出使夏川得到这个喜悦值，季堂的期望购买次数。

显然的 Min-max 容斥模板题。最大的喜悦值就是给出的喜悦值的和，而剩下就是套式子了。用 dfs 枚举子集 \(T\)，时间效率 \(O(2^n)\) ，空间效率 \(O(n)\)。

#include <bits/stdc++.h>
using namespace std;
const int maxn=30;
int n;
long long ans;
double res;
double p[maxn];

void dfs(int now,double sum,int opt){
    if(now==n+1){
        if(sum>1e-9)res+=1.0*opt/sum;
        return;
    }
    dfs(now+1,sum+p[now],-opt);
    dfs(now+1,sum,opt);
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        long long u;
        scanf("%lf%lld",&p[i],&u);
        ans+=u;
    }
    printf("%lld\n",ans);
    dfs(1,0,-1);
    printf("%.3lf\n",res);
    return 0;
}

推荐阅读