2019 Multi-University,HDU Day 8
Problem A
Upsolved by Kilo_5723.
题意:给定一个
Problem B
Unsolved.
Problem C
Solved by Weaver_zhu. 04:20:32 (+3)
Problem D
Solved by Xiejiadong. 03:50:43 (+)
题意:要求不重不漏的走完 $n\times m$ 的所有格子,每一次的步长必须满足 $>1$ 且 $<3$ 。
题解:对于 $n>m$ 的 swap 一下,我们就只需要处理 $n\le m$ 的情况。
显然,$n<2$ 或者 $m<3$ 的时候无解,有一个坑点是 $n=1,m=1$ 的时候有解。
分两部分进行。
第一次从最后一行进行到第三行,偶数行走 $2,4,6,\cdots $ ,奇数行走 $\cdots 5,3,1$ ,在行与行交接的地方,显然步长为 $\sqrt{2}$ ,满足要求;
然后直接走到 $(1,1)$ ,在继续走第二行的偶数位置,返回第一行走奇数位置,在 $(1,3)$ 处结束;
从 $(2,1)$ 出发,步长 $\sqrt{5}$ ;
依次走前两行剩下的位置 $(1,2),(2,3),(3,4),\cdots $ ,每次步长都是 $\sqrt{2}$ ;
剩下的,奇数行从大到小走偶数位置,偶数行从小到大走奇数位置就好了。
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)$ ,向左的就是在反串上类似的求。
F0RE1GNERS 的 SA 板子狂 TLE 不止,被演了 2h 。
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 (+)