Dwango Programming Contest 6th题解

Source

Dwango Programming Contest 6th

dwacon6th-prelims

B Fusing Slimes

请先思考后再展开

转化题意为,有n-1个长度为$a_i$的间隔,每次给一个间隔打上叉,且代价为自己+右边最长连续叉

于是考虑每个间隔的被统计次数,枚举被$i-j$按下,则$j+1..i都必须在j之前叉,即\frac{1}{i-j+1}$的概率,求和即可得到期望

code

请先思考后再展开

很容易想到考虑权值的组合意义就是每个球在覆盖它的区间里面选一个作为自己的颜色

于是只有有色球和没色球之分,$f(i)=i个没色球,f_{z}(i-t) \leftarrow f_{z-1}(i)*\sum_{u} C_i^uC_{n-i}^{a-u}C_u^t$,后面那个系数其实就是$C_i^t \sum_u C_{i-t}^{u-t}C_{n-i}^{a-u}$,范德蒙德卷积可知就是$C_i^tC_{n-t}^{a-t}$,$O(n^2k)$

code

D Arrangement

请先思考后再展开

感觉很不好卡故直接写了个爆搜,光荣tle

仔细想想什么情况下能卡,发现例如$n,n,n,n,n,n,1$这样,则必须第一个选n;于是爆搜的时候判断一下不是剩下所有点都指向$ban[nxt]$这个不能选的点就行了

code

E Span Covering

请先思考后再展开

显然容斥若干个位置一定没有被覆盖,则权值为$\prod_i (长度\ge L_i的段长和-L_i+1)$,这是个经典模型,从大到小考虑长度为now的段的数量,dp记录个数和长度和即可。

这个做法的复杂度咋一看是$O(X^3lnX)$,通过精细地处理不等式可以让常数非常小,n=1000可以0.5s通过,code

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/a528d33e.html
转载请注明出处,谢谢!