P9572 题解

Mr_Biantainne · 2023-08-19 19:08:40 · 题解

前言

第一次 AK Div3 比赛，写篇题解庆祝一下。

题意简述

有两个数组 s 和 t，现在要选一个 k，将 s 复制 k 次（设结果为 s'），求使得 t 与 s' 的最长公共子序列最长的最小的 k。

题意分析

一开始我想的是动态规划来做，但看数据非常多，必然不对。

后来就想到有一个策略：因为要使最长公共子序列最长，所以 t 里面的数只要 s 里面有，那一定会加上去。

策略的证明

假设 t 和 s' 的最长公共子序列为 a，而且 s 中有的元素没有在 a 中存在，则必然可以将 s' 增加一段，变为 s' + s，使得 t 与 s' + s 的最长公共子序列比 a 长。

继续分析

有了这个策略就好做了。先把 s 中所有的数字装入桶中。假设现在循环到 i，那么桶的下标是 s_i，装的内容是 i。

随后在 t 中寻找。先要准备一个记录当前下标的 idex（即当前 s' 的末尾元素下标），和一个记录最长公共子序列长度的 ans。

同样假设现在循环到 i：

• 如果桶里面没有 t_i，那就丢弃掉。
• 如果有 t_i，那就必然能够装进最长公共子序列中，因此把 ans 增加 1，随后在桶中找到第一个 > idex 的值，将 idex 更新为它。如果找到末尾也没有 > idex 的值，就需要新开一段，s' 变为 s' + s，随后将 idex 更新为桶中的第一个元素。

  优化与提示

  1. 可以发现，s 和 t 数组在计算完以后就不需要用了，因此不需要开数组。

2. 而且每个桶中的内容具有单调性，因此寻找第一个 > idex 的值的位置可以用二分。

3. 一开始就是第一段，所以要初始化 k 为 1。

   代码

   #include <iostream>
   #include <algorithm>
   #include <cmath>
   #include <vector>
   #define ll long long
   using namespace std;
   ll n, m, c1, c2, k = 1, ans, idex, s, t; //注意 k = 1
   vector <ll> v[1000005]; //桶
   int main()
   {
   cin >> n >> m >> c1 >> c2;
   for (ll i = 1; i <= n; i++) cin >> s, v[s].push_back(i); //把下标扔进桶中
   for (ll i = 1; i <= m; i++)
   {
       cin >> t;
       if (v[t].size() == 0) continue; //桶中无物，直接跳过
       ans++; //添加最长公共子序列的长度
       ll p = upper_bound(v[t].begin(), v[t].end(), idex) - v[t].begin(); //寻找第一个下标 > idex 的位置
       if (p == v[t].size()) //找到末尾也没有
       {
           k++; //新开一段
           idex = v[t][0]; //更新下标为第一个元素
       }
       else idex = v[t][p]; //更新下标为当前元素
   }
   cout << ans * c1 << " " << k * c2;
   }