HDU4336 Card Collector 题解

Zi_Gao

2024 年 03 月 10 日

284 次浏览

暂无评论

1319字数

默认分类

## 题意

玩一个抽卡游戏有 $n$ 张卡牌，每次抽到第 $i$ 中卡牌张的概率是 $p_i$，问集齐每种卡牌的期望抽卡次数。

$n\leq 20$

## 题解

### min-max 容斥

先丢两个公式，第一个公式是第二个公式的特殊情况，一般用不到第二个。

1. 最大值形式：

$$
\max\left(S\right)=\sum_{T\subset S} \left(-1\right)^{\left|T\right|+1}\min\left(T\right)
$$

2. 第 $k$ 大值形式：

$$
k\text{th}\max\left(S\right)=\sum_{T\subset S} \left(-1\right)^{\left|T\right|+k}{\left|T\right|-1\choose k-1}\min\left(T\right)
$$

证明非常简单，考虑每个值 $x$ 作为最小值时的贡献，若所有比 $x$ 大的元素构成集合是 $T$，那么贡献是：

$$
\sum_{V\subset T} \left(-1\right)^{\left|V\right|}
$$

注意这里的指数，由于最终贡献的集合还要在 $V$ 上加入 $x$ 所以是 $\left(-1\right)^{\left|V\right|}$，显然在 $\left|T\right|=0$ 时，式子等于 $1$ 其他情况式子是 $0$，也就是只有最大值贡献是 $1$。

另一个式子证明同理。

### 做题

容易发现某一种抽卡情况中，抽的次数取决于最后被抽到的那张卡，即最大值，记随机变量 $t_i$ 表示抽到第 $i$ 张卡的时间。

$$
Ans=E\left(\max\left\{t_i\right\}\right)
$$

由于期望的线性性有：

$$
E\left(U\right)=\sum_{S\subset U} \left(-1\right)^{\left|S\right|+1}\min\left(S\right)
$$

那么考虑对于每个 $S$ 求出 $\min\left(S\right)$，肯定是第一次抽到 $S$ 中元素的时间，也就是说前面的时间都只能抽 $S$ 以外的东西，设抽到 $T$ 集合中的元素概率为 $P_T$，那么有：

$$
\min\left(S\right)=\frac{1}{1-P_{U-S}}
$$

做完了，双倍经验是洛谷P3175。

## 代码

```cpp
#include<bits/stdc++.h>
// #define ONLINE_JUDGE
#define INPUT_DATA_TYPE int
#define OUTPUT_DATA_TYPE int
INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10^48);return;}

long double sumP[1<<20],E[1<<20];

int main(){
	#ifndef ONLINE_JUDGE
	freopen("name.in", "r", stdin);
	freopen("name.out", "w", stdout);
	#endif

int n;
    while(scanf("%d",&n)==1){
        register int i,j,U,maxs;
        register long double res=0,cnt=0;
  
        U=(maxs=1<<n)-1;
        for(i=0;i<n;++i) scanf("%Lf",&sumP[1<<i]),cnt+=sumP[1<<i];

sumP[0]=1-cnt;

for(i=0;i<n;++i)
            for(j=0;j<maxs;++j)
                if((j>>i)&1)
                    sumP[j]+=sumP[j^(1<<i)];

for(j=1;j<maxs;++j)
            if(sumP[U^j]==1) return puts("INF"),0;
            else res+=(__builtin_popcount(j)&1?1:-1)/(1-sumP[U^j]);

printf("%.5Lf\n",res);

for(j=0;j<maxs;++j) sumP[j]=0;
    }

#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	#endif
    return 0;
}
```

最后修改：2024 年 04 月 27 日