AT_arc151_e.[ARC151E] Keep Being Substring

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个长度为 $N$ 的整数序列 $A = (A_1, A_2, \ldots, A_N)$ 。此外，给定 $A$ 的一个长度为 $P$ 的连续子序列 $X = (X_1, X_2, \ldots, X_P)$ ，以及 $A$ 的一个长度为 $Q$ 的连续子序列 $Y = (Y_1, Y_2, \ldots, Y_Q)$ 。

你可以对 $X$ 进行如下四种操作中的任意一种，每种操作可以执行任意次数（也可以不执行）：

在 $X$ 的开头添加任意一个整数。
删除 $X$ 的开头元素。
在 $X$ 的末尾添加任意一个整数。
删除 $X$ 的末尾元素。

但无论操作前后， $X$ 必须始终是 $A$ 的非空连续子序列。请你求出将 $X$ 变为 $Y$ 所需的最小操作次数。已知在本题的限制下，总能通过若干次操作使 $X$ 变为 $Y$ 。

什么是连续子序列？
序列 $X = (X_1, X_2, \ldots, X_P)$ 是序列 $A = (A_1, A_2, \ldots, A_N)$ 的连续子序列，当且仅当存在整数 $1 \leq l \leq N-P+1$ ，使得对于所有 $i = 1, 2, \ldots, P$ ，都有 $X_i = A_{l+i-1}$ 。

输入格式

输入按以下格式从标准输入读入。

$N$ $A_1$ $A_2$ $\ldots$ $A_N$ $P$ $X_1$ $X_2$ $\ldots$ $X_P$ $Q$ $Y_1$ $Y_2$ $\ldots$ $Y_Q$

输出格式

输出答案。

输入输出样例

输入#1
```
7
3 1 4 1 5 7 2
2
3 1
3
1 5 7
```
输出#1
```
3
```

输入#2

20
2 5 1 2 7 7 4 5 3 7 7 4 5 5 5 4 6 5 6 1
6
1 2 7 7 4 5
7
7 4 5 5 5 4 6

输出#2

说明/提示

数据范围

$1 \leq N \leq 2 \times 10^5$
$1 \leq A_i \leq N$
$1 \leq P, Q \leq N$
$(X_1, X_2, \ldots, X_P)$ 和 $(Y_1, Y_2, \ldots, Y_Q)$ 都是 $(A_1, A_2, \ldots, A_N)$ 的连续子序列
输入均为整数

样例解释 1

可以按如下步骤操作，使 $X$ 始终为 $A$ 的非空连续子序列，并最终变为 $Y$ ：

首先删除 $X$ 的开头元素，结果 $X = (1)$ 。
然后在 $X$ 的末尾添加 $5$ ，结果 $X = (1, 5)$ 。
再在 $X$ 的末尾添加 $7$ ，结果 $X = (1, 5, 7)$ ，此时 $X$ 与 $Y$ 相同。

上述操作共需 $3$ 次，这就是最小操作次数。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页