首页 > 代码库 > Codeforces 314B(倍增)
Codeforces 314B(倍增)
题意:[a,b]表示将字符串a循环写b遍,[c,d]表示把字符串c循环写d遍,给定a,b,c,d,求一个最大的p,使得[[c,d],p]是[a,b]的子序列(注意不是子串,也就是不要求连续)。(b,d<=1e7,|a|,|c|<=100)
分析:如果找到了最大的s,使得[c,s]是[a,b]的子序列,那么结果显然就是p=s/d
考虑用一个字符串a去匹配[c,s],那么就相当于指针从下标i->下标j,如果i->j中包含了c的分界点,那么答案就要加上分界点个数
这看似还是不好处理,怎么办呢?
注意到[c,s]是由c重复得到的,所以i,j的取值一定是[0,len(c)-1]
所以可以预处理next[i],cnt[i],表示以c的第i个位置为起点,用一个字符串a进行匹配,next表示下一个匹配的位置,cnt表示该次匹配过程中遇到了多少个分界点
那么最后只需要枚举b次,将所有cnt相加就行
这样是O(b)的,也可以跑过
当然这种循环重复的,也可以很方便的用倍增搞,搞成O(logb)的
Codeforces 314B(倍增)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。