[NOIP2016]换教室
[P4550]收集邮票 : 看题解
[BZOJ4204]取球游戏
有(m)个球，一开始每个球均有一个初始标号，标号范围为(1～n)且为整数，标号为(i)的球有(a_{i})个，并保证(Σa_{i} = m)。
每次操作等概率取出一个球（即取出每个球的概率均为(frac{1}{m})），若这个球标号为(k（k < n）)，则将它重新标号为(k + 1)；若这个球标号为(n)，则将其重标号为(1)。（取出球后并不将其丢弃）
现在你需要求出，经过(K)次这样的操作后，每个标号的球的期望个数。
(dp[i]:)编号为(i)的球的个数
(dp[i]=dp[i]+dp[i−1]∗frac{1}{m}−dp[i]∗frac{1}{m})
(dp[i]=frac{1}{m}dp[i-1]+frac{m-1}{m}dp[i])
写成矩阵形式,发现是个循环矩阵(从第2行开始都是由前一行向右移一位得到的)
循环矩阵乘循环矩阵还是循环矩阵
所以只要记录第一行即可
[CH3803]扑克牌
(54)张牌，每次随机摸一张，求得到 A张黑桃 B张红桃 C张梅花 D张方块 的期望步数．特别地，大王和小王可以当做任意一种花色，当然，会选择当前的最优策略．
设(f[a][b][c][d][p][q])代表已选了(a,b,c,d,)王的情况为(p,q)时到达目标的期望步数．设最终状态步数为(0),则(f[0][0][0][0])即为所求．
这是因为初始情况只有一个，而最终情况有很多种．
所以这道题用到 记忆化搜索
算出已经选的牌(sum),则有
(f[a][b][c][d][p][q]=frac{13-a}{54-sum}f[a+1][b][c][d][p][q]+frac{13-b}{54-sum}f[a][b+1][c][d][p][q])
(+frac{13-c}{54-sum}f[a][b][c+1][d][p][q]+frac{13-d}{54-sum}f[a][b][c][d+1][p][q])
(+min{frac{1}{54-sum}f[a][b][c][d][1∼4][q]}(if p==0))
(+min{frac{1}{54-sum}f[a][b][c][d][p][1∼4]}(if q==0))
[HDU4035]Maze
一棵树 , 从结点(1)出发 , 开始走 , 在每个结点(i)都有(3)种可能 :
(1.)被杀死 , 回到结点(1)处 (概率为(k_i))
(2.)找到出口 , 走出迷宫 (概率为(e_i))
(3.)和该点相连有(m)条边 , 随机走一条
求走出迷宫所要走的边数的期望值
(1.)设对每个结点转化为：(E[i] = Ai*E[1] + Bi*E[father[i]] + Ci;) $ $方便dfs中转移
(2.)推式子要考虑清楚叶节点的情况 , 要记得乘上概率(frac{1}{m})
[HDU4089]Activation
题意：有(n)个人排队等着在官网上激活游戏。Tomato排在第(m)个。
对于队列中的第一个人。有一下情况：
1、激活失败，留在队列中等待下一次激活（概率为(p1))
2、失去连接，出队列，然后排在队列的最后（概率为(p2)）
3、激活成功，离开队列（概率为(p3)）
4、服务器瘫痪，服务器停止激活，所有人都无法激活了。
求服务器瘫痪时Tomato在队列中的位置(<=k)的概率
详见原博客
[USACO18DEC]Balance Beam
可以这样理解 : 如果想要从(i)跳到一个(l)或(r)停止 , 则期望得分为(frac{r-i}{r-l}val[l]+frac{i-l}{r-l}val[r])
类似于在(l)点和(r)点连一条线 , 如果是凸包的形状 , 则期望得分更优 .
所以凸包上的点是停止点 , 一个点的期望得分(=)左边的停止点得分(*)概率(+)右边的停止点得分(*)概率
CF1097D Makoto and a Blackboard
给定 (n,k)一共会进行 (k) 次操作 , 每次操作会把 (n) 等概率的变成 (n) 的某个约数
求操作 (k) 次后 (n) 的期望是多少
(f[i][j]) 表示以某质数的 (i) 次方经过 (j) 次操作后的结果
发现答案是积性的 , 质因数分解后转移
(f[n][k]∗f[m][k]=f[nm][k] (gcd(n,m)=1))
对于(f[i][j])的转移 :
(f[i][j]=frac{1}{i+1}sum_{k=0}^{i}f[k][j-1])
大胆猜测积性的性质 , 转化为质因数分解后求解
其实肯定要写出最基础的暴力才能发现一些性质 , 所以不管是什么题都要先把暴力打了再说 ; 积性函数这种猜想还是要打表证明一下
记忆化是一个神奇的东西
[PKUWC2018]随机游走
最值反演 (又称 MinMax容斥 ) : $$max{S}=∑_{T⊆S}(−1)^{|T|−1}min{T}$$
觉得这是一种很流氓的搞法 , 做法就是字面意思 : 把集合中全部取到的期望(=)所有子集中至少有一个被取到的期望的容斥
然后就可以直接转化了 , 设(f_i=A_i*f_{fa[i]}+B_i),再推一下式子即可 , 类似于这道题[HDU4035]Maze
[六省联考2017]分手是祝愿
每次随机选择一个开关(i) , 会使(i)的约数状态全部改变 , 目标把全部灯关上 , 如果当前最优策略步数(le K)则停止随机选 , 直接选(K)次 , 求期望步数
任何键的操作都不能被别的键替代 , 这就不再是一道(DP)题 , 而转化为一道期望题了
设 (f[i]) 表示从 (i) 个需要按的键到 (i-1) 个需要按的键的期望操作次数
则 (f[i]=frac{i}{n}+frac{n-i}{n} imes(f[i]+f[i+1]+1))
意思是有(frac{i}{n})的概率按到正确位置 , 其他的按错了还要按回来
化简得 (f[i]=frac{n+(n-i) imes f[i+1]}{i})
如果$ cnt>K$直接把 (f[cnt]+f[cnt-1]+....+f[k+1]) 作为答案即可
[TJOI2015]概率论
求(n)个节点的二叉树的叶节点期望个数
令(f_n)表示 (n) 个点的二叉树个数 , (g_n)表示 (n) 个点的所有 (f_n)棵二叉树的叶节点总数
对于每个(n)个节点的二叉树 , 都有(n+1)个位置可以长出一个新节点 , 这样的每一个长出的新节点都要算进去
所以 (g_n=nf_{n-1})
对于(f_i)的递推有形如卡特兰数的式子 , 即枚举左右儿子的大小
(f_n=sum_{i=1}^{n-1}f_if_{n-i-1})
通项公式 :(f_n=frac{inom{2n}{n}}{n+1}=frac{4n-2}{n+1}f_{n-1})
于是答案即为 $frac{g_n}{f_n} = frac{nf_{n-1}}{f_n}=frac{n(n+1)}{2(2n-1)} $
[LnOI2019][P5249]加特林轮盘赌
轮流开枪打一个环上的人 , 每次(p)的概率打死 , (p)始终相同 , 从第(1)个人开始 , 求第(k)个人成为唯一幸存者的概率
19.3.30
设(f1[i])表示([1,k-1])在(i)轮以内全死的概率 , (f2[i])表示([k+1,n])在(i)轮以内全死的概率 ,
(s[i])表示某一个人在(i)轮以内死掉的概率 , 易知(s[i]=1-(1-p)^i)
(f1[i]=s[i]^{(k-1)})
(f2[i]=s[i]^{(n-k)})
枚举第(k)个人第(i)轮死 , (ans=sum{f1[i]*f2[i-1]*(s[i]-s[i-1])})
(10^4)个人枚举(10^6)轮就差不多了 , (f1)和(f2)的预处理是(O(nl_{og}n))的
19.4.4
首先可以容易地得出某一个人在(i)轮以内死掉的概率(s[i]=1-(1-p)^i) , 以及在第(i)轮死掉的概率(s[i]-s[i-1])
也许就能推出连续一段人在(i)轮死掉的概率(s[i]^{r-l+1})
考虑怎么枚举比较方便 : 枚举自己在第(i)轮死 ,
那么在此之前其他的都要死 , 即前面的要在(i)轮内死 , 后面的要在(i-1)轮内死
枚举自己的状态 , 考虑前面和后面要满足的条件 , 参考[JSOI2018]机器人
[HNOI2015]亚瑟王
(n)个技能 , 打(k)轮 , 每轮按顺序可能打出某个技能 , 第(i)个技能有(p_i)概率发动并打出伤害 , 且(k)轮内每个技能只能发动一次 , 求期望伤害
19.4.1
设第(i)张牌被使用的概率为(f[i]) , 则(ans=sum{f[i]*d[i]})
有(f[1]=1-(1-p[i])^m)
设(g[i][j])表示前(i)张牌中使用(j)张的概率 , 则
即有(j)轮不会考虑到(i) , 还有(m-j)轮会考虑到(i) , 这些轮中又要选(i)的概率
转化为求(g[i][j])的转移方程
(1.)取了第(i)张牌 (g[i][j]=sum{g[i-1][j-1]*(1-(1-p[i])^{m-j+1})})
(2.)没取第(i)张牌 (g[i][j]=sum{g[i-1][j]*(1-p[i])^{m-j}})
19.4.4
枚举当前点的思路 :
使用第(i)张牌的概率为(f[i])
设(g[i][j])表示前i轮中选(j)张牌的概率 , 那么就可以推到到当前第(i)张有多少轮是考虑过了的
(利用好题目意思可以想到 , 因为如果轮数没打完是一定要继续打的)
一般复杂的纯期望题都要转化一步 , 求另一个式子的转移方程 , 但也一定要考虑好题目要求的信息的转移方程
求(g[i][j])的时候还是枚举当前点状态(取没取第(i)张) : 那么前面的要怎么样(已经取了(j)张或(j-1)张) , 转移条件是怎么样(剩下的轮怎么样)
这里也体现了阶段的重要性 , 即依次考虑每个点
[SCOI2008]奖励关
结束状态很多 , 而初始状态是确定的 , 所以考虑从后往前(DP)或者从前往后记忆化搜索
转移可以参考[CH3803]扑克牌的记忆化搜索做法 , 而本题可以用(DP)
设(f[i][S])表示在第(1)轮到第(i-1)轮内宝物是否取过的状态为(S)，第(i)轮到第(K)轮的最大期望得分
答案就是(f[1][0])
状态的转移无非就是(轮数,已选状态)之间的递推 ; 还有就是一定要把题看清 , 比如这里的每个物品只能得一次分
如果可以取 , (f[i][S]+=max(f[i+1][S],f[i+1][S|(1<<k-1)]+P_k))
否则不能取 , 即(f[i][S]+=f[i+1][S])
[HAOI2018]苹果树
求(n)个点的二叉树上所有点对距离之和(定义为边数)的期望(*n!)的结果
19.3.22
路径长的期望又乘上 (n!) , 因为(n)个点的二叉树有(n!)种,所以相当于算可能的情况的贡献和.
令 (f_i)表示 (i) 个节点的子树，根的深度为 (1) 时，所有点的期望深度之和（乘 (i!) ）的值
令 (g_i)表示 (i) 个节点的子树，期望两两路径之和（乘 (i!) ）的值
(L,R) 分别表示左右子树的大小
那么$$ f_i = i * i! + sum limits_{L+R=i-1} inom{i - 1}{L} (f_L * R! + f_R * L!)$$
19.4.4
这就是传说中的(Wearry)的计数神题了吧 .
(n)个点的二叉树有(n!)种 , 答案乘上(n!)提示我们要求所有可能的二叉树的情况的贡献之和
设(g[i])表示(i)个点的二叉树的所有情况的点对路径之和
常见的套路是枚举左右子树的大小 , 发现要是能维护深度之和就好了
枚举左右儿子的时候 , 对于左儿子(f[i]) , 右儿子有(j!)种情况 , 对于右儿子(f[j]) , 左儿子有(i!)种情况
然后对于(g)的转移 , (f[i])还需要乘上(j+1)代表和其他点组合