P9572 题解

· · 题解

P9572 「NnOI R2-T4」Colorful Days♪

题目大意

定义 s^k 为 k 个数组 s 首尾相接。求数组 s^k 和数组 t 的最长公共子序列和满足最长下最小的 k。

解法

题目中，s 是可以变的，而 t 不变。也就是说，最长公共子序列的长度最大值是确定的，也就是 len_t。对于每一个 t_i，只要它存在于 s，我们都可以通过复制一遍 s 使它在最长公共子序列中出现。那么第一问就解决了，循环 t，只要 t_i 存在于 s 便将答案加一。

既然第一问是一个个找 t_i，我们想让复制的次数尽可能小，总不能每一个 t_i 都复制一遍 s。

所以用一个记录枚举 s 下标的变量，每次从这个下标开始在 s 中找 t_i。每当这个变量从 n 变到 1，意味着要复制一遍 s，将答案加一。

然而这是 O(n^2) 的，考虑优化。

可不可以跳跃的找 t_i 呢？不妨用 \text{vector} 预处理每个 t_i 在 s 中的每一个位置，这样找 t_i 时便可以遍历它每一个出现的位置，复杂度肯定降低不少。

再对这个过程优化，由于我们的预处理使得 \text{vector} 中对于一个 t_i 位置是连续的，考虑二分。二分至一个位置使得它在下标变量的右边并且距离它最近即可。

最终复杂度：O(m\log n)。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,c1,c2,s[N],t[N];
int ans,ans1=1,it=0,mp[N];
vector<int> pos[N];
int main(){
    scanf("%d%d%d%d",&n,&m,&c1,&c2);
    for(int i=1;i<=n;++i){
        scanf("%d",&s[i]),mp[s[i]]=1;//标记出现
        pos[s[i]].push_back(i);//预处理位置
    }
    for(int i=1;i<=m;++i) scanf("%d",&t[i]);
    for(int i=1;i<=m;++i){
        if(!mp[t[i]]) continue;
        ans++;
        if(pos[t[i]][pos[t[i]].size()-1]<=it){//最后一个位置也比当前枚举s的下标小，意味着必须得复制
            it=pos[t[i]][0];//复制完距离it最近的就是第一个位置
            ans1++;
            continue;
        }
        int l=0,r=pos[t[i]].size()-1;//二分
        while(l<=r){
            int mid=(l+r)>>1;
            if(pos[t[i]][mid]>it) r=mid-1;
            else l=mid+1;
        }
        it=pos[t[i]][l];
    }
    printf("%d %d",c1*ans,c2*ans1);
    return 0;
}