好得没话说的题
# 题面
点击展开/折叠 题面
三个人玩游戏,一开始每个人分别有 $x,y,z$ 枚硬币。每轮游戏,有最多硬币的人(如果有两个人的硬币数量最多,则随机选取一人)把自己的一枚硬币随机地给另外两个人之一。游戏一直进行到三个人有一样多的硬币。
给定 $x,y,z$,求游戏期望进行多少轮,或期望值为 $+\infty$ 输出 $-1$。
# 解析
记 $n=x+y+z$,不难想到一个状态数为 $n^2$ 的 DP;为了方便下面分析正解,这里采取一个(在之后的正解中)更为优美的 DP 定义:$f(a,b)$ 表示,当最大值与另外两个值之差分别为 $a,b$ 时,期望进行多少轮结束。
为了方便描述,令 $a=x-y,b=x-z$,即 $x$ 为最大值。
终止状态 $f(0,0)=0$,不可达状态为 $3\not\mid a+b$ 的 $f(a,b)$。
然后考虑转移,需要注意的是转移硬币后最大值改变的情况:
- 若 $a,b\ge 2$,则 $x$ 无论分给哪一个,$x$ 也一定还是最大值,则有 $f(a,b)=\frac{f(a-1,b-2)+f(a-2,b-1)}2+1$;
若 $a=1,b\ge 2$($b=1,a\ge 2$ 同理):
如果 $x$ 分给 $z$,则 $x-1=y\ge z+1$,最大值不变:$f(0,b-2)$;
如果分给 $y$,则 $y+1=x,x-1=y$,其实并没有变化:$f(1,b)$;
则有 $f(1,b)=\frac{f(0,b-2)+f(1,b)}2+1$;
若 $a=0,b\ge 2$:
如果 $x$ 分给 $y$,则最大值变为 $y+1$,新的状态为 $f(2,b+1)$;
如果 $x$ 分给 $z$,则最大值变为 $y$,新的状态为 $f(1,b-1)$;
则有 $f(0,b)=\frac{f(2,b+1)+f(1,b-1)}2+1$;
对于 $f(0,b)$ 的转移式,把 $f(2,b+1)$ 的转移式代入可得:
这样我们消元得到了一个无环的 DP,可以在时间复杂度 $O(n^2)$ 内求解。
进一步分析,DP的转移只有在 $a<2$ 或 $b<2$ 时是需要消元来解环的,其他时候($a,b\ge 2$)的转移形式都是“日字形”,从 $(a,b)$ 转到 $(a-1,b-2)/(a-2,b-1)$。
那么可以先 $O(n)$ 预处理出 $f(0/1,b)$,然后直接计算每个 $f(0/1,b)$ 对 $f(x,y)$ 的贡献——
- $f(1,b)$ 对 $f(x,y)$ 的贡献就是 $T(L+f(1,b))\times2^L$,其中 $T$ 是从 $(x,y)$ 走日字形走到 $(1,b)$ 的路径条数,路径长度为 $L$。
- $f(0,b)$ 的贡献仍然是 $T(L+f(1,b))\times2^L$,但是注意 $T$ 包含的路径不能经过 $f(1,b+2)$,不然会和 $f(1,b+2)$ 的贡献算重。
# 源代码
1 | /*Lucky_Glass*/ |
THE END
Thanks for reading!
> Linked 赤途-网易云