题解 CF2164D Copy String

· · 题解

题解 CF2164D Copy String

其他题

题意

给定字符串 s,t，令 s_0=s，你可以进行若干次操作，第 i 次操作得到 s_i，其中 s_{i,j} 可以从 s_{i-1,j} 和 s_{i-1,j-1} 中选一个（j=1 时显然不能选后者）。

试问能否用不超过 k_{\max} 次操作使得最后一次操作得到的 s_k=t，如果可以，求出最小的 k 并给出一组构造方案。

数据范围：多测，\sum nk_{\max}\le 10^6。

做法

容易想到一种直接匹配的方法：枚举 s_i 并维护指针 p 使其与 t 中各项匹配并记录每个 i 匹配到的 p（记作 r_i），这个过程中如果枚举到某个 i 时 p<i 则匹配失败（依照题意字符只能往右移动），匹配成功后若 \max\{r_i-i\}>k_{\max} 仍视为匹配失败，否则操作次数即为 \max\{r_i-i\}，依题意模拟即可。

但是这个东西跑样例 #5 会输出 -1。

10 3
vzvylxxmsy
vvvvvllxxx

原因是 t_0,t_1,\dots,t_4 全部匹配给了 s_0。

所以上述方法求出来的方案不是最优的。

于是考虑当当前 r_i-i=k_{\max} 时强行结束 s_i 的匹配。

然后会发现我把 k_{\max} 开大点它又炸了。

然后发现他是放 nk_{\max} 过的，所以直接从小到大枚举操作次数，然后用上上面强行结束匹配的思路，匹配完输出答案之前再确定一遍是否能够到达最终状态（有时只判 p<i 判不掉一些情况）即可。复杂度 O(nk_{\max})。

:::success[代码]

#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<fstream>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#include<cassert>
#define ll long long
#define lf double
#define ld long double
using namespace std;
ll T,n,k,l[1000010],r[1000010],lst[30];
string s,t;
bool work(ll now){
    ll p=0;
    bool flg=0;
    memset(lst,-1,sizeof(lst));
    for(int i=0;i<n;i++){
        if(p<i){
            flg=1;
            break;
        }
        l[i]=p;
        while(p<n&&t[p]==s[i]){
            if(p-1-i==now)break;
            p++;
        }
        r[i]=p-1;
    }
    if(flg){
        return false;
    }
    string tmp=s;
    for(int i=1;i<=now;i++){
        for(int j=0;j<n;j++){
            if(j+i<=r[j]){
                tmp[j+i]=s[j];
            }
        }
    }
    if(tmp!=t){
        return false;
    }
    cout<<now<<endl;
    tmp=s;
    for(int i=1;i<=now;i++){
        for(int j=0;j<n;j++){
            if(j+i<=r[j]){
                tmp[j+i]=s[j];
            }
        }
        cout<<tmp<<endl;
    }
    return true;
}
int main(){
    ios::sync_with_stdio(0);
    cin>>T;
    while(T--){
        cin>>n>>k>>s>>t;
        bool flg=0;
        for(int i=0;i<=k;i++){
            if(work(i)){
                flg=1;
                break;
            }
        }
        if(!flg){
            cout<<-1<<endl;
        }
    }
    return 0;
}

:::