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

tiger2005 · 2026-03-07 18:30:17 · 题解

本文主要介绍不依赖于 bitset 的 \mathcal{O} (\sum n k \sqrt k) 做法。

不妨研究一下“摩卡串”对于“字典序小于 s 的子串”的限制等价于什么。考虑 s = \texttt{11010}，列出字典序比这个字符串小的所有字符串，不难发现它们恰能被如下正则表达式之一匹配：

1
11
110
1101

0[01]*
10[01]*
1100[01]*

不难发现，上面的字符串分为两种：

• 第一种是 s 的所有真前缀；
• 第二种是取所有 s 的前缀，满足最后一个位置是 \texttt{1}，随后将其换成 \texttt{0}，并允许在后面继续添加任意 01 字符串。

因此，考虑不断向字符串 t 的末尾追加字符的过程，在追加一个新字符时，根据增量思想应该只考虑 t 的所有新的后缀。此时：

• 如果某个新的后缀与第一种字符串匹配，则自然会多一个字典序小于 s 的子串；
• 如果某个新的后缀与第二种字符串匹配，则除了在这个位置产生贡献之外，它也会在之后每次追加字符时产生贡献。

接下来分别研究上述两种情况的性质：

因此，匹配过程中的状态为：

• 第二种情况总共触发了多少次（也等价于现在有多少个后缀小于 s）；

使用 BFS 搜索从 (0, 0, 0, 0) 状态到达 (\circ, \circ, k, 1) 状态的最短路即可。此时的时间复杂度为 \mathcal{O} (\sum n k^2)。

接下来需要注意到：在第二种情况触发时，实际上对应的是一次失配，而这次失配之前还包含了多次匹配，也就是第一种情况触发时的情况。可以证明，如果第二种情况触发了 c 次，则字典序小于 s 的子串个数不小于 \frac{c (c + 1)} 2。因此，状态的第二维实际上不会超过 \mathcal{O}(\sqrt k)。

在上述讨论之后，该做法的时间复杂度降低至 \mathcal{O} (\sum n k \sqrt k)，可以通过。

::::info[代码]

// https://qoj.ac/submission/2105504

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>

using namespace std;

int t, n, k;
char s[210];

int nxt[210];
int mtch[210][2], accu[210][2];
int dep[210];

const int MAX_P = 200;
const int MAX_C = 80;

/*
  状态：
    p - t 的后缀匹配 s 的前缀的最长长度
    c - t 加 0 时对应的失配总数
  cnt - 字典序比 s 小的子串数量
   ok - t 是否存在 s 作为子串
*/

struct Transition {
  short ch;
  short lp, lc, lk, lok;
};

Transition dp[MAX_P + 1][MAX_C + 1][3010][2];
bool vis[MAX_P + 1][MAX_C + 1][3010][2];

queue<tuple<short, short, short, short>> que;

int main() {
  int _;
  scanf("%d%d", &_, &t);
  while (t --) {
    scanf("%d %d %s", &n, &k, s + 1);

    nxt[1] = 0;
    dep[1] = (n != 1);
    for (int i = 2, j = 0; i <= n; i ++) {
      while (j != 0 && s[i] != s[j + 1])
        j = nxt[j];
      if (s[i] == s[j + 1])
        ++ j;
      nxt[i] = j;
      dep[i] = dep[j] + (i != n);
    }

    for (int i = 0; i <= n; i ++) {
      for (int j: {0, 1}) {
        int pos = i, cnt = 0;
        while (pos != 0 && s[pos + 1] != j + '0')
          pos = nxt[pos];
        if (s[pos + 1] == j + '0')
          ++ pos;
        mtch[i][j] = pos;

        pos = i;
        while (pos != 0)
          cnt += s[pos + 1] == '1', pos = nxt[pos];
        cnt += s[1] == '1';
        accu[i][j] = cnt;
      }
    }

    memset(vis, 0, sizeof vis);
    dp[0][0][0][0] = {0, 0, 0, 0, 0};
    vis[0][0][0][0] = true;

    while (!que.empty()) que.pop();
    que.push({0, 0, 0, 0});

    bool flg = false;
    tuple<int, int, int, int> st;
    while (!que.empty()) {
      auto [p, c, lk, ok] = que.front();
      que.pop();
      if (ok && (lk == k)) {
        flg = true;
        st = {p, c, lk, ok};
        break;
      }
      for (int ch : {0, 1}) {
        int np = mtch[p][ch];
        int nc = c + (ch == 0) * accu[p][ch];
        int nk = lk + nc + dep[np];
        int nok = ok || (np == n);
        if (nk <= k) {
          if (!vis[np][nc][nk][nok]) {
            vis[np][nc][nk][nok] = true;
            dp[np][nc][nk][nok] = {
              ch, p, c, lk, ok
            };
            que.push({np, nc, nk, nok});
          }
        }
      }
    }

    if (!flg) {
      puts("Impossible");
      continue;
    }

    auto [p, c, lk, ok] = st;
    string str = "";
    while (p != 0 || c != 0 || lk != 0 || ok != 0) {
      auto [ch, np, nc, nlk, nok] = dp[p][c][lk][ok];
      str = char('0' + ch) + str;
      p = np; c = nc; lk = nlk; ok = nok;
    }

    puts(str.c_str());
  }
  return 0;
}

::::