Minimax

显然每个叶节点的值都是能取到的。

设 $dp_{i,j}$ 表示点 $i$ 取到第 $j$ 小的值的概率。当 $i$ 是叶节点或者仅有一个儿子是转移很容易,有两个儿子时的转移也不难写出
$$
\begin{aligned}
dp_{i,j}&=dp_{ls,j}\times\left(\sum_{k<j}dp_{rs,k}\times p_i+\sum_{k>j}dp_{rs,k}\times(1-p_i)\right)\\&+dp_{rs,j}\times\left(\sum_{k<j}dp_{ls,k}\times p_i+\sum_{k>j}dp_{ls,k}\times(1-p_i)\right)
\end{aligned}
$$
考虑开 $n$ 棵线段树来维护每个点对应的 $dp$ 数组,那么转移时直接线段树合并即可。

具体的,每次合并时记录两边的贡献,并在线段树上打乘法标记即可。这一部分可以结合代码理解一下。

时间复杂度 $\mathcal{O}(n\log n)$,空间复杂度 $\mathcal{O}(n\log n)$。

代码

Slay the Spire

首先考虑,假如已经随机出了 $m$ 张卡,怎样才能使总伤害最大。

容易发现的是,因为强化牌上的数字都大于 $1$,所以多选强化牌必然更优;而我们选的必然是最大的那些牌。

那么就可以得到一个贪心策略了:

  • 如果强化牌的数量 $<k$,则选所有强化牌,然后选最大的攻击牌补至 $k$ 张。
  • 否则,选最大的 $k-1$ 张强化牌,然后选最大的一张攻击牌。

那么我们考虑计算所有最优选择方案在多少种抽取方案中。

首先将强化牌和攻击牌各从大到小排序。

设 $f_{i,j}$ 表示前 $i$ 张强化牌选了 $j$ 张所有方案的强化数值之和,$g_{i,j}$ 表示前 $i$ 张攻击牌选了 $j$ 张所有方案的攻击数值之和。

容易得到转移
$$
\begin{aligned}
f_{i,j}&=f_{i-1,j-1}\times w_j+f_{i-1,j}\\
g_{i,j}&=g_{i-1,j-1}+{i-1\choose j-1}\times w_j+g_{i-1,j}
\end{aligned}
$$
然后枚举随机出的强化牌的数量,利用组合数计算出答案即可。时间复杂度 $\mathcal{O}(Tn^2)$。

不开 O2 会 WA 的代码

斗地主

非常抱歉,这个题鸽了。

随机算法

设 $dp_S$ 表示子图 $S$ 的正确率,$mx_S$ 表示子图 $S$ 的最大独立集大小。

考虑转移。记 $T_i$ 为 $S$ 去掉 $i$ 和所有与 $i$ 相连的点后形成的集合。那么首先有
$$
mx_S=\max_{i\in S}\left\{mx_{T_i}\right\}+1
$$
然后有
$$
dp_S=\frac{\sum_{i\in S}[mx_S=mx_{T_i}+1]dp_{T_i}}{|S|}
$$
时间复杂度 $\mathcal{O}(n2^n)$。

代码

猎人杀

考虑一个比较神仙的转化:每个人死后不让他退场,而是给他一个标记;选择对象时如果选中了一个有标记的人就重选一次。可以发现这样子答案是一样的。

这个转化有一个好处:分母 $\sum_{j=1}^mw_{i_j}$ 恒等于 $\sum_{i=1}^nw_i$,也就是说分母不会变了。

接着可以考虑一个容斥。我们钦定 $S\;(1\notin S)$ 中的人在 $1$ 之后死,那么容斥系数为 $(-1)^{|S|}$,概率为
$$
\frac{w_1}{\sum_{i=1}^nw_i}\times\sum_{i=0}^\infty(1-\frac{w_1+\sum_{j\in S}w_j}{\sum_{j=1}^n w_j})^i
$$
后面的东西可以等比数列求和,整个式子化简为
$$
\frac{w_1}{w_1+\sum_{i\in S}w_i}
$$
可以发现不同的 $\sum_{i\in S}w_i$ 只有至多 $100000$ 个,因此我们可以考虑对于每个 $\sum_{i\in S}w_i$ 计算出它前面的系数。

容易发现这是一个背包的过程:对于每个 $w_i$,加入它后系数乘上 $-1$。但是直接背包的话复杂度无法承受。

考虑生成函数。第 $i$ 个人的生成函数是 $-x^{w_i}+1$,我们只需要将第 $2$ 到 $n$ 个人的生成函数乘起来即可。可以使用分治 FFT 完成。时间复杂度 $\mathcal{O}(n\log^2 n)$。

代码

随机游走

考虑 min-max 容斥的式子
$$
E(\max\{S\})=\sum_{T\subseteq S}(-1)^{|T|+1}E(\min\{T\})
$$
如果我们把第一次被访问到时走的步数作为每个元素的权值,那么这里的 $\max\{S\}$ 即为访问完 $S$ 中所有元素的步数,$\min\{S\}$ 即为第一次访问到 $S$ 中某一个元素的步数。

那么我们仅需要求出从 $u$ 出发第一次访问到 $S$ 中某个元素的期望步数即可。

设 $f_{u,S}$ 表示从 $u$ 点出发,访问到 $S$ 中某个元素的期望步数。容易列出方程
$$
f_{u,S}=\frac{\sum_{(u,v)\in E}f_{v,S}}{deg_u}
$$
直接高斯消元显然会 T。因为这是在树上,所以可以使用一种叫做「树上高斯消元」的科技。

设 $f_{u,S}=a_u\times f_{fa,S}+b_u$,然后推一推式子:
$$
\begin{aligned}
f_{u,S}&=\frac{f_{fa,S}+\sum_{v\in son_u}f_{v,S}}{deg_u}+1\\
&=\frac{f_{fa,S}+\sum_{v\in son_u}(a_v\times f_{u,S}+b_v)}{deg_u}+1\\
&=\frac{f_{fa,S}+\left(\sum_{v\in son_u}a_v\right)\times f_{u,S}+\left(\sum_{v\in son_u}b_v\right)}{deg_u}+1
\end{aligned}
$$

$$
\begin{aligned}
suma_u&=\sum_{v\in son_u}a_v\\
sumb_u&=\sum_{v\in son_u}b_v
\end{aligned}
$$

$$
f_{u,S}=\frac{f_{fa,S}+suma_u\times f_{u,S}+sumb_u}{deg_u}+1
$$
化简得到
$$
f_{u,S}=\frac{f_{fa,S}}{deg_u-suma_u}+\frac{sumb_u+deg_u}{deg_u-suma_u}
$$
比较系数得到
$$
\begin{aligned}
a_u&=\frac{1}{deg_u-suma_u}\\
b_u&=\frac{sumb_u+deg_u}{deg_u-suma_u}
\end{aligned}
$$
发现这个仅和子树中节点有关,那么就可以直接在树上 DFS 求出了。注意边界问题:当 $u\in S$ 时 $f_{u,S}=0$,所以此时 $a_u=b_u=0$。另外根节点 $x$ 没有父节点,因此 $f_{x,S}=b_x$。

现在我们已经求出了所有的 $f_{u,S}$,而实际上 $E(\min\{S\})$ 就是 $f_{x,S}$,那么我们就可以通过 min-max 容斥求出答案了。时间复杂度 $\mathcal{O}(Q2^n)$。

仔细观察 min-max 容斥的式子,可以发现是子集和的形式,于是用 FWT 预处理出所有子集和即可。时间复杂度 $\mathcal{O}(n2^n)$。

代码

最后修改:2021 年 03 月 22 日 09 : 43 PM