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

From EOJ Wiki
Jump to: navigation, search

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

题意:一块蛋糕上有 $k^2$ 根蜡烛,问能否横竖各切 $k-1$ 刀,将蛋糕分成 $k^2$ 个小块,每块上有一根蜡烛。

题解:通过统计每行上方的蜡烛数量数判断能否横切 $k-1$ 刀,再以同样的方法判断竖切的情况。

Problem E

Unsolved.

Problem F

Solved by Xiejiadong. 0:57 (+)

题意:对于一个字符串只能删除非回文串,对于一个字符串最多几次删除。

题解:上来 WA 了一片。于是开始耐心的讨论,讨论的结果是。

  • 如果一个串不是回文串,直接删掉。
  • 如果一个串是回文串,而且半段的子母全部相同,无解。
  • 如果一个串是回文串,且长度为奇数,半段间隔位相同,半段的倒数第二位和中间位相同,无解。
  • 其余情况均为两次删除。

Problem G

Unsolved. (-1)

Problem H

Solved by Kilo_5723. 1:33 (+1)

题意:$n$ 块间距为 $1$ 石头,$m$ 只青蛙在第一块石头上想到第 $n$ 块石头去,中间有 $k$ 块石头必须被恰好一只青蛙到达一次。第 $i$ 只青蛙在跳跃跨度超过 $d$ 时会消耗 $a_i$ 的能量,问最少消耗多少能量。

题解:先用单调队列求出能够选出多少条不相干的从起点到终点,每一步跨度都小于等于 $d$ 的路径,分类讨论:

1)路径条数 $p>0$:让消耗能量最多的至多 $p$ 只青蛙通过这些路径从起点到终点,易证如果这样的路径存在,不在路径中的石头可以加入任何一条路径而不破坏性质,那么剩下的青蛙只要一步跳到终点即可。

2)路径条数 $p=0$:让能量消耗最少的青蛙按顺序到达每一块石头并到达终点,其余的青蛙一步跳到终点。

注意特判起点到终点跨度不超过 $d$ 的情况。

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