题解 P3500 【[POI2010]TES-Intelligence Test】

· · 题解

考虑暴力。对于每一个询问，我们都维护两个指针，分别扫描原串 a 和询问的串 b。如果 a[i]=b[j]，那么两个指针都往后扫，否则仅 a 的指针往后扫即可。

时间复杂度 O(nm)。

容易发现，其实没必要对于每一个询问的串都扫描一次 a，我们其实可以只扫描一次 a，对于 a 的每一位，分别去匹配每一个 b 即可。 具体一点，设一个串 b_i 的前 x 位都被扫完并比配了，我们就需要在 a 串中找到下一个 b_i[x+1] 的位置。

扫描 a 串，设现在扫描到第 i 位，b_i 串已经匹配完前 num_i 个位置了。那么所有 a_i=b_j[num_j] 的 b_j 第 num_j 位就匹配上了，对于这些 b_j，我们将 num_j 加一即可。

如何求出扫描到第 i 位时有哪些 b 串满足正好需要匹配 a_i 呢？用 \operatorname{vector} 即可。设 pos[x] 表示现在需要匹配数字 x 的 b 串有哪些，对于 a_i=k，我们将 pos[k] 里面的 b 全部往下匹配一个位置即可。

时间复杂度 O(n+\sum^{m}_{i=1}len[i])。其中 len[i] 表示第 i 个 b 串的长度。

#include <cstdio>
#include <vector>
#include <cctype>
#include <cstring>
#include <algorithm>
#define mp make_pair
using namespace std;

const int N=1000010;
int n,m,len,a[N],b[N],st[N];
bool ans[N];
vector<pair<int,int> > pos[N],cpy;
// pos[x][j].first 表示第 j 个需要匹配的数字为 x 的 b 串编号是几
// pos[x][j].second 表示第 j 个需要匹配的数字为 x 的 b 串 现在匹配到哪个位置了

int read()
{
    int d=0,f=1; char ch=getchar();
    while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
    while (isdigit(ch)) d=(d<<1)+(d<<3)+ch-48,ch=getchar();
    return f*d;
}

int main()
{
    n=read();
    for (int i=1;i<=n;i++)
        a[i]=read();
    m=read();
    for (int i=1,x;i<=m;i++)
    {
        x=read(); st[i]=len+1;  //省空间，将所有 b 串压缩在一个数组里
        for (int j=1;j<=x;j++)
            b[++len]=read();
        pos[b[st[i]]].push_back(mp(i,st[i]));
        // 一开始所有串都匹配到第一个位置
    }
    st[m+1]=len+1;
    for (int i=1;i<=n;i++)
    {
        cpy.clear();
        for (int j=0;j<pos[a[i]].size();j++)  // 枚举所有能匹配的串
        {
            int k=pos[a[i]][j].first,p=pos[a[i]][j].second;
            if (p+1==st[k+1]) ans[k]=1;  // 这个串已经全部匹配完了
                else cpy.push_back(mp(k,p+1));  //记录匹配下一位
        }
        pos[a[i]].clear();
        for (int j=0;j<cpy.size();j++)  //将上面匹配的串的下一位插入
        {
            int k=cpy[j].first,p=cpy[j].second;
            pos[b[p]].push_back(mp(k,p));
        }
    }
    for (int i=1;i<=m;i++)
        if (ans[i]) printf("TAK\n");
            else printf("NIE\n");
    return 0;
}