题解：P15650 [省选联考 2026] 摩卡串 / string

· · 题解

:::info[赛时思路，无法通过此题，正确做法在下文] 暴力日过去了。

观察一下大样例，发现答案可以表示为 abscd 的形式，s 为原串，令 abcd 的每个字母表示的串都为爆搜的小串，全都为 0，全都为 1，暴力枚举一下 abcd 即可通过所有大样例。

正确性不保证，但是很难卡，可以通过所有大样例。

时间复杂度应该是 O(n^4) 的。

赛时思路 qoj 爆成 75 分了，恭喜！ :::

题目链接

P15650 [省选联考 2026] 摩卡串 / string

解题思路 & 参考代码

注意到这题数据范围比较小而且我们还要支持字符串匹配状物，容易想到 dp。

刻画一下字典序比较，显然是前缀相同，不同的第一位满足 s 这一位为 1，t 这一位为 0 才能造成贡献。此后每加入一个字符贡献就会加上 1，称这个为一类贡献；若为严格前缀则为二类贡献。

由于我们 dp 的过程中是一个前缀匹配状物且需要考虑失配问题，因此我们建立一个 kmp 自动机后进行 dp：f_{i,j,k,0/1} 表示当前匹配到了 kmp 自动机的第 i 个节点，一类贡献为 j，总贡献为 k，是否包含 s（即是否走到过 kmp 自动机的第 n 个节点）时的最小长度。

具体可以使用 bfs 来实现，搜到终点就 break，因此我们不需要额外记录最小长度是多少。

考虑如何快速算出一类贡献，发现我们可以直接通过暴力跳 nxt 数组得到，于是我们预处理一下即可快速进行转移。

时间复杂度 O(nk^2)，由于如果有 x 次一类贡献的话总贡献就是 O(x^2) 级别的，于是第二维只需要开到 O(\sqrt{k}) 级别（一个字符至多失配后只造成一个贡献），时间复杂度为 O(nk\sqrt{k})。

:::info[参考代码]

ll n,m,pd;
string s;
ll nxt[210],dep[210];
ll pos[210][2],a[210][2];
struct node{
    short x,i,j,k;
    bool l;
};
struct nide{
    short i,j,k;
    bool l;
}E;
queue<nide>q;
node f[210][80][3010][2];
bool vis[210][80][3010][2];
vector<ll>ans;
void solve()
{
    while(!q.empty())
        q.pop();
    ans.clear();
    cin>>n>>m>>s;
    s=' '+s+'?';
    ll L=0;
    nxt[1]=0,dep[1]=n!=1;
    forl(i,2,n)
    {
        while(L && s[L+1]!=s[i])
            L=nxt[L];
        if(s[L+1]==s[i])
            L++;
        nxt[i]=L,dep[i]=dep[nxt[i]]+(i!=n);
    }
    forl(i,0,n)
        forl(j,0,1)
        {
            ll p=i,S=0;
            while(p && s[p+1]-'0'!=j)
                p=nxt[p];
            if(s[p+1]-'0'==j)
                p++;
            pos[i][j]=p;    
            p=i;
            while(p)
                S+=s[p+1]=='1',
                p=nxt[p];
            S+=s[1]=='1',
            a[i][j]=S;
        }
    forl(i,0,n)
        forl(j,0,79)
            forl(x,0,m)
                forl(y,0,1)
                    vis[i][j][x][y]=0;
    f[0][0][0][0]={0,0,0,0,0};
    vis[0][0][0][0]=1;
    q.push({0,0,0,0});
    pd=0;
    while(!q.empty())
    {
        nide now=q.front();
        q.pop();
        if(now.k==m && now.l)
        {
            pd=1,E=now;
            break;
        }
        forl(i,0,1)
        {
            nide nw;
            nw.i=pos[now.i][i];
            nw.j=now.j+a[now.i][i]*(i==0);
            nw.k=now.k+nw.j+dep[nw.i];
            nw.l=now.l|(nw.i==n);
            if(nw.k<=m && !vis[nw.i][nw.j][nw.k][nw.l])
                vis[nw.i][nw.j][nw.k][nw.l]=1,
                f[nw.i][nw.j][nw.k][nw.l]={i,now.i,now.j,now.k,now.l},
                q.push(nw);
        }
    }
    if(!pd)
    {
        cout<<"Impossible\n";
        return ;
    }
    while(E.i+E.j+E.k+E.l>0)
    {
        node now=f[E.i][E.j][E.k][E.l];
        ans.pb(now.x);
        E.i=now.i,E.j=now.j,E.k=now.k,E.l=now.l;
    }
    reverse(ans.begin(),ans.end());
    for(auto i:ans)
        cout<<i;
    cout<<endl;
}

:::