首页 > 代码库 > 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(倍增)