Difference between revisions of "2019 Multi-University,HDU Day 8"

From EOJ Wiki
Jump to navigation Jump to search
Line 27: Line 27:
 
考虑枚举 $x$ ,每一次从一个位置 $i$ 开始向两边拓展,为了保证不重不漏,向前拓展的长度不能超过 $x$ ,每一次拓展的位置 $i$ 一定要与前一次距离至少 $x$ 。
 
考虑枚举 $x$ ,每一次从一个位置 $i$ 开始向两边拓展,为了保证不重不漏,向前拓展的长度不能超过 $x$ ,每一次拓展的位置 $i$ 一定要与前一次距离至少 $x$ 。
  
这样直接枚举的复杂度是 $O(\frac{|s|}{1}+\frac{|s|}{2}+cdots \frac{|s|}{|s|/k})$ ,复杂度近似 $O(nlogn)$ 。
+
这样直接枚举的复杂度是 $O(\frac{|s|}{1}+\frac{|s|}{2}+\cdots \frac{|s|}{|s|/k})$ ,复杂度近似 $O(nlogn)$ 。
  
 
向右最多的拓展长度,显然就是求 $lcp(i,i+x)$ ,向左的就是在反串上类似的求。
 
向右最多的拓展长度,显然就是求 $lcp(i,i+x)$ ,向左的就是在反串上类似的求。

Revision as of 10:50, 14 August 2019

Problem A

Unsolved.

Problem B

Unsolved.

Problem C

Solved by Weaver_zhu. 04:20:32 (+3)

Problem D

Solved by Xiejiadong. 03:50:43 (+)

Problem E

Solved by Xiejiadong. 02:55:46 (+2)

题意:求字符串中有多少子串满足均分成 $k$ 段以后,每一个子段都相同。

题解:如果一个字符串是最短循环节长度为 $x$ ,长度为 $len$ ,显然这一段的答案就是 $len-kx+1$ 。

所以我们只要找到所有的长度 $\ge kx$ 的循环串即可。

考虑枚举 $x$ ,每一次从一个位置 $i$ 开始向两边拓展,为了保证不重不漏,向前拓展的长度不能超过 $x$ ,每一次拓展的位置 $i$ 一定要与前一次距离至少 $x$ 。

这样直接枚举的复杂度是 $O(\frac{|s|}{1}+\frac{|s|}{2}+\cdots \frac{|s|}{|s|/k})$ ,复杂度近似 $O(nlogn)$ 。

向右最多的拓展长度,显然就是求 $lcp(i,i+x)$ ,向左的就是在反串上类似的求。

Problem F

Solved by Kilo_5723 && Xiejiadong. 03:06:21 (+2)

Problem G

Unsolved.

Problem H

Solved by Kilo_5723. 04:26:28 (+2)

Problem I

Solved by Kilo_5723. 01:38:27 (+2)

Problem J

Solved by Xiejiadong. 00:07:46 (+)

Problem K

Solved by Kilo_5723. 00:26:03 (+)