2018 Multi-University Training Contest 8 比赛记录

Author Avatar
Sakits 8月 15, 2018

enter image description here

A. Character Encoding

solved by Sakits. 00:25:24 (-1)

  上来就秒了,结果调了半天求组合数,最后组合数没开两倍大小还爆了一发…(我怎么现在多校整天写的都是数学题啊…
  二项式反演。
  至少有ii个超过限制的数的方案为AiA_i,则有:

Ai=(mi)(Ki×n+m1m1)A_i=\binom{m}{i}\binom{K-i\times n+m-1}{m-1}

  设恰好有ii个超过限制的数的方案为BiB_i,则有:

Ai=j=im(ji)BjA_i=\sum_{j=i}^m \binom{j}{i}B_j

  二项式反演可得:

B0=i=0m(1)iAi=i=0m(1)i(mi)(Ki×n+m1m1)\begin{aligned} B_0&=\sum_{i=0}^m(-1)^iA_i\\ &=\sum_{i=0}^m(-1)^i\binom{m}{i}\binom{K-i\times n+m-1}{m-1} \end{aligned}

  就完了

B. Pizza Hub

solved by reek. 03:24:28 (-9)

  寄蒜几盒,胡爷爷不知道HDU不能用long double爆了几发…

D. Parentheses Matrix

solved by reek. 02:36:34 (-3)

  神仙构造题。

E. Magic Square

solved by DriverLao. 00:35:16 (-3)

  按照题意模拟即可。

J. Taotao Picks Apples

solved by Sakits. 02:44:29 (-1)

  MD一开始看错题还给写出来了,难度比这题大多了…(可以拿去出毒瘤题了…
  这题直接离线处理询问,先正着预处理一波,然后倒着单调栈,在单调栈上二分答案即可。