XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Ukraine

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