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

题意：给 5 个集合的大小，已知任意两个集合的交都不超过 1。求 5 个集合的并最小是多少。

题解：看起来很像是可以乱搞的题。然后就假了？

由于数据范围很小，很自然地想到可以暴搜枚举所有 31 - 5 = 26 种交集有还是没有。里面还有很多情况是非法的，可以剪掉。边搜边剪。合法的情况可能只有两千多种。根据题设再剪掉一批不合法的（比如元素个数不够的），就好了。

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