PKUWC2018题解

PKUWC2018

按照( exttt{loj})的顺序写的

「PKUWC2018」Minimax

比较神仙的线段树合并,可能是我对于线段树合并还了解的不够透彻吧.

很显然可以对于每一个点的取值离散化后(dp)概率对吧.

[egin{align} dp_{u,i}&=dp_{l,i} imes(sum_{j=1}^{i-1}dp_{r,j}*p+sum_{j=i+1}^{tot}dp_{r,j}*(1-p))\ &+dp_{r,i} imes(sum_{j=1}^{i-1}dp_{l,j}*p+sum_{j=i+1}^{tot}dp_{l,j}*(1-p)) end{align} ]

这个东西的转移需要一个前缀和一个后缀和.

然后线段树合并的套路就是对于这个东西在合并左右子树线段树的时候记录一个和.如果要返回直接打乘法标记上去.

很清奇

代码

「PKUWC2018」Slay the Spire

考虑贪心肯定是先选强化牌（从大到小），再选最大的攻击跑。

设(f_i)表示选(i)张强化牌的(prod)的(sum)，(g_i)表示选(i)张攻击牌的(sum).

那么不难发现答案就是(sum_{i=0}^mf_ig_{m-i}),可以用乘法分配律证明.

递推式为:

[f_i=sum_{j} egin{cases} f_{i-1} i ge k\ f_{i-1}*a_j i<k\ end{cases} \ g_i=sum_{j} inom{j-1}{i-1} a_j+ egin{cases} 0 i le m-k+1\ g_{i-1} i>m-k+1\ end{cases} ]

代码

「PKUWC2018」斗地主

对不起,它咕了.

「PKUWC2018」随机算法

比较容易的状压题.

考虑一个独立集的大小可以(dp),那么我们边(dp)独立集大小边(dp)概率.

考虑将一个点插入最后一个位置(即排列的最后一位),这样子的概率是(|S|)的,可能性是(sum_{S'}f_{S'})

那么如果最大独立集大小更新了,(f)数组也要清零.

代码

「PKUWC2018」猎人杀

神仙题!

现将题目转换一下,钦定开枪打死一个人为给这个人标记一个死亡标记,但是不让他死去.如果一次开枪选到了一个有标记的人就一直选下去.令一次选择为开枪(而不是一次死人为开枪)

这样子和题目原本求的东西没有区别.

考虑容斥:

令(S)表示至少在(1)后面死的人的集合,他们的(sum)为(Su),所有人的(sum)为(A),那么有:

[ans=-1^{|S|}sum_{i=0}^{infty}(1-frac{Su+w_1}{A})^icdot frac{w_1}{A} ]

式子的含义是在前面无限次开枪都不能够选到这些人,选完之后选到(1).

然后一个无穷等比数列(递减)求和可以化简为

[ans=-1^{|S|}frac{w_1}{w_1+Su} ]

这个时候发现我们不是很好求,考虑(dp)出所有和是(Su)的集合的容斥系数,那么就可以做了.

这就是01背包.

这样子可以获得80pts的好成绩.

再看一眼数据范围(sum_{1}^nw_i le 10^5),很好,可以做一点有意思的事情.

仔细思考一下背包的本质就是一个卷积,然后把背包数组写成一个生成函数,要求的就是:

[prod_{i=2}^n1-x^{w_i} ]

这样子就可以分治(NTT)了.

代码

「PKUWC2018」随机游走

首先看了题解发现可以(min-max)容斥,那么我们只需要求出(min)就可以了.

考虑树上高斯消元,设(f_u)表示(u)点到(S)集合最近点的期望值,这个东西树上高斯消元可以做到(O(n)).

具体而言是:

[f_u=1+frac{1}{d_u}{f_{fa_u}}+frac{1}{d_u}sum_{vin son_u}{f_{v}} ]

设(f_u=af_{fa_u}+b),然后推一下式子就知道:

[a_u=frac{1}{d_i-sum a_v}\ b_u=frac{d_i+sum b_v}{d_i-sum a_v} ]

这个东西就可以递推了.

然后答案就是(b_{root}).之后就是(FMT)的事情了.

注意(min-max)容斥的基本式子.

代码