题解：P5640 【CSGRound2】逐梦者的初心

· · 题解

思路

关键在于想到怎么表示不合法的长度，用 bitset 维护反而是容易想到的。

设当前 |T|=k，对于任意满足 T_j=S_i 的位置对 (i,j)，由题意可知，其对应的不合法长度为：

l=k-j+i

定义不合法长度集合：

F_k=\{k-j+i\mid T_j=S_i,\ 1\le j\le k,\ 1\le i\le m\}

同时预处理每种字符的出现位置集合：

P_c=\{i\mid S_i=c,\ 1\le i\le m\}

考虑两种操作对 F_k 的影响。

尾插字符 c

原有字符的位置 j 不变，而 k 增加 1，因此原有的不合法长度全部增加 1。

对于新加入的字符，若 S_i=c，则产生的不合法长度为 i。 故：

F_{k+1}=\{l+1\mid l\in F_k\}\cup P_c

头插字符 c

原有字符的位置 j 与 k 同时增加 1，因此原有的不合法长度不变。

对于新加入的字符，若 S_i=c，则产生的不合法长度为 k+i。

故：

F_{k+1}=F_k\cup\{k+i\mid i\in P_c\}

维护

直接用布尔数组维护上述的操作复杂度是 O(n+m^2)。

bitset 一次处理约 64 位，可以将复杂度降至 O(n+\frac{m^2}{64})。

用 bitset f 和 pos[c] 分别表示集合 F_k 和 P_c，其中第 l-1 位对应长度 l。

集合平移对应左移，集合并对应按位或。

因此两种操作分别为：

// 尾插
f = (f << 1) | pos[c];

// 头插
f |= (pos[c] << k);

最终答案为：k-|F_k\cap[1,k]|

即 f 前 k 位中 1 的个数。

代码

#include <bits/stdc++.h>
using namespace std;
const int M = 33333;
int n, m;

bitset<M> pos[1001];
bitset<M> f, mask;

int main()
{
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        int s;
        cin >> s;
        if (i < m)
            pos[s][i] = 1;
    }

    int len = 0;
    while (m--)
    {
        int opt, ch;
        cin >> opt >> ch;
        if (opt == 0)
            f = (f << 1) | pos[ch];
        else if (opt == 1)
            f |= (pos[ch] << len);
        len++;

        mask <<= 1;
        mask.set(0);
        cout << len - (f & mask).count() << "\n";
    }

    return 0;
}