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

· · 题解

我菜了/ll。

考虑贡献咋算，如果 t 的一个子串 h 满足 h 是 s 的前缀，那么会发生两种情况：

  2. 否则，贡献为 1。

那么我们把字典序比较转化为了前缀比较。

前缀匹配，考虑 KMP，设 f_{i,j,k,0/1} 表示当前匹配到了 KMP 自动机的 i 号结点上，造成了 j 次 1 类贡献，总贡献为 k，是否匹配出了 s（即是否到过了 n 号结点）。

考虑如何快速算出一类贡献，显然，我们可以通过不停跳 \text{next} 数组得到，同时我们还能进而直接得到失配时最终跳到了的结点。

上面的状态是 O(nk^2) 的，但你会发现 x 次一类贡献会带来 O(x^2) 的贡献。所以第二维是 O(\sqrt k) 的，O(nk^{1.5})。

#include<bits/stdc++.h>
using namespace std;

const int N=205,K=3005;
int n,k;
string s;
int nxt[N],dep[N];
int sp[N][2],ct[N][2];

struct node{
    short ch;
    short lp,lc,lk,lok;
};
struct nd{
    short p,c,lk,ok;
};
node dp[N][80][K][2];
bool vis[N][80][K][2];

void solve(){
    cin>>n>>k>>s;s=' '+s;
    nxt[1]=0;dep[1]=(n!=1);
    for(int i=2;i<=n;i++){
        nxt[i]=nxt[i-1];
        while(nxt[i]&&s[nxt[i]+1]!=s[i]) nxt[i]=nxt[nxt[i]];
        if(s[nxt[i]+1]==s[i]) nxt[i]++;
        dep[i]=dep[nxt[i]]+(i!=n);
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<=1;j++){
            int pos=i,cnt=0;
            while(pos&&s[pos+1]!=j+'0') pos=nxt[pos];
            if(s[pos+1]==j+'0') pos++;
            sp[i][j]=pos;
            pos=i;
            while(pos){
                cnt+=s[pos+1]=='1';
                pos=nxt[pos];
            }
            cnt+=s[1]=='1';
            ct[i][j]=cnt;
        }
    }
    memset(vis,0,sizeof vis);
    dp[0][0][0][0]={0,0,0,0,0};
    vis[0][0][0][0]=1;
    queue<nd> q;
    q.push({0,0,0,0});
    nd ed;bool fg=0;
    while(!q.empty()){
        nd f=q.front();q.pop();
        if(f.ok&&f.lk==k){
            ed=f;fg=1;
            break;
        } 
        for(int j=0;j<=1;j++){
            nd nxt;
            nxt.p=sp[f.p][j];
            nxt.c=f.c+(j==0)*ct[f.p][j];
            nxt.lk=f.lk+nxt.c+dep[nxt.p];
            nxt.ok=f.ok|(nxt.p==n);
            if(nxt.lk<=k&&!vis[nxt.p][nxt.c][nxt.lk][nxt.ok]){
                vis[nxt.p][nxt.c][nxt.lk][nxt.ok]=1;
                dp[nxt.p][nxt.c][nxt.lk][nxt.ok]={j,f.p,f.c,f.lk,f.ok};
                q.push(nxt);
            }
        }
    }
    if(!fg){
        cout<<"Impossible"<<endl;
        return;
    }
    string res;
    while(ed.p||ed.lk||ed.ok||ed.c){
        node pp=dp[ed.p][ed.c][ed.lk][ed.ok];
        res=(char)(pp.ch+'0')+res;
        ed.p=pp.lp;
        ed.c=pp.lc;
        ed.lk=pp.lk;
        ed.ok=pp.lok;
    }
    cout<<res<<endl;
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int _,T;cin>>_>>T;while(T--) solve();
    return 0;
}