Codeforces Round #362 (Div. 2)

6/6

这场CFdiv2有六题，拖了很久终于补完了。。。。撒花~~撒花~~

题A Pineapple Incident

题意：告诉你 t, t?+?s, t?+?s?+?1, t?+?2s, t?+?2s?+?1……周期地发生什么，给你t，s，k，问你k可不可能是其中的某个数？

题解：简单题，先判断k是不是t，然后判断k-t和k-t-1是不是s的倍数即可。

题B Barnicle

题意：给你一个科学计数法表示的浮点数，展开它。

题解：注意0的情况和1.0e0的情况即可。

题C Lorenzo Von Matterhorn

题意：给你一颗二叉树，然后告诉你会有两种操作：

1.u v w表示u到v的路径的边增加w

2.u v询问路径权值为多少

题解：暴力！暴力！暴力！直接开个map暴力放进去，从u和v不断往前爬知道公共祖先。询问也一样。

题D Puzzles

题意：给你一棵树，然后让你模拟dfs，但是dfs的时候如果有多个结点，那么则随机选一个结点去访问，最后问你每个点访问时间的期望，假设访问一个结点用时1s。

题解：我们可以这样考虑，采用平均的策略，即（最好+最坏）/ 2；

最好：马上找到一个结点，用时1s

最坏：访问完剩余子树再来访问这个子树，那么就是其他子树的结点；

所以最后答案为：（假设当前树的sz为s1，要算的子树的sz为s2）

(s1 - s2 + 1) / 2；

题E PLEASE

题意：给你三个杯子，然后把要猜的东西放在中间，然后随意把左右的杯子拿来交换，做n次，然后最后猜的是中间，问你中的概率？这个n很大，他给你k个数，a1……ak，这k个数乘起来表示n。

题解：杯子的所有情况：

2 -> 13 -> 2312 -> 13122313……

2的出现次数为0、2、2、6……

最后可以推出这个序列为an = 2^n-1 - an-1，因为一共有2^n种可能，所以答案为：

bn = an / 2 ^ n，最后化简得:

现在n = ，指数很大我们都用欧拉定理进行降幂，具体参考欧拉公式。因为这个mod是素数，所以我们可以把n % (mod - 2)来进行降幂。最后说一下这道题要求的输出方式：是把分子mod了之后分母mod了之后输出，但是这个分子分母来自于我们的推导公式，也就是分子 = an，分母 = 2 ^ n。

题F Legen...

题意：给你n个串，每个串有自己的权值，构造一个长度为l的串使得这个串的权值最大，这个串的权值是n个串出现一次就会加上相应的权值。

题解：这道题要用到倍增floyd的思想。

先安利一篇论文里面解释了为什么能够这样做：

俞华程《矩阵乘法在信息学中的应用》

这里简单复述一下：

假设dp[i][j]为当前长度为i，末尾为j结点（Ac自动机构造的），然后转移方程为：

然后假设g[i][j]为i结点到j结点增加的权值，那么就可以类似地得到下面的矩阵转移方程：

最后利用矩阵乘法加一下速即可。