Colorful Days♪ 题解
船酱魔王
·
·
题解
Colorful Days♪ 官方题解
题意回顾
给定长度为 n 的数组 S 和长度为 m 的数组 T 。
定义 AB 为 A 数组后拼接 B 数组，定义 A^{0}=\{\} （即空数组），\forall i \in \mathbb{N^+} ，有 A^{i}=A^{i-1}A 。
定义 \operatorname{LCS}(A,B) 为 A 数组和 B 数组的最长公共子序列长度。
求出 i \in \mathbb{N} 使得 \operatorname{LCS}(S^i,T) 取到最大，在此基础上 i 最小，并按照规定要求输出。
## 分析
输出 ```0 0``` 可得 2 分。
解决第一问（即 sub4）可再得 15 分，先考虑第一问解法，即不择手段地构造最长 $ \operatorname{LCS} $。
可以发现，当一个数不在 $ S $ 中出现，他一定不会存在在 $ \operatorname{LCS} $ 中。
设有 $ m' $ 个 $ T $ 的位置使得该位置数字在 $ S $ 中出现，记为 $ T $ 的合法位置，则复制 $ S $，复制 $ m' $ 次。可以在每次 $ S $ 循环一遍时，第 $ i $ 次可以选出第 $ i $ 个 $ T $ 的合法位置。
因此，第一问答案即为 $ m' $。
我们记 $ T' $ 为将 $ T $ 中合法位置依次串联组成的新数组。
第二问即要求在 $ S $ 的不断重复中找到 $ T' $ 作为子序列。
可以贪心的按照 $ T' $ 中的数依次找，每次找到这个数在上一个数出现后第一次出现在 $ S $ 的不断循环中的位置。
每次暴力去找的时间复杂度最坏是 $ O(n) $ 的，因为捆绑了测试点且数据经过特殊构造只能拿到 sub2~3 的分数。因此考虑快速去找。
我们开辟动态数组 $ g $, $ g_i $ 表示数字 $ i $ 在 $ S $ 中的出现的所有位置。
维护变量 $ sc,pos $ 每次找一个位置之后的字符时只需要在新字符的数组中二分大于 $ pos $（当前位置）的出现位置，如果找不到将 $ sc $ 加一，$ pos $ 更新为新字符第一次的出现位置。
时间复杂度 $ O(m \log n) $。
## AC 代码
```
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e6 + 5;
int n, m, c1, c2;
int s[N];
int t[N];
vector<int> g[N];
int findx(int p, int val) {
int l, r, mid;
l = -1;
r = g[p].size();
while(l + 1 < r) {
mid = (l + r) >> 1;
if(g[p][mid] > val) {
r = mid;
} else {
l = mid;
}
}
return r;
}
bool vis[N];
int main() {
scanf("%d%d%d%d", &n, &m, &c1, &c2);
for(int i = 1; i <= n; i++) {
scanf("%d", &s[i]);
vis[s[i]] = 1;
}
for(int i = 1; i <= m; i++) {
scanf("%d", &t[i]);
}
for(int i = 1; i <= m; i++) {
if(!vis[t[i]]) {
t[i] = -1;
}
}
int m1 = m;
m = 0;
for(int i = 1; i <= m1; i++) {
if(t[i] != -1) {
m++;
t[m] = t[i];
}
}
if(m == 0) {
printf("0 0\n");
return 0;
}
for(int i = 1; i <= n; i++) {
g[s[i]].push_back(i);
}
int sc = 1;
int pos = g[t[1]][0];
for(int i = 2; i <= m; i++) {
pos = findx(t[i], pos);
if(pos == g[t[i]].size()) {
pos = g[t[i]][0];
sc++;
} else {
pos = g[t[i]][pos];
}
}
printf("%d %d\n", m * c1, sc * c2);
return 0;
}
```
## 总结与评价
本题用到的算法较为基础，但是考察选手的思维能力。
个人认为下位绿。