P9572 「NnOI R2-T4」Colorful Days♪

· · 题解

题目链接

定义 A^i=A^{i-1}A 其实就是 i 个 A 数组拼接在一起。所以对于 k 我们需要求出最少几个 S 拼接在一起能够与 T 数组构成最长公共子序列，这里我们用一个 cnt 来维护。

不难发现，LCS(S^k,T) 最大时，就是 T 与 S 所有公共的元素都出现时。我们不妨用一个桶在输入时来记录 S 中元素是否出现，再用另一个动态数组来记录这个数每次出现的位置。在输入 T 时判断此数是否出现过即可，将他们存入一个 vector 中。

然后我们用 pre 来记录当先元素的下标，去枚举第 i 个公共元素，在它的数组中用 upper_bound 去查询第一个大于 pre 的位置，如果找不到就再增加一个 S，同时 cnt 增加 1，用这个数组中第一个元素去更新 pre。知道我们将所有公共元素遍历完。

此时 cnt\cdot c1 和 ans\cdot c2 即为答案。

附代码：

#include<bits/stdc++.h>
using namespace std;
const int N(1e6+5);
int read(){
    int x=0,f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+48);
}int s[N],t[N];
vector<int> v[N],z,b;bool pot[N];
int main(){
    z.push_back(1);
    int n=read(),m=read(),c1=read(),c2=read();int cnt=0;
    for(int i=1;i<=n;++i)s[i]=read(),pot[s[i]]=1,v[s[i]].push_back(i);
    for(int i=1;i<=m;++i){
        t[i]=read();
        if(pot[t[i]])z.push_back(t[i]),cnt++;
    }int pre=0,ans=1;
    for(int i=1;i<=cnt;++i){
        int k=upper_bound(v[z[i]].begin(),v[z[i]].end(),pre)-v[z[i]].begin();
        if(k==v[z[i]].size()) ++ans,pre=v[z[i]][0];
        else pre=v[z[i]][k];
    }
    cout<<cnt*c1<<' '<<ans*c2<<'\n';
    return 0;
}