over 2 years ago

前言

三道题难度还算适中。

A

两个人玩游戏,每个人都有堆石子,每堆石子的个数分别为,保证都是递增的,每次两个人从各自的石堆中随机选出一堆石子,如果,那么第一个人赢下这一轮,否则第二个人赢下这一轮,之后两人把这堆石子扔掉,假设最终第一个人赢了轮,那么得到的收益就是,求期望收益。

我们考虑容斥的想法,设表示前堆,第一个人有堆一定赢了,其余堆赢不赢未知的方案数,设表示第一个人的第堆可以打败第二个人的前堆,那么递推的方程就是:

最后把乘上,设表示赢堆的方案数,我们发现这个求出的实际上是:

那么我们就可以求出答案了。
duel.cpp

B

给定长度为的字符串和长度为的字符串,字符集大小为,定义字符串“相等”为经过若干次交换任意两种字符后,,注意这里的交换两种字符指的是把所有变成,把所有变成,求中与相等的子串个数。
,每组测试点有组数据
注意这里字符串的同构定义稍微变化了一下,但是这依然阻挡不了我们的脚步,我们可以记录出一个字符的前驱,然后根据题目中的描述来定义等于,这样我们就可以照样匹配了。
reform.cpp

C

给定平面上个不相交,不包含的圆,求出相切的圆的对数。

首先答案是线性的,这个是可以证明的,也可以构造出最大的答案。
然后我们可以用维护一条扫描线从左往右,相切的圆一定只会出现在中相邻的两个元素中,于是我们每次加入时判断一下当前点和前驱,当前点和后继,删除时判断一下前驱和后继即可。
bubble.cpp

← C(n,m) mod M NOI2016游记&&感想 →
 
comments powered by Disqus