23.4.18 考试小记

发布于 2018-04-23  4.6k 次阅读


又是一天数学题。

T1

A和B玩剪刀石头布,每一轮需要玩n局,B知道每一局A三种决策的概率,且B会采取最优策略,当B胜A m2 轮的时候B胜利,A胜B m1轮时A胜利,如果一轮平局则直接作废,求B胜利的最大概率。

首先这个问题中A和B是在合作而不是博弈,注意到每一轮其实都是一样的,所以我们考虑求出一轮中B的最大胜率。

考虑B进行的决策序列,我们并不能仅仅按照使得当前步内的期望收益最大的贪心策略进行决策,因为这样虽然能让最后期望收益最大,但是并不能使获胜的概率最大,因为我们并不关注获胜后胜利的局数,而只关注能使获胜次数大于0的概率,所以我们应该动态的进行决策,而不是贪心。

因为平局其实是不考虑的,所以我们可以直接忽略平局的情况,改变状态空间的大小,设p为胜率,q为败率,则我们的目的是最大化k=p/(p+q),可以转化一下:

$$ k = \frac {p} {p+q} = 1 -  \frac {1} {1+ \frac {p} {q} } $$

这样,我们最大化的对象就变成了t=p/q,可以用分数规划的方法,二分t,使得最大的p-tq>0。

接下来,我们可以DP解决这个问题。为了考虑决策的顺序,我们需要倒着进行DP。

设f[i][j]表示[1,i]轮中,差为j时,[i+1,n]的最大期望收益,这样最后的答案就是f[0][0],转移时枚举三种决策即可,初始化要把正的差设为1,负的设为-t。为什么要这样初始化?因为我们这样就可以用对应的概率乘上最后的贡献了,如果胜利了对胜率的贡献是1,否则就对败率贡献是1,需要乘上-t。

最后,我们知道了最优胜率后,可以用高斯消元或者直接迭代来处理,因为这道题是浮点数运算,而且收敛的很快,所以迭代次数最多也就几千次,我就直接沿用考试的做法了。

 

T2

考试的时候题目少了条件导致根本不可做(还好我有梦想瞎容斥了一波,得了60),然而正解很神,到现在还没人看懂题解。

 

T3

给定一张n个点m条边的无向图,每条边有红绿蓝之一的颜色,求满足绿边<=g,蓝边<=b的生成树的个数。

其实之前做过类似的题目,主要还是利用矩阵树加上一点多项式的知识。把红边边权看作1,绿边x,蓝边y,那么直接矩阵树后求出的其实是一个多项式,而它的合法项系数就是我们的答案,因此,题解给出了“二维拉格朗日插值”的神奇做法,然而我连一维的都不会。因此,我们可以继续使用高斯消元,将每个系数看作变量,给xy代数然后矩阵树求行列式,最后高斯消元就好了。

由于变量数是O(n^2)的,所以总复杂度是O(n^6+n^5logn),然而我们的变量数其实要/2,高斯消元的常数应该要/6,所以其实是可过的。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974