P9572

Ryder00 · 2023-08-19 19:31:17 · 题解

题意比较清楚，不再阐述。

以下简要称输入的两数组为 A 数组和 B 数组。

思路

考虑第一问如何作答。

观察到，LCS（最长公共子序列）中的元素，必须都出现在 A 数组和 B 数组中。所以，只在一个数组中出现过的元素，就一定不会在 LCS 中出现。我们可以先把这些元素去除掉，得到新的 A 和 B。

由题意，A 数组可以复制无限次。这说明，A 一定可以通过复制操作，将 B 中所有的元素全都囊括在内。故第一问的答案为 B 与 A 的共同元素个数。

考虑第二问。

为了方便，我们将两数组“离散化”。用样例 2 举例子，此处的 A 数组和 B 数组都是经过第一问操作处理过的，看图理解：

处理完之后就好做了。我们发现，B 数组一定会作为一个子序列出现在答案数组中 。所以对于 A 数组中的每个元素，使用 vector 记录相同元素出现过的位置。枚举 B 数组中的每个元素，维护元素当前对应到 A 数组中的位置 now。使用 map 维护 A 中出现过多次的元素的位置在 vector 中的对应下标。如果下标大于元素出现过的次数，或者当前枚举元素的位置对应到 A 中小于 now，则说明可用元素都用完了，该复制这个数组了，答案加一。

使用 map 时要卡常数。

文字太抽象，建议看代码理解。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define db double
#define mkp make_pair
#define pb push_back
#define P pair<int,int>
#define _ 0
const int N=1e6+10,mod=1e9+7,MOD=1e9+123,inf=1e18;
int T=1,n,m,c1,c2,a[N],b[N],ans1,vis[N],val[N],lst[N],c[N],vis2[N];
vector<int> vec[N];
unordered_map<int,int> mp;
void solve(){
    cin>>n>>m>>c1>>c2;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        vis[a[i]]=1;
    }
    int ans1=m,cnt=0;
    for(int i=1;i<=m;i++){
        cin>>b[i];
        if(!vis[b[i]]) {
            ans1--;
            continue;
        }
        cnt++;
        if(!vis2[b[i]]) lst[b[i]]=cnt,vis2[b[i]]=1;
        val[cnt]=lst[b[i]];
    }
    m=cnt,cnt=0;
    for(int i=1;i<=n;i++){
        if(lst[a[i]]){
            a[++cnt]=lst[a[i]];
        }
    }
    n=cnt;
    for(int i=1;i<=n;i++){
        vec[a[i]].pb(i);
    }
    int ans2=0,now=0;
    for(int i=1;i<=m;i++){
        if(mp[val[i]]>=(int)vec[val[i]].size()){
            ans2++,mp.clear(),now=0;
        }
        int &mpp=mp[val[i]];
        while(vec[val[i]][mpp]<now&&mpp<(int)vec[val[i]].size()) mpp++;
        if(mp[val[i]]>=(int)vec[val[i]].size()){
            ans2++,mp.clear(),now=vec[val[i]][mp[val[i]]],mp[val[i]]++;
        }
        else{
            if(vec[val[i]][mp[val[i]]]>now){
                now=vec[val[i]][mp[val[i]]];
                mp[val[i]]++;
            }
            else ans2++,mp.clear(),now=vec[val[i]][mp[val[i]]],mp[val[i]]++;
        }
    }
    cout<<c1*ans1<<" "<<c2*(ans2+1);
}
signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(false),cin.tie(0);
    while(T--){
        solve();
    }
    return ~~(0^_^0);
}

好像代码也很丑陋呢。。