P9572题解

· · 题解

这题虽然提到了最长公共子序列但是和求最长公共子序列并无关系。

对于第一个输出，我们可以想到，由于可以拼接任意个数组 S ，对于 T 中的每一个元素，只要它在 S 中出现了，它就一定能成为最长公共子序列的一部分。设在 T 中出现但不在 S 中出现的元素个数为 t ，那么答案即为 m-t。

对于第二个输出，我们枚举 T 的每一个在 S 中出现了的元素，在 S 中找到该元素第一个大于上一个 T 元素在 S 出现位置的位置，如果找不到，说明需要再拼接一个数组 S。（这句话略绕，可以看代码理解）

意识到，上述的查找过程会被卡到 O(n)。

解决方法也很简单，注意到值域只有 10^6 ，因此我们可以开 10^6 个set或者vector来维护每一个元素在 S 中出现的位置，然后upper_bound即可。

我的代码中使用的是set。至于为什么不用vector，我会说set插入只需要打insert6个字母而vector插入需要打push_back8个字母加一个下划线吗。

代码也很简短：

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<set>

#define MAXN_INT 2147483647
#define MAXN_LL 9223372036854775807

#define MOD A_NUMBER
#define N 1000005

//#define x0 fuckcpp1
//#define y0 fuckcpp2

#define mp make_pair

using namespace std;
int n,m,c1,c2;
int len;
int s[N],t[N];
int temp;
bool vis[N];
set<int>q[N];//用set维护每一个元素在s中出现的位置，例如q[114514]这个set维护的就是114514这个元素在s中出现的所有下标
typedef set<int>::iterator IT;
int ans=1;
int last=0;
int main()
{
    scanf("%d%d%d%d",&n,&m,&c1,&c2);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&s[i]);
        q[s[i]].insert(i);
        vis[s[i]]=1;
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&temp);
        if(vis[temp])t[++len]=temp;//去除t中所有在s中未出现过的元素
    }
    m=len;
    last=*q[t[1]].begin();
    for(int i=2;i<=m;i++)
    {
        IT it=q[t[i]].upper_bound(last);
        if(it==q[t[i]].end())//找不到，需要再拼接一个s
        {
            ans++;
            last=*q[t[i]].begin();
        }
        else last=*it;//能找到
    }
    printf("%d %d",m*c1,ans*c2);
    return 0;
}