在新Blog上食用

重更Blog写道毒瘤题题解

CH5702 Count The Repetitions

题面

首先明确一个道理，即：
conn(conn(s2,n2),m)=conn(s2,n2*m)
[长得很像乘方运算]

所以可以求出一个最大的M，使得conn(s2,M)可以被conn(s1,n1)生成
然后⌊M/n2⌋即为答案

我们考虑将M拆分为：
M=2^k1+2^k2+2^k3+...+2^kn
于是效率就有了大幅的提升

再考虑使用DP。
定义状态f[i][j]
表示从s1[i]开始用多少个字符可以凑成conn(s2,2^j)
然后就是状态转移方程：

f[i][j]=f[i][j-1]+f[(f[i][j-1]+i)%s1.length()][j-1]

最后一步就是枚举s1起始位置，并统计最大的M值
这一步很简单，就不再赘述

下面讲细节问题：

1.<s1.length( ) <s2.length( )千万不要打错

2.当s1串中少了s2串中的一个字符时，特判输出0
然后千万不能return
因为是多组数据！

3.f数组的j那维要开到30
因为有10^6*100的数据，20不够！

好不容易听我耐心地讲完，该放代码了：

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;
int n1,n2;
string s1,s2;
long long f[101][31];
int main()
{
    bool bj=0;
    St:
    while(cin>>s2>>n2>>s1>>n1)
    {
        for(int i=0;i<s1.length();i++)
        {
            f[i][0]=0;
            int t=i;
            for(int j=0;j<s2.length();j++)
            {
                int cnt=0;
                while(s1[t]!=s2[j])
                {
                    t=(t+1)%s1.length();
                    if(++cnt>=s1.length())
                    {
                        printf("0\n");
                        goto St;
                    }
                }
                t=(t+1)%s1.length();
                f[i][0]+=cnt+1;
            }
        }
        for(int j=1;j<=30;j++)
            for(int i=0;i<s1.length();i++)
                f[i][j]=f[i][j-1]+f[(i+f[i][j-1])%s1.length()][j-1];
        long long m=0;
        for(int i=0;i<s1.length();i++)
        {
            long long x=i,ans=0;
            for(int j=30;j>=0;j--)
                if(x+f[x%s1.length()][j]<=s1.length()*n1) x+=f[x%s1.length()][j],ans+=(1<<j);
            m=max(m,ans);
        }
        printf("%lld\n",m/n2);
    }
    return 0;
}