P9572 Colorful Days♪ 题解报告

_XHY20180718_ · 2023-08-19 18:59:13 · 题解

题意简述：

给定 A、B 两个数组，让你求至少多少个 A 拼起来能达到与 B 有的最长公共子序列，以及最长公共子序列长度是多少。

思路：

既然要求最长公共子序列，那么有效元素一定是在 A 和 B 都出现过的元素，元素个数自然也是最长公共子序列的最大长度，然后我们便以 B 为基准，往后在 A 中找下一个符合的元素即可，这里可以用一个 vector 存各个 B 中的每个字符在 A 中分别在哪些地方出现过，然后在 vector 中二分查找大于上一次匹配到的位置，若匹配失败，则重新加上一个 A，然后继续进行匹配。

时间复杂度：O(n\log n+m)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,a[N],b[N],k=1;
vector<int>c[N];
char vis[N];
bool c1,c2;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>c1>>c2;
    for(int i=1; i<=n; ++i)cin>>a[i],vis[a[i]]=2;
    for(int i=1; i<=m; ++i){
        cin>>b[i];
        if(!vis[b[i]])--m,--i;
        else vis[b[i]]=1;
    }
    for(int i=1; i<=n; ++i)
        if(vis[a[i]]==1)c[a[i]].push_back(i);
    int lst=0;
    for(int i=1; i<=m; ++i){
        auto t=lower_bound(c[b[i]].begin(),c[b[i]].end(),lst+1);
        if(t==c[b[i]].end())++k,lst=c[b[i]][0];else lst=*t;
    }cout<<m*c1<<' '<<k*c2;
    return 0;
}