CSAcademy Prefix Suffix Counting 题解

CSAcademy Prefix Suffix Counting 题解
- 题意
- 思路
- 做法
- 程序

题意

给你两个数字\(N\)和\(M\)，现在\(K\)表示\(M\)的位数。问你从\(1\)到\(N\)，有多少个数字满足\(M\)同时是它的前\(K\)个数字和后\(K\)个数字。

思路

我们现在假设\(N\)和\(M\)都是字符串，如果没有特别提及，都作为字符串处理。

假设有一个数字\(S\)大于等于\(1\)小于等于\(N\)，我们可以分类讨论它的情况：（同样\(S\)作为字符串处理）

\(S\)的长度大于等于\(2K\)，那么前缀和后缀不会互相影响，中间的空出的没填部分在满足这个数字的值小于等于\(N\)的情况下随便填。
\(S\)的长度小于\(2K\)，那么前缀和后缀会互相重叠，你需要保证它们不会互相冲突，也就是仍旧满足前后缀都是\(M\)。而且，你也没有可以自由地填进去的数字了。

做法

对于上文提到的情况，可以分别实现：

我们枚举当前这个串/数字的长度，假如它的总长度小于\(N\)的总长度，那么它一定小于\(N\)，中间的空当可以随便填。假如它的总长度等于\(N\)的长度，那么我们枚举某一位，在这一位前，所有的数字都和\(N\)中的一样，这一位的数字比\(N\)的这一位小了，那么后面的就随便填。特别地，有可能这一位在前\(K\)个数字中出现过了，那么中间的所有数位都随便填，或者，中间所有数位都填\(0\)时，当前的数字仍旧比\(N\)大，那么就没有合法方案。
同样的，枚举当前串/数字的长度，满足前后缀重叠部分相同这一条件需要快速判断，可以使用Z或者KMP等字符串匹配方法快速计算。

程序

同做法，使用Z匹配前后缀。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod=1000000007;

char s[1000005];//s表示题目中的数字N

char t[1000005];//t表示题目中的数字M

int n,m;//n, m分别表示题目中的N, M的长度

ll pw[1000005],ans;//pw[i]表示10的i次方对mod取模后的大小，ans表示最终答案

bool check(int emp){//check表示中间空出了emp个填0的数位的时候，前后缀是M的数字是否小于等于N，emp<0时，表示前后缀的M重叠了几个位置

    char *r=new char[n+1];

    memset(r,'0',n+1);

    memcpy(r+1+n-(m+emp+m),t+1,m);

    memcpy(r+1+n-m,t+1,m);//构造一个前后缀为M的数字，长度小于N时高位补零

    bool fl=false,va=true;

    for(int i=1;i<=n;i++){

        if(r[i]<s[i])fl=true;

        if(r[i]>s[i]&&!fl)va=false;

    }//判断大小关系（数学意义）

    delete[] r;

    return va;

}

int main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    pw[0]=1;

    for(int i=1;i<=1000000;i++)pw[i]=pw[i-1]*10%mod;//预处理

    cin>>s+1;

    n=strlen(s+1);

    cin>>t+1;

    m=strlen(t+1);

    if(check(-m))ans++;//单个M作为数字，这里其实可能会出锅，但数据中没有

    int *z=new int[m+1],l=1,r=1;

    z[1]=m;

    for(int i=2;i<=m;i++){

        z[i]=0;

        if(i>r){

            l=i;r=i-1;

            while(r<m&&t[r+1]==t[z[i]+1])r++,z[i]++;

        }else{

            if(i+z[i-l+1]<=r){

                z[i]=z[i-l+1];

            }else{

                l=i;

                z[i]=r-i+1;

                while(r<m&&t[r+1]==t[z[i]+1])r++,z[i]++;

            }

        }

        if(i+z[i]-1==m){

            if(m+m-z[i]<n||(m+m-z[i]==n&&check(-z[i])))ans++;

        }

    }

    delete[] z;//Z算法

    if(m+m<n||(m+m==n&&check(0)))ans++;//计算有数字形如M+M时是否合法

    for(int i=1;m+i+m<n;i++){//枚举空出了i个数字时

        ans=(ans+pw[i])%mod;

    }

    if(m+m<n&&check(n-m-m)){

        int emp=n-m-m;

        bool pref=false,suff=true,suf=false;//pref表示前K个数字是否已经比N小了，这样可以随便填，suff表示M是否小于等于N的K个数字，是就可以让中间的数字全部等于N对应数位

        for(int i=1;i<=m;i++){

            if(s[i]>t[i])pref=true;

            if(s[i+n-m]>t[i])suf=true;

            if(s[i+n-m]<t[i]&&!suf)suff=false;

        }

        if(pref)ans=(ans+pw[emp])%mod;//加上中间任意填的方案

        else{

            ans=(ans+suff)%mod;//加上suff的方案

            for(int i=m+1;i<=n-m;i++){

                ans=(ans+pw[n-m-i]*(s[i]-'0'))%mod;//加上当前位前面的数字和N相同，当前位小于N对应数位，后面随便填的方案

            }

        }

    }

    cout<<ans%mod<<endl;

    return 0;

}

巴特西

CSAcademy Prefix Suffix Counting 题解

CSAcademy Prefix Suffix Counting 题解

题意

思路

做法

程序

最新文章

热门文章