Difference between revisions of "2014-2015 Petrozavodsk Winter Training Camp, Contest.58 (Makoto rng 58 Soejima contest)"
(5 intermediate revisions by 2 users not shown) | |||
Line 4: | Line 4: | ||
Solved by kblack. 00:25 (+1) | Solved by kblack. 00:25 (+1) | ||
+ | |||
+ | 略带凉意的签到。 | ||
== Problem B == | == Problem B == | ||
Solved by ultmaster. 03:07 (+) | 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 == | == Problem C == | ||
Solved by ultmaster. 01:34 (+) | Solved by ultmaster. 01:34 (+) | ||
+ | |||
+ | 题意:给 5 个集合的大小,已知任意两个集合的交都不超过 1。求 5 个集合的并最小是多少。 | ||
+ | |||
+ | 题解:看起来很像是可以乱搞的题。然后就假了? | ||
+ | |||
+ | 由于数据范围很小,很自然地想到可以暴搜枚举所有 31 - 5 = 26 种交集有还是没有。里面还有很多情况是非法的,可以剪掉。边搜边剪。合法的情况可能只有两千多种。根据题设再剪掉一批不合法的(比如元素个数不够的),就好了。 | ||
== Problem D == | == Problem D == | ||
Solved by zerol. 02:39 (+1) | Solved by zerol. 02:39 (+1) | ||
+ | |||
+ | 题意:题面花里胡哨的。 | ||
+ | |||
+ | 题解:奇偶分别用双端队列维护,然后逐行考虑。先不考虑删除,就是把奇偶互换,然后首位按照行数的奇偶还要特判,再把删除的那些对交换。 | ||
== Problem G == | == Problem G == | ||
Solved by kblack. 03:49 (+1) | Solved by kblack. 03:49 (+1) | ||
+ | |||
+ | 题意:给一条简单折线,问能不能通过墙上一个小孔。 | ||
+ | |||
+ | 题解:等价于对于折线每个端点,都能找到一条直线使得所有之前和之后的点分立两侧,枚举点以后转一圈数一数。 | ||
== Problem J == | == Problem J == | ||
Solved by kblack. 00:53 (+) | 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})}$ 的系数,背个包乘一乘就好了。 |
Latest revision as of 16:25, 7 November 2018
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})}$ 的系数,背个包乘一乘就好了。