about 2 years ago

前言

我的第一次SRM就是这么滚粗的QAQ,但不得不说TC的题目质量还是不错的。

题目大意

有两队人排队在超市的收银台等待付款,分别有个人。有两个收银员,每个收银员有一个属性,定义表示收取一个人费用的时间为的概率。求出第一队人处理完的时间严格小于第二队人的概率。

分析

为了方便我们直接令
我们可以发现的一个含义就是每轮有的概率决策,然后在第轮做出这个决策的概率。
我们设表示剩余两队分别剩余个人,第一队获胜的概率,我们考虑这个情况下两个队伍的决策情况。
(1)如果当前情况下第一队选那么贡献为
(2)如果当前情况下第二队选那么贡献为
(3)如果当前情况下都选那么贡献为
(4)如果当前情况下都不选那么这种情况的概率为,然后重新考虑(1)(2)(3)
(1)(2)(3)的和为,假设(4)的概率为,那么总贡献就是:

这样我们就可以直接转移了,时间复杂度
Queueing.cpp

← TC SRM686 CyclesNumber TC SRM685 FoxAirline2 →
 
comments powered by Disqus