P9572

聊机 · 2023-08-19 19:51:10 · 题解

快抢题解

rank1 赛时只用了 4 分钟，而我做了将近 20 分钟才写完，失败。

赛时我把几乎每一部分部分分都写了。

首先是 c2 为 0 的部分，对于在 T 中的数字，只要在 S 出现过，就可以是最长公共子序列的一部分，所以 17 分拿下。

for(int i=1;i<=n;i++) S[i]=qr(),vis[S[i]]=1;
for(int i=1;i<=m;i++) T[i]=qr();
for(int i=1;i<=m;i++)
    if(vis[T[i]]) ++cnt;
if(c2==0) {
    printf("%d %d",cnt*c1,0);
    return 0;
}

再看数据，有一部分 n，m 很小，所以可以暴力枚举 T 的每一个元素，然后在 S 里面找，如果找不到就把 k 加一，于是 40 分拿下。

if(m<=10000) {
    int j=1,k=1;
    for(int i=1;i<=m;i++) {
        if(!vis[T[i]]) continue;
        while(j<=n&&S[j]!=T[i]) ++j;
        if(j==n+1) {
            j=1;++k;
            while(j<=n&&S[j]!=T[i]) ++j;
        }
    }
    printf("%d %d",cnt*c1,k*c2);
    return 0;
}

到这里就离正解不远了，我们发现每次我们只需要在 S 中去寻找某一个值，那我们为何不预处理出来每一个值在 S 里的位置呢？

具体的：对每一个值开一个动态数组，然后按顺序差入它的位置，这样在枚举 T 中元素并寻找时可以直接二分查找出现的位置，100 分拿下。

for(int i=1;i<=n;i++) S[i]=qr(),vis[S[i]]=1,p[S[i]].push_back(i);
for(int i=1;i<=m;i++) T[i]=qr();

int j=1,k=1;
for(int i=1;i<=m;i++) {
    if(!vis[T[i]]) continue;
    if(p[T[i]][p[T[i]].size()-1]<j) j=1,++k;
    vector<int>::iterator x=lower_bound(p[T[i]].begin(),p[T[i]].end(),j);
    j=*x+1; ++cnt;
}
printf("%d %d",cnt*c1,k*c2);