MiceHunter 杯省选模拟赛 III

OI - Official

From This_poet


小时

尚未报名

信函加密 25/36 From
Rainbow的问题 13/33 From
卖萌分身术 13/46 From

题解:

第一题:送分题哎……题目的结构就是一个二叉排序树(实际上题面里都告诉你了),因此我们记录一下深度,直接用一个set扫一遍就好。详细可以参见标程。

第二题:这里需要用到一种特殊的素数:梅森素数
我们把满足 E = 2 ^ i - 1 的素数E称作梅森素数。
关于梅森素数,有一个重要的定理:“一个数能够写成几个不重复的梅森素数的乘积” 等价于 “这个数的约数和是2的幂次”。
还有一个重要内容就是,N的约数和幂次是可以直接由构成它的梅森素数的来源幂次相加而得的。
梅森素数是非常少的,在题目给出的范围之内,只有8个梅森素数,可以打表列出,然后判断每一个给出的数中是不是唯一拥有若干个梅森素数。
之后由于只有8个梅森素数,使用状态压缩DP即可。

第三题:记F[i]为i次操作后的总分,X[i]为i次操作后横坐标的和,Y[i]为i次操作后纵坐标的和,T[i]为i次操作后猫咪总数。
那么有如下递推式:
F[i] = (S - L - R) * F[i-1] + S * Y[i-1]
Y[i] = S * Y[i-1] + (L - R) * X[i-1]
X[i] = (R - L) * Y[i-1] + S * X[i-1] + S * T[i-1]
T[i] = (L + R + S) * T[i-1]
N的范围较大,所以要用矩阵乘法来加速递推。

最后来宣传一下出题人的新Blog地址:http://thispoet.tk:777。(跟CH是同一个服务器……)