2014-2015 Petrozavodsk Winter Training Camp, Contest.58 (Makoto rng 58 Soejima contest)

ultmaster: 久违地达到了平均贡献。

Problem A

Solved by kblack. 00:25 (+1)

略带凉意的签到。

Problem B

Solved by ultmaster. 03:07 (+)

Problem C

Solved by ultmaster. 01:34 (+)

Problem D

Solved by zerol. 02:39 (+1)

Problem G

Solved by kblack. 03:49 (+1)

题意：给一条简单折线，问能不能通过墙上一个小孔。

题解：等价于对于折线每个端点，都能找到一条直线使得所有之前和之后的点分立两侧，枚举点以后转一圈数一数。

Problem J

Solved by kblack. 00:53 (+)

题意：从一个 $d$ 维的超长方体上切下 $\sum_{i=1}^{d}{x_i} \leq s$ 的部分，求体积大小乘 $d!$（以下省略）。

题解：如果是切下完整的一个边长为 $x$ 的角，那么他的体积显然等于 $x^d$，但是有的维度会切光，切光了以后多出来的部分要剪掉，多个维度切光以后会重复剪掉，容斥的系数实际上是 $\prod_{i=1}^d{(1-x^{a_i})}$ 的系数，背个包乘一乘就好了。