PKUWC2018

概率期望泛做

远古坑,历史遗留问题

还是naive了

Minimax

给出一颗以\(1\)为根的二叉树,叶子节点有权值,非叶子节点有\(p_i\)的概率取儿子中的大值,否则取小值。

设根有\(m\)种可能取值,从小到大构成序列\(V_i\),取到的概率是\(D_i\),求:
$$\sum\limits_{i=1}^{m}i\cdot V_i\cdot D_i$$

考虑\(O(nm)\)的暴力dp,离散化叶节点取值,设\(f[i][j]\)是点\(i\)取到\(j\)的概率,则有
$$f[x][i]=f[ls][i]\times\sum\limits_{j=1}^{i-1}f[rs][j]\times p[x]+f[ls][i]\times(1-\sum\limits_{j=1}^{i-1}f[rs][j])\times(1-p[x])$$
然后交换左右再加一次。

如何优化这个暴力,可以用线段树合并,复杂度就降低到了log级别。

Slay the Spire

有攻击牌和强化牌各\(n\)张,强化牌可以使手中所有的攻击牌乘以\(w_i\),攻击牌可以打出\(w_i\)的伤害。现随机选\(m\)张牌,然后以最大伤害打出\(k\)张。求所有情况的伤害和。

首先如果牌固定,显然有最优策略:优先先打高权值的强化牌,但是至少在最后打出一张高权值的攻击牌。

设\(a_i\)是强化牌权值,\(b_i\)是攻击牌权值。
先对\(a_i,b_i\)排序。

设\(ff[i][j]\)是后\(i\)张加强牌中选\(j\)张的所有情况的加强倍数的和,并且钦定选倒数第\(i\)张。
设\(f[i][j]\)是后\(i\)张加强牌中选\(j\)张的所有情况的加强倍数的和。

设\(gg[i][j]\)是后\(i\)张攻击牌中选\(j\)张的所有情况的攻击力的和,并且钦定选倒数第\(i\)张。
设\(g[i][j]\)是后\(i\)张攻击牌中选\(j\)张的所有情况的攻击力的和。

特殊处理\(k=1\)的情况,此时只能打一张攻击牌。

否则分两类,对于选择的强化牌大于等于\(k-1\)的情况,枚举使用的强化牌和攻击牌(强化牌一定是\(k-1\)张,可以利用\(ff\)线性枚举),然后用组合数算出选择了但未使用的牌的方案(一定比使用的权值要小)。

对于强化牌少于\(k-1\)的情况,同样枚举使用的强化牌和攻击牌,此时强化牌可以直接利用\(f\)枚举,再用组合数计算选择了但未使用的攻击牌方案数。

复杂度\(O(n^2)\)

随机算法

随机一个排列\(p_i\),维护最大独立集\(S\),最开始为空,从\(1\)到\(n\)检查,若\(S\cup p_i\)仍然是独立集,就使\(S=S\cup p_i\)。求这个算法正确的概率。

状压dp,设\(dp[S]\)是\(S\)集合正确的概率,显然由比\(S\)少任何一个元素的状态\(S’\)都可以转移过来,而且是等概率的,直接枚举转移,复杂度\(O(n\cdot 2^n)\)。


PKUWC2018》有4条评论

  1. :

    你太强辣!

  2. :

    你太强辣!

  3. 你太强辣!

    1. 我太弱啦QAQ

Leave a reply