ABC346F 题解

· · 题解

题意

给出整数 N 和两个字符串 S 和 T，将字符串 S 整体复制 N 次拼接起来得到母串，要求把 T 中每个字符分别复制 k 次再拼接起来得到的串为母串的子序列，求 k 的最大值。

思路

显然，若 k 合法，则 k-1 只需在 k 的取法上把原串中每个字符少取一个即可，因此具有单调性，可以二分答案。

现在需要写出check函数，考虑反过来做，对于一个 k 值求出需要复制 S 串的次数，再与 N 比较来check。

这样问题就成了求把 T 中每个字母按顺序分别取 k 个所需的 S 数量。为了求出这个数量，需要维护 S 串中各字母出现的后缀次数以及各字母出现的位置，具体看下边的代码实现吧。

这里要注意二分的上界，设 S 长度为 ls，T 长度为 lt，若 N 个 S 串被尽可能利用，最多能使 k 达到 \lfloor \frac{n\times ls}{lt}\rfloor，以此为二分上界能在不爆longlong的前提下通过。

代码

#include<iostream>
#include<vector>
#include<cstring>
#define int long long
using namespace std;
const int N=1e5+10;
const int K=26+10;
int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar();}
    return s*w;
}
int n,ls,lt;
char s[N],t[N];
int a[N][K];//a_i 记录s串中第i位到末尾 各个字母出现次数
vector <int> pos[K];//pos_i 记录s串中第i个字母出现的位置 
bool check(int x)
{
    if(x==0) return true;
    int cnt=0,lpos=ls;//cnt表示构成g(T,x)需要的s串个数，lpos表示上一个s串用到了第(lpos-1)位 
    for(int i=0;i<lt;i++)//构成每个字母 
    {
        int tc=t[i]-'a',ts=x;//需要的字符及数量 
        if(ts<=a[lpos][tc]) //如果上一个s串中剩余的tc足够
            lpos=pos[tc][a[0][tc]-a[lpos][tc]+ts-1]+1;//只需修改使用到的位置 
        else
        {
            ts-=a[lpos][tc];//先把上个串用完 
            cnt+=ts/a[0][tc];//再用完整的若干个串 
            ts%=a[0][tc];//还需要多少个该字母 
            if(ts) 
            {
                cnt++;
                lpos=pos[tc][ts-1]+1;
            }//如果还需要，就多用一个串并记录位置 
            else lpos=pos[tc][a[0][tc]-1]+1;//否则记录s串中该字母最后一次出现的位置即可 
        } 
    }
    return cnt<=n;//判断是否合法 
}
signed main()
{
    n=read();
    cin>>s>>t;
    ls=strlen(s),lt=strlen(t);
    for(int i=ls-1;i>=0;i--)
    {
        for(int j=0;j<26;j++) a[i][j]=a[i+1][j];
        a[i][s[i]-'a']++;
    }//倒序处理后缀a数组 
    for(int i=0;i<lt;i++) if(!a[0][t[i]-'a'])
    {
        cout<<0;
        return 0;
    }//这里特判：若t串中有s串没有的字符，则直接输出0
    //如果不判的话，在check函数里会除以0寄掉 
    for(int i=0;i<ls;i++) pos[s[i]-'a'].push_back(i);//正序记录各字母出现位置 
    int l=0,r=n*ls/lt,ans;//这里二分上界要注意 
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }//二分答案 
    cout<<ans;
    return 0;
}