NOIP2019模拟赛(十)06.02

Link

NOIP2019模拟赛(十)06.02

A. transfer

题意

有$n$个小孩,他们会进行$t$轮游戏。一开始,鲜花在第一个孩子手里,每轮游戏持有鲜花的小孩可以把鲜花传递给除了自己以外的任意一个小孩。那么,一共有多少种传递方法,可以让鲜花在游戏结束时回到第一个小孩上呢?
对于$100$%的数据,$n,t \leq 10^{18}$

思路

每一轮,每个小孩都可以传递给另外一个小孩,那么就有$n-1$种传递方法。
有$t$轮,所以总共有$(n-1)^t$种传递方法。
每种传递方法的概率都是相同的,所以传递给第一个孩子的可能性为$\frac{(n-1)^t}{n}$。
注意,$n,t$的范围都很大,所以需要快速幂$+$乘法逆元。
对于$NOIPPJ$等级的我,只需要明白:费马小定理:当$ p $为素数时,$ a^{p-1}=1 (mod p) $。那么$ a*a^{p-2}=1 (mod p) $。即可。

Code

B. minecraft

题意

思路

首先$O(n^2)$求出每个点到其他点的距离:$sqrt({(x_1-x_2)}^2+{(y_1-y_2)}^2)-(z_1+z_2)$
然后跑一遍最短路就好了。
但是二分答案来check也行。

Code

C. rewrite

题意

对于一片森林,有两个操作:
1. 输入$x,y$把$ x,y $两点连通,并且把他们的权值修改为$\frac{⌊Vx+Vy⌋}{2}$,若$x,y$已经连通,则忽略此操作。
2.查询$ x,y $两点之间的唯一路径上有多少种不同的点权,若$x,y $此时还不连通,输出$-1$。

思路

开一个$ 60 $位的二进制,某一位为$ 1 $就表示有这种颜色,然后用线段树维护区间信息就好了,每次合并或者查询就是一个二进制“或”的操作。
当然,用$LCT$与树剖都可以。

Code

暂无评论

发送评论


				
上一篇
下一篇