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 (+)

题意：给 50 个长度为 20 的字符串。字符串有些位置被挖掉了。让你把挖掉的位置填上使得组成一个有序的各不相同的字符串序列。问有多少种方案。

题解：f[l][r][p][ch] 表示从 l 到 r 的字符串，在 p 位置之前都是相同的，在 p 这个位置依次出现了 a, b, c, d, ... ch 这些字符的合法方案数。

转移的时候枚举 l 和 r 之间的 mid，对于符合 s[mid + 1][p] ~ s[r][p] 都相等，且可以填 ch 的 mid，增加 f[l][mid][p][ch - 1] * f[mid + 1][r][p + 1]['z']。

有几个小技巧：

• 写成记忆化搜索比较好写，对于 l > r 的状态可以直接返回 1。
• 注意各不相同，所以对于 ch < 'a' 的状态，不仅要判断字符串是否都结束了，还要判断 l == r。

感觉不怎么简单啊？为什么大家都会啊？

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})}$ 的系数，背个包乘一乘就好了。