自动搬运

查看原文

来自洛谷，原作者为

	船酱魔王 如花美眷，似水流年

搬运于2025-08-24 22:49:42，当前版本为作者最后更新于2023-05-15 22:09:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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$ 最小，并按照规定要求输出。

$1 \le n \le 10^6$，$1 \le m \le 10^6$，$1 \le S_i,T_i \le 10^6$。

分析

输出 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;
}

总结与评价

本题用到的算法较为基础，但是考察选手的思维能力。

个人认为下位绿。