TCO19 SRM 752 Div1 解题记录

### Easy ReconstructNumber
题意：要构造一个最小的没有前导0的数满足一些条件：对于每一个相邻的数位$a_i,a_{i+1}$会有$>,<,=,!$四种条件分别表示$a_i$是大于/小于/等于/不等于$a_{i+1}$，条件个数$n\le 2000$

题解：直接$dp$，$f(i,0-9)$直接表示到第$i$位，$0-9$结尾的最优方案。每一次暴力更新，时间复杂度$O(10n^2)$

### Medium Literature

题意：三个人玩一个游戏，有$3n$张牌写着$[1,3n]$的每一个数字，一开始三个人各摸$n$张牌，三个人轮流操作：每一次随机说一个自己没有的牌。现在已经进行了$m$个操作，给出第一个人的手牌，问第一个人期望在多少轮后知道所有人的牌。
$n\le 1000,m\le 200$

题解：直接$dp$，考虑设$f(i,j,0/1/2)$表示$B$有$i$个确定，$C$有$j$个确定，轮到$A/B/C$的情况下到终点的期望步数。$f(n,n,A/B/C)$显然就是$0$，考虑列出方程：
$$f(i,j,0)=\frac{n-j}{2n}f(i,j+1,1)+\frac{n+j}{2n}f(i,j,1)+1$$
$$f(i,j,1)=\frac{n-i}{2n}f(i+1,j,2)+\frac{n+i}{2n}f(i,j,2)+1$$
$$f(i,j,2)=f(i,j,0)+1$$
发现带环，实际上可以把上一层的状态看作常数，把$f(i,j,0)$解出来。
$$f(i,j,0)=\frac{\frac{n-j}{2n}f(i,j+1,1)+\frac{(n+j)(n-i)}{4n^2}f(i+1,j,2)+\frac{(n+j)(n+i)}{4n^2}+\frac{n+j}{2n}+1}{1-\frac{(n+j)(n+i)}{4n^2}}$$
就可以直接$DP$了。
总的来说，还是道不是很难的小清新概率题。
### Hard TokenDoublingGame

题意：桌子上一开始有$n$个棋子，你的手里一开始有$1$个棋子，你每次随机选择如下操作中的一种：
1、弃掉手中所有棋子，新拿两个棋子，一个放桌上，一个放手里，如果桌上有$2n$个棋子时结束游戏。
2、如果手中有$X$个棋子，那么从桌上拿$X$个。如果桌上在拿完后或者在拿的过程中没有棋子了，结束游戏。
问进行游戏的期望步数。
$n\le 10^5$

Rockdu's Blog

导航

最近发表

大佬们的友链