蒟蒻的理解
查看原帖
蒟蒻的理解
467906
Anyakwi楼主2022/10/3 10:22

之前一直卡在Q+Q能把a覆盖这个点上。

如果Q<1/2a|Q|<1/2|a|怎么办?也就是能被跳到的最短公共前后缀的长度都大于二分之一怎么办?

然后细细品了品,如果前后缀长度>1/2,那么一定有重叠的部分,把这部分记为b。b是后缀的前缀、前缀的后缀,同时因为前后缀相等,b也是前缀的前缀、后缀的后缀。那么前缀的前缀=后缀的后缀,还可以继续跳,直到前后缀长度<1/2,一定可以满足题意

2022/10/3 10:22
加载中...