P9572 Colorful Days♪

· · 题解

思路

Step0.骗分

显然，题目中的 c_1,c_2 就是为了送分，如果比赛中没有思路，倒是可以直接输出两个 0 先得到 2 分，聊胜于无。

Step1.暴力不出奇迹

显然第一个想到的是暴力，枚举 k，容易观察得出，若一次增加 k 而 LCS 不变，则再增加 k 也无用。可凭借这个结论暴力验证，然后得出答案。

但是非常显然，这样时间复杂度及其高，定然会 TLE。

Step2.观察性质

我们发现，如果 k 足够大，那么所有同时存在于数组 S,T 的数字都可以贡献答案，所以最大的 LCS 就是同时存在数组 S,T 的个数。

Step3.从模拟入手

想要直接找到最小 k 不是一件简单的事情，不如逐步模拟。

因为我们在 Step2 中得出结论，只要是同时存在于数组 S,T 的，都需要计算，所以我们可以遍历数组 T。

假设当前遍历到的数是 x。

如果 x 不在数组 S 中，则可以直接跳过，因为无论 k 多大，也没有任何用处。

如果 x 在数组 S 中，那么就可以贡献答案，如果前一个可贡献答案的数在数组 S 中的位置之后有 x 的话，那么不需要增加 k，如果没有的话，则需要增加一次 k，用新增加的一段中的 x 满足要求。

这样就完美地解决了 k 的问题。

Step4.代码写法

可以用 vector 储存每个数字在数组 S 中的位置。

用一个变量，储存上一个可贡献答案的数在数组 S 中的位置。

我们就只需要遍历 vector，找到位置之后的满足条件的坐标，如果找不到，就增加 k，并把变量赋值为该数字第一次出现的位置。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int n,m,c1,c2,s[1000005],t[1000005],res,k=1,p,cnt;
vector<int>v[1000005];
int main()
{
    scanf("%d%d%d%d",&n,&m,&c1,&c2);
    for(int i=1;i<=n;++i) scanf("%d",&s[i]),v[s[i]].push_back(i);
    for(int i=1;i<=m;++i) scanf("%d",&t[i]);
    for(int i=1;i<=m;++i)
    {
        if(!v[t[i]].size()) continue;//如果在S中不存在就直接跳过
        else
        {
            int flag=0;res++;//用flag标记是否找到位置
            for(int j=0;j<v[t[i]].size();++j) if(v[t[i]][j]>p){flag=1,p=v[t[i]][j];break;}//找到第一个大于p的位置
            if(!flag) k++,p=v[t[i]][0];//没找到就需要增加k了，记得赋值
        }
    }
    printf("%d %d",res*c1,k*c2);//别忘了乘以c1,c2
    return 0;
}

题外话

这个代码其实有个小问题，如果 LCS 为 0，那么非负整数 k 的最小值应该是 0。只不过因为太细节，加了可能会影响公平性，所以没加。

改代码也很简单，只需要判断 res 是不是 0 就好。这里不改是看看到时候会不会有人直接复制交（滑稽）。

Step5.进一步的优化

原本交了，但是被巨佬同学说了，我这个复杂度过了是因为数据水，所以我有屁颠屁颠地跑回来修改了。

显然如果数据构造合适，在查找位置的时候会被卡，所以考虑在查找优化时间复杂度，第一时间就想到是二分。绝对不是看到标签里有二分。

这样的话就容易了，只需要再写个二分查找就好了。

仅贴出部分代码（二分查找函数和调用部分的循环代码）

int find(int i,int x)
{
    int l=0,r=v[i].size()-1,mid,ans=-1;
    while(l<=r)
    {
        mid=l+r>>1;
        if(v[i][mid]>x) r=mid-1,ans=v[i][mid];
        else l=mid+1;
    }
    return ans;
}
/////////////
for(int i=1;i<=m;++i)
{
    if(!v[t[i]].size()) continue;
    else
    {
        int l=find(t[i],p);res++;
        if(l==-1) k++,p=v[t[i]][0];
        else p=l;
    }
}