洛谷3175 [HAOI2015]按位或
Luogu 分析 我们把每个数看成一些二进制位的集合，每一位的值是加入的时间。那么我们要求的是全集的 $\max$ 值。 考虑 min-max 容斥 那么只需要求子集和，可以 FMT。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.com/ // ==...
Luogu 分析 我们把每个数看成一些二进制位的集合，每一位的值是加入的时间。那么我们要求的是全集的 $\max$ 值。 考虑 min-max 容斥 那么只需要求子集和，可以 FMT。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.com/ // ==...
Luogu 分析 显然答案为 我们知道矩阵树定理求的实际上是 $\sum_T \prod_{e \in T} w_e$，于是我们可以使用矩阵树定理算出后面东西。 但是有 $p_e = 1$ 的情况，我们只需要把 $p_e$ 设为 $1-\epsilon $ 即可。 代码 //It is made by M_sea #include <algorithm> #include &l...
Luogu 分析 看到这个巨大的误差允许范围，可以考虑乱搞。 我们给所有入度为 $0$ 的点赋一个随机权值，然后将每个点的权值设为所有能到达这个点的点权的最小值。 经过一番推导后可以发现，这个权值的期望是 $\frac{\mathrm{RAND\_MAX}}{k}$，这里的 $k$ 是能到达这个点的入度为$0$的点的个数。那么这样子就能够估算出 $k$ 了。 代码 //It is made ...
Luogu 分析 设 $f_{i, j}$ 表示还剩 $i$ 个人时第 $j$ 个人的获胜概率。 考虑转移。首先枚举庄家抽到的卡牌 $k$，从而得到这一轮被淘汰的人的位置 $c$。 如果 $c \neq j$，则无法转移。否则第 $c$ 个人被淘汰之后，剩下的 $i-1$ 个人要组成一个新的环，庄家为第 $c$ 个人的下一个。容易算出，当 $c > j$ 时，第 $j$ 个人是新的环里...