2019 CCPC Qinhuangdao Onsite Contest

Problem A

Solved by Kilo_5723. 01:45:25 (+)

Problem B

Unsolved.

Problem C

Unsolved.

Problem D

Solved by Xiejiadong. 00:02:50 (+)

题意：判断 $\frac{1}{n}$ 是否是一个有限小数。

题解：显然 $n$ 只能是 $2$ 和 $5$ 的倍数。

Problem E

Solved by Weaver_zhu && Kilo_5723. 03:27:20 (+)

Problem F

Solved by Xiejiadong. 02:35:01 (+5)

题意：给出一个仙人掌，可以任意的删边，求有多少方案，使得删边以后是一个森林。

题解：很显然，对于一个环，只需要删除至少一条边，就会变回森林，所以如果一个环的大小为 $n$ ，方案有 $2^n-1$ 种。

如果有 $x$ 条边不属于任何一个环，对于这些边可以任意地删除，所以方案就有 $2^x$ 种。

问题就是统计仙人掌中所有环的大小。

可以跑出任意一个生成树，有一些边不属于这棵树的，显然这些边会属于一个环，这个环的大小可以通过这条边加到 lca 的距离得到。

重现赛一开始内存没开大，数据格式还是错的。 Wa 爆了。

Problem G

Upsolved by Kilo_5723. (-3)

Problem H

Unsolved.

Problem I

Solved by Weaver_zhu. 00:49:05 (+)

Problem J

Solved by Xiejiadong. 00:44:40 (+2)

题意：对于一个字符串的后缀，假设他的周期串长度是 $l$ ，他的长度是 $len$ ，那么他的价值等于 $a\times len-b\times l$ ，求所有后缀的最大价值。

题解：显然对于每一个后缀，肯定是 $l$ 越小越好。

也就是求每一个后缀的最小周期串的长度，这个可以直接用 kmp 求。

然后枚举每一个后缀，求最大的价值即可。

Problem K

Unsolved.

Problem L

Unsolved.