UOJ Logo Universal Online Judge

UOJ

#902. 【IOI2024】象形文字序列

附件下载 统计

题目描述

一个研究团队正在研究象形文字序列之间的相似性。他们将每个象形文字表示成一个非负整数。为了开展研究,他们采用了关于序列的如下概念。

对于一个给定的序列 A,某个序列 S 被称为是 A子序列,当且仅当 S 能够通过移除 A 中的某些(也可能零个)元素而得到。

下表给出了序列 A=[3,2,1,2] 的子序列的一部分例子。

子序列 A 得到子序列的方式
[3, 2, 1, 2] 不移除任何元素。
[2, 1, 2] [3, 2, 1, 2]
[3, 2, 2] [3, 2, 1, 2]
[3, 2] [3, 2, 1, 2] 或者 [3, 2, 1, 2]
[3] [3, 2, 1, 2]
[ ] [3, 2, 1, 2]

另一方面,[3,3][1,3] 不是 A 的子序列。

考虑有两个象形文字序列 AB。某个序列 S 被称为是 AB公共子序列,当且仅当 S 同时是 AB 的子序列。此外,我们说某个序列 UAB 的一个最全公共子序列,当且仅当如下两个条件成立: UAB 的一个公共子序列。 AB 的任意公共子序列,都是 U 的一个子序列。

可以证明,任意两个序列 AB 都至多有一个最全公共子序列。

研究人员发现了两个象形文字序列 AB。序列 A 包含 N 个象形文字,而序列 B 包含 M 个象形文字。请帮助研究人员为序列 AB 找到一个最全公共子序列,或者判定这样的序列并不存在。

实现细节

你要实现以下函数。

std::vector<int> ucs(std::vector<int> A, std::vector<int> B)
  • A:长度为 N 的数组,给出第一个序列。
  • B:长度为 M 的数组,给出第二个序列。
  • 如果 AB 有一个最全公共子序列,该函数应当返回一个包含该序列的数组。否则,该函数应当返回 [1](一个长度为 1 的数组,其唯一元素为 1)。
  • 对每个测试用例,该函数恰好被调用一次。

约束条件

  • 1N100000
  • 1M100000
  • 对所有满足 0i<Ni,都有 0A[i]200000
  • 对所有满足 0j<Mj,都有 0B[j]200000

子任务

子任务 分数 额外的约束条件
1 3 N=MAB 均由 N不同的整数构成,取自 0N1(包括这两个值)
2 15 对任意整数 kkAB 中的出现次数,加起来至多等于 3
3 10 对所有满足 0i<Ni,都有 A[i]1;对所有满足 0j<Mj,都有 B[j]1
4 16 AB 存在最全公共子序列。
5 14 N3000M3000
6 42 没有额外的约束条件。

例子

例 1

考虑以下函数调用。

ucs([0, 0, 1, 0, 1, 2], [2, 0, 1, 0, 2])

此时,AB 的公共子序列为:[ ][0][1][2][0,0][0,1][0,2][1,0][1,2][0,0,2][0,1,0][0,1,2][1,0,2][0,1,0,2]

由于 [0,1,0,2]AB 的一个公共子序列,而 AB 的所有公共子序列又都是 [0,1,0,2] 的子序列,因此函数应该返回 [0,1,0,2]

例 2

考虑以下函数调用。

ucs([0, 0, 2], [1, 1])

此时,AB 唯一的公共子序列为空序列 [ ]。因此函数应该返回一个空数组 [ ]

例 3

考虑以下函数调用。

ucs([0, 1, 0], [1, 0, 1])

此时,AB 的公共子序列为 [ ][0][1][0,1][1,0],可以看出两者并不存在最全公共子序列。因此,函数应该返回 [1]

评测程序示例

输入格式:

N  M
A[0]  A[1]  ...  A[N-1]
B[0]  B[1]  ...  B[M-1]

输出格式:

T
R[0]  R[1]  ...  R[T-1]

这里 Rucs 所返回的数组,而 T 为其长度。

时间限制:1s

空间限制:2048MB