Difference between revisions of "2019 CCPC Qinhuangdao Onsite Contest"

From EOJ Wiki
Jump to navigation Jump to search
 
(One intermediate revision by the same user not shown)
Line 26: 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 42: 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.