2021-11-15 Test

雀氏码农场，一道构造后的大模拟，一道恶心的数据结构，相形见绌的网络流。

Solutions:

A

感觉对期望的理解始终不强。

这题又利用了期望的线性性。考虑每个点被删除的概率。总期望就是每个点被删除的期望之和，不难发现就是每个点被删除的概率之和。

每个点何时会被删除？设他的度数为 $d_i$ ，那他会被删除的概率就是 $1- {1\over d_i + 1}$。

B

不会的 DS 题

C

大模拟题。

D

咕