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

· · 题解

我已急哭。

只考虑前 x 位，对于 1 \le l \le x，如果 t_lt_{l + 1} \dots t_x 小于 s 且不是 s 的前缀，那么 t_lt_{l + 1} \dots t_y 小于 s 对任意 y \ge x 都成立。这个对大于号也成立。

考虑剩下的 t_lt_{l + 1}\dots t_x 是 s 前缀的情况，记录最长的这样的 t 的子串 t_{l_0}t_{l_0 + 1}\dots t_x，发现其它这样的串都要满足：t_lt_{l + 1}\dots t_x 是它的 border。

建立 KMP 自动机，设 f_{i, j, k, 0/1} 表示，当前 x - l_0 + 1 = i，有 j 个满足 t_lt_{l + 1} \dots t_x 小于 s 且不是 s 的前缀的 l，当前有 k 个 t 的子串小于 s，转移 O(1)，状态数 O(nk^2)。

显然 j 是 O(\sqrt k) 级别，所以复杂度是 O(nk^{1.5})。

代码进行了卡空间，实际上 B 只到约 80。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline ll Read() {
    int sig = 1; ll x = 0; char c = getchar();
    while(!isdigit(c)) { if(c == '-') sig = -1; c = getchar(); }
    while(isdigit(c)) x = (x << 3) + (x << 1) + (c ^ '0'), c = getchar();
    return x * sig;
}
void Write(ll x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) Write(x / 10);
    putchar(x % 10 + 48);
}
bool ST;
const int N = 205, K = 3005;
int n, k, a[N], b[N], fail[N], cnt[N], nxt[2][N], addlst[N];
bool Comp(int l, int r) {
    int i;
    for(i = l; i <= min(r, l + n - 1); i++) if(b[i] != a[i - l + 1]) return b[i] < a[i - l + 1];
    return false;
}
int Calc(int len) {
    int i = len - 1, cnt = Comp(len, len);
    while(i) {
        if(Comp(len - i, len)) cnt++;
        i = fail[i];
    }
    return cnt;
}
void Init() {
    int i, j; fail[1] = 0, cnt[1] = 1;
    for(i = 2, j = 0; i <= n; i++) {
        while(j && a[j + 1] != a[i]) j = fail[j];
        if(a[j + 1] == a[i]) j++;
        fail[i] = j, cnt[i] = cnt[j] + 1;
    }
    nxt[a[1]][0] = 1, nxt[a[1] ^ 1][0] = 0;
    b[1] = 0, addlst[0] = Calc(1);
    for(i = 1; i <= n; i++) {
        b[i] = a[i];
        nxt[0][i] = (i < n && !a[i + 1]) ? i + 1 : nxt[0][fail[i]];
        b[i + 1] = 0, addlst[i] = Calc(i + 1);
        nxt[1][i] = (i < n && a[i + 1]) ? i + 1 : nxt[1][fail[i]];
    }
    // for(i = 0; i <= n; i++) cerr << fail[i] << ' ' << addlst[i] << endl;
    // cerr << endl;
}
namespace Sub2 {
    const short N = 205, B = 305, K = 2005, inf = 60000;
    short f[2][N][B][K];
    struct Status {
        short suf, cnt;
        unsigned char match;
        bool full;
        Status() : match(0), suf(0), cnt(0), full(false) {}
        Status(unsigned char _match, short _suf, short _cnt, bool _full) : 
            match(_match), suf(_suf), cnt(_cnt), full(_full) {}
    }st[2][N][B][K];
    void DP() {
        int i, j, x, y; queue<Status> q;
        for(i = 0; i < 2; i++) for(j = 0; j <= n; j++) for(x = 0; x < B; x++) for(y = 0; y <= k; y++) {
            f[i][j][x][y] = (1 << 13) - 1;
        }
        f[0][0][0][0] = (1 << 13), q.emplace(0, 0, 0, 0);
        while(!q.empty()) {
            Status t = q.front(), _t; q.pop();
            // cerr << "f " << t.full << ' ' << t.cnt << ' ' << t.suf << ' ' << t.match << ' ';
            // cerr << f[t.full][t.match][t.suf][t.cnt] << endl;
            if(t.full && t.cnt == k) {
                vector<bool> vec;
                while(t.full || t.cnt || t.suf || t.match) {
                    vec.emplace_back(f[t.full][t.match][t.suf][t.cnt] >> 14);
                    t = st[t.full][t.match][t.suf][t.cnt];
                }
                reverse(vec.begin(), vec.end());
                for(auto v : vec) putchar(v + 48);
                putchar('\n'); return ;
            }
            _t.match = nxt[0][t.match], _t.suf = t.suf + addlst[t.match];
            _t.cnt = t.cnt + _t.suf + cnt[_t.match], _t.full = t.full;
            if(_t.match == n) _t.cnt--, _t.full = true;
                // cerr << " -> " << _t.full << ' ' << _t.cnt << ' ' << _t.suf << ' ' << _t.match << endl;
            if(_t.cnt <= k && !((f[_t.full][_t.match][_t.suf][_t.cnt] >> 13) & 1)) {
                q.emplace(_t), f[_t.full][_t.match][_t.suf][_t.cnt] = 1 << 13;
                st[_t.full][_t.match][_t.suf][_t.cnt] = t;
                f[_t.full][_t.match][_t.suf][_t.cnt] |= (f[t.full][t.match][t.suf][t.cnt] & ((1 << 13) - 1) + 1);
            }
            _t.match = nxt[1][t.match], _t.suf = t.suf;
            _t.cnt = t.cnt + _t.suf + cnt[_t.match], _t.full = t.full;
            if(_t.match == n) _t.cnt--, _t.full = true;
                // cerr << " -> " << _t.full << ' ' << _t.cnt << ' ' << _t.suf << ' ' << _t.match << endl;
            if(_t.cnt <= k && !((f[_t.full][_t.match][_t.suf][_t.cnt] >> 13) & 1)) {
                q.emplace(_t), f[_t.full][_t.match][_t.suf][_t.cnt] = (1 << 14) | (1 << 13);
                st[_t.full][_t.match][_t.suf][_t.cnt] = t;
                f[_t.full][_t.match][_t.suf][_t.cnt] |= (f[t.full][t.match][t.suf][t.cnt] & ((1 << 13) - 1) + 1);
            }
        }
        printf("Impossible\n");
    }
}
int C;
void Solve() {
    int i; n = Read(), k = Read();
    char c = getchar();
    while(!isdigit(c)) c = getchar();
    bool b0 = true;
    for(i = 1; i <= n; i++) a[i] = c ^ '0', b0 &= !a[i], c = getchar();
    Init(), Sub2::DP();
}
bool ED;
int main() {
    // freopen("string.in", "r", stdin), freopen("string.out", "w", stdout);
    C = Read();
    int T = Read();
    while(T--) Solve();
}