CH5702 Count The Repetitions

佚名 6年前 (2019-04-17) 随笔 1836人围观抢沙发百度已收录

题意

5702 Count The Repetitions 0x50「动态规划」例题

描述

定义 conn(s,n) 为 n 个字符串 s 首尾相接形成的字符串，例如：
conn("abc",2)="abcabc"
称字符串 a 能由字符串 b 生成，当且仅当从字符串 b 中删除某些字符后可以得到字符串 a。例如“abdbec”可以生成“abc”，但是“acbbe”不能生成“abc”。
给定两个字符串 s_1 和 s_2，以及两个整数 n_1 和 n_2，求一个最大的整数 m，满足conn(conn(s_2,n_2 ),m) 能由 conn(s_1,n_1) 生成。
s_1 和 s_2 长度不超过100，n_1 和 n_2 不大于 10^6。

输入格式

本题只有1个测试点，包含多组数据。每组数据由2行组成，第一行是s2,n2，第二行是s1,n1。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

输出格式

对于每组数据输出一行表示答案m。

样例输入

ab 2
acb 4
acb 1
acb 1
aa 1
aaa 3
baab 1
baba 11
aaaaa 1
aaa 20

样例输出

来源

https://leetcode.com/problems/count-the-repetitions/deｓｃｒｉｐｔion/

分析

发现可以求出最大的m'，满足conn(s2,m')能由conn(s1,n1)生成，那么答案m=m'/n2。

由于m'≤1e8不能直接F[i,j]表示从s1[i]开始要多少字符生成conn(s2,j)，观察到m'可以用二进制拆分，所以利用倍增优化。

设F[i,j]表示从s1[i]开始至少需要多少字符才能生成conn(s2,\(2^j\))。状态转移方程为：
\[ F[i,j]=F[i,j-1]+F[(i+F[i,j-1])\bmod |s_1|,j-1] \]
可以暴力预处理F[i,0]。总时间复杂度\(O(|s_2||s_1|^2+|s_1|\log(|s_1|*n_1/|s_2|))\)

代码

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
typedef long long ll;
using namespace std;

string s1,s2;
int n1,n2;
ll f[100][28];
void Count_the_Repetitions(){
    for(int i=0;i<s1.size();++i){
        int pos=i;
        f[i][0]=0;
        for(int j=0;j<s2.size();++j){
            int cnt=0;
            while(s1[pos]!=s2[j]){
                pos=(pos+1)%s1.size();
                if(++cnt>=s1.size()) return cout<<0<<endl,void();
            }
            pos=(pos+1)%s1.size(),f[i][0]+=cnt+1;
        }
    }
    for(int j=1;j<=27;++j)
        for(int i=0;i<s1.size();++i)
            f[i][j]=f[i][j-1]+f[(i+f[i][j-1])%s1.size()][j-1];
    ll m=0;
    for(int st=0;st<s1.size();++st){
        ll x=st,ans=0;
        for(int k=27;k>=0;--k)
            if(x+f[x%s1.size()][k]<=s1.size()*n1)
                x+=f[x%s1.size()][k],ans+=1<<k;
        m=max(m,ans);
    }
    cout<<m/n2<<endl;
}
int main(){
    ios::sync_with_stdio(0);
    while(cin>>s2>>n2>>s1>>n1) Count_the_Repetitions();
    return 0;
}