题解：CF1624E Masha-forgetful

· · 题解

题解

因为本题无需最小化操作次数，所以说我们可以考虑出构造一种通解。

第一个想法是能不能直接枚举去匹配，但是长度可能各种各样，如果直接做必然超时。

这时我们可以发掘一下性质，我们发现，一个长度为 4 的方案可以拆成 2+2，长度为 7 的方案可以拆成 2+2+3。所以我们发现，长度无论为多少，都可以由 2 与 3 的方案构成。这样问题就被简化了，可能的长度变成了 2 个。

接着我们可以设 dp_i 表示对于前缀长度为 i 的字符串是否合法。然后分讨长度为 2 和 3 的情况即可。

然后我们考虑如何输出方案。

我们在转移 dp 时，如果其合法，那么我们可以定义一个 last 数组表示当前下标的上一个是谁，同步维护一个数组 pre 表示当我们成功拼到第 i 位时，最后使用的那个子串来自哪里。子串来自哪里直接预处理即可。最后维护答案时，直接倒着跑一边，输出方案即可。

代码

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int l,r,id;
};
string s,a[1005];
node b[1005],c[1005],pre[1005],ans[1005];
int dp[1005],qwq[1005];
int get2(string &x,int p)
{
    return (x[p]-'0')*10+x[p+1]-'0';
}
int get3(string &x,int p)
{
    return (x[p]-'0')*100+(x[p+1]-'0')*10+x[p+2]-'0';
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=0;i<1000;i++)
            c[i] = b[i] = {0,0,0};
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            a[i] = '_'+a[i];
            for(int j=1;j<m;j++)
            {
                int x = get2(a[i],j);
                if(!b[x].id) b[x] = {j,j+1,i};
            }
            for(int j=1;j<m-1;j++)
            {
                int x = get3(a[i],j);
                if(!c[x].id) c[x] = {j,j+2,i};
            }
        }
        cin>>s;
        s = '_'+s;
        for(int i=0;i<=m;i++)
        {
            dp[i] = 0;
            qwq[i] = -1;
            pre[i] = {0,0,0};
        }
        dp[0] = 1;
        for(int i=0;i<=m;i++)
        {
            if(dp[i]==0) continue;
            if(i+2<=m)
            {
                int x = get2(s,i+1);
                if(b[x].id&&!dp[i+2])
                {
                    dp[i+2] = 1;
                    qwq[i+2] = i;
                    pre[i+2] = b[x];
                }
            }
            if(i+3<=m)
            {
                int x = get3(s,i+1);
                if(c[x].id&&dp[i+3]==0)
                {
                    dp[i+3] = 1;
                    qwq[i+3] = i;
                    pre[i+3] = c[x];
                }
            }
        }
        if(dp[m]==0)
        {
            printf("-1\n");
            continue;
        }
        int cnt = 0;
        int p = m;
        while(p>0)
        {
            ans[cnt++] = pre[p];
            p = qwq[p];
        }
        for(int i=0;i<cnt/2;i++) swap(ans[i],ans[cnt-1-i]);
        printf("%d\n",cnt);
        for(int i=0;i<cnt;i++) printf("%d %d %d\n",ans[i].l,ans[i].r,ans[i].id);
    }
}