Difference between revisions of "XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Ukraine"
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
Line 54: | Line 54: | ||
== Problem J == | == Problem J == | ||
− | + | Upsolved by Kilo_5723 && Xiejiadong. (-17) | |
+ | |||
+ | 题意:随机一个 $10^7$ 个点和 $10^7$ 条边的森林,求至少包含一半最小生成森林边的集合。 | ||
+ | |||
+ | 题解:我们只保留每个点连出去的最小边,显然,这至少包含一半最小生成森林边,而且一定是最小生成森林边的子集合。 | ||
== Problem K == | == Problem K == |
Revision as of 13:25, 29 May 2019
Problem A
Unsolved.
Problem B
Solved by Weaver_zhu. 0:21 (+)
Problem C
Solved by Xiejiadong && Kilo_5723. 2:56 (+)
题意:求一个价值最大的子序列,一个子序列的价值是 $\frac{len_t^2}{c_t}$ , $len_t^2$ 表示子序列的长度, $c_t$ 表示子序列的循环节长度。
题解:因为只有三种子母,所以必有其中一种子母的数量 $\ge \frac{n}{3}$ ,对于所有这种子母组成的组序列,他的价值 $\ge \frac{len^2}{9}$ ,所以我们只需要枚举分母 $\le 8$ 的。
显然分母 $\le 8$ 的不多,对于确定的循环节,枚举满足要求的最长子序列即可,枚举子序列的复杂度是 $O(n)$ 的。
Problem D
Solved by Kilo_5723. 0:39(+)
Problem E
Unsolved.
Problem F
Solved by Xiejiadong. 0:57 (+)
题意:对于一个字符串只能删除非回文串,对于一个字符串最多几次删除。
题解:上来 WA 了一片。于是开始耐心的讨论,讨论的结果是。
- 如果一个串不是回文串,直接删掉。
- 如果一个串是回文串,而且半段的子母全部相同,无解。
- 如果一个串是回文串,且长度为奇数,半段间隔位相同,半段的倒数第二位和中间位相同,无解。
- 其余情况均为两次删除。
Problem G
Unsolved. (-1)
Problem H
Solved by Kilo_5723. 1:33 (+1)
Problem I
Unsolved.
Problem J
Upsolved by Kilo_5723 && Xiejiadong. (-17)
题意:随机一个 $10^7$ 个点和 $10^7$ 条边的森林,求至少包含一半最小生成森林边的集合。
题解:我们只保留每个点连出去的最小边,显然,这至少包含一半最小生成森林边,而且一定是最小生成森林边的子集合。
Problem K
Unsolved.
Problem L
Solved by Weaver_zhu. 2:03 (+)