Difference between revisions of "2019 CCPC Qinhuangdao Onsite Contest"
Xiejiadong (talk | contribs) (Created page with "== Problem A == Solved by Kilo_5723. 01:45:25 (+) == Problem B == Unsolved. == Problem C == Unsolved. == Problem D == Solved by Xiejiadong. 00:02:50 (+) == Problem E =...") |
Xiejiadong (talk | contribs) |
||
(2 intermediate revisions by the same user not shown) | |||
Line 14: | Line 14: | ||
Solved by Xiejiadong. 00:02:50 (+) | Solved by Xiejiadong. 00:02:50 (+) | ||
+ | |||
+ | 题意:判断 $\frac{1}{n}$ 是否是一个有限小数。 | ||
+ | |||
+ | 题解:显然 $n$ 只能是 $2$ 和 $5$ 的倍数。 | ||
== Problem E == | == Problem E == | ||
Line 22: | Line 26: | ||
Solved by Xiejiadong. 02:35:01 (+5) | Solved by Xiejiadong. 02:35:01 (+5) | ||
+ | |||
+ | 题意:给出一个仙人掌,可以任意的删边,求有多少方案,使得删边以后是一个森林。 | ||
+ | |||
+ | 题解:很显然,对于一个环,只需要删除至少一条边,就会变回森林,所以如果一个环的大小为 $n$ ,方案有 $2^n-1$ 种。 | ||
+ | |||
+ | 如果有 $x$ 条边不属于任何一个环,对于这些边可以任意地删除,所以方案就有 $2^x$ 种。 | ||
+ | |||
+ | 问题就是统计仙人掌中所有环的大小。 | ||
+ | |||
+ | 可以跑出任意一个生成树,有一些边不属于这棵树的,显然这些边会属于一个环,这个环的大小可以通过这条边加到 lca 的距离得到。 | ||
+ | |||
+ | 重现赛一开始内存没开大,数据格式还是错的。 Wa 爆了。 | ||
== Problem G == | == Problem G == | ||
Line 38: | Line 54: | ||
Solved by Xiejiadong. 00:44:40 (+2) | Solved by Xiejiadong. 00:44:40 (+2) | ||
+ | |||
+ | 题意:对于一个字符串的后缀,假设他的周期串长度是 $l$ ,他的长度是 $len$ ,那么他的价值等于 $a\times len-b\times l$ ,求所有后缀的最大价值。 | ||
+ | |||
+ | 题解:显然对于每一个后缀,肯定是 $l$ 越小越好。 | ||
+ | |||
+ | 也就是求每一个后缀的最小周期串的长度,这个可以直接用 kmp 求。 | ||
+ | |||
+ | 然后枚举每一个后缀,求最大的价值即可。 | ||
== Problem K == | == Problem K == |
Latest revision as of 13:55, 28 September 2019
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.