2018 Multi-University Training Contest 6 比赛记录

Author Avatar
Sakits 8月 08, 2018

再次抱胡爷爷大腿上分~胡爷爷最后2min切掉了神仙题飞升进第一页233
enter image description here

A. oval-and-rectangle

solved by swm_sxt. 00:57:23(+3)

  欺负高一小朋友既不会椭圆又不会微积分呜呜呜…
  数学题跑去问瓜瓜~瓜瓜花了5min丢了个式子给我就A掉了,剧毒的是HDU要求的是小数点六位向下取整!而不是四舍五入…巨坑

B. bookshelf

solved by Sakits. 04:07:37(+4)

  贡献的一道比较有难度的题目。
  首先打表可得以下性质:

gcd(2fib(ai)1)=2gcd(fib(ai))1=2fib(gcd(ai))1gcd(2^{fib(a_i)}-1)=2^{gcd(fib(a_i))}-1=2^{fib(gcd(a_i))}-1

  然后题目就变成了求每种gcd(ai)gcd(a_i)的出现次数最后算算期望了。
  要算d=gcd(ai)d=gcd(a_i)的方案数肯定要先求dgcd(ai)d|gcd(a_i)的方案数啦~
  因为有:

i=1mai=n\sum_{i=1}^m a_i=n

  实际上可以看成是把nn个点按dd分组,然后分成mm组可有空组,这个方案显然是:

(nd+m1m1)\binom{\frac{n}{d}+m-1}{m-1}

  然后容斥一下就可以得到d=gcd(ai)d=gcd(a_i)的方案数了,当然也可以求个μ\mu当容斥系数。
  求出来之后直接代回原式求期望就好啦,忘记-1和多组数据炸了4发= =窝NOIP怕是要被多组数据送退役(flag)…
  复杂度应该是约数个数2^2的。

C. Ringland

solved by reek. 04:57:45 (-10)

  好像是个神仙智商题,还没看怎么做。

I. Werewolf

solved by reek & Sakits. 02:04:29 (-3)

  玩过狼人杀果然是好事。enter image description here
  其实这和反水立警被反水的人身份低是一个道理的。如果一个人被另一个人说是狼,而这个人却给他发金水,那在这题里就是铁狼了,因为村民不会说谎,只有狼才会。
  因为说是好人具有传递性,如果这个人说的好人说的好人说的好人说的好人说他是狼,那他也是铁狼,所以其实就是一个环里只有一条狼边,那么狼边的终点为铁狼。
  还可以扩展,说铁狼是村民的也是铁狼,并且铁好人是无法确定的,所以这题基环树找环一下就完了。

L. Pinball

solved by reek. 00:21:40 (-1)

  文化课选手胡爷爷一下就把这题切了。
  好像按斜面垂直和平行正交分解一下模拟直到跳到地面上就好了。