p9572题解

lraM41 · 2023-08-19 21:17:11 · 题解

赛场上看到T3是数学就弃了（哭。

开始打纯暴力，又红又紫又黑。

因为数组 A 可以复制无数遍，很容易想到答案就是 B 中在 A 中出现过的数的个数。由于下标单调递增，考虑二分。

对于这题我的做法：对于每个数 a 记录下它的下标（存在 vector 里），并且可以靠它来计算答案。接着记录下所有 B 在 A 中出现过的数（按输入顺序），对于这些数在 vector 的下标中二分，如果上一个数的下标在不大于该数的最后一个下标，便返回离上个下标最近的该数的下标，并且更新上一个下标， k 加一。具体还是看代码吧qwq。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int k,t,l,c1,c2;
int n,m,s,p[1000005],a[1000005],c,b[10000005];
vector<int> v[1000005];
signed main()
{
   cin>>n>>m>>c1>>c2;
   for(int i=1;i<=n;i++)
      cin>>a[i],p[a[i]]=1,v[a[i]].push_back(i);//记录下标。
   for(int i=1;i<=m;i++){
      cin>>c;
      if(p[c]) b[++s]=c;//记录 b 中 a 出现过的数。
   }
   if(!c1&&!c2) puts("0 0"),exit(0);//特判，下同。
   if(!c2)cout<<s<<" 0",exit(0);
    for(int i=1;i<=s;i++){
        k=upper_bound(v[b[i]].begin(),v[b[i]].end(),t)-v[b[i]].begin();//二分。
        if(k>=v[b[i]].size()) t=v[b[i]][0],l++;//没找到符合条件的下标，更新上一个下标， k 加一。
        else t=v[b[i]][k];//符合条件，更新上一个下标。
    }cout<<s<<' '<<l+1;//由于不复制数组时 k 就是一，因此最后要加一。
   return 0;
}