CF1955D.Inaccurate Subsequence Search

普及/提高-

通过率：0%

AC君温馨提醒

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

题目描述

Maxim 有一个长度为 $n$ 的整数数组 $a$ 和一个长度为 $m$ 的整数数组 $b$ （ $m \le n$ ）。

Maxim 认为长度为 $m$ 的数组 $c$ 是好的，如果数组 $c$ 的元素可以重新排列，使得其中至少有 $k$ 个元素与数组 $b$ 的元素相同。

例如，如果 $b = [1, 2, 3, 4]$ 且 $k = 3$ ，那么数组 $[4, 1, 2, 3]$ 和 $[2, 3, 4, 5]$ 是好的（它们可以分别重排为 $[1, 2, 3, 4]$ 和 $[5, 2, 3, 4]$ ），而数组 $[3, 4, 5, 6]$ 和 $[3, 4, 3, 4]$ 不是好的。

Maxim 想要选择数组 $a$ 的每一个长度为 $m$ 的连续子段作为数组 $c$ 的元素。请帮助 Maxim 统计有多少个被选中的数组是好的。

换句话说，求有多少个位置 $1 \le l \le n - m + 1$ ，使得 $a_l, a_{l+1}, \dots, a_{l + m - 1}$ 组成的数组是好的数组。

输入格式

第一行包含一个整数 $t$ （ $1 \le t \le 10^4$ ），表示测试用例的数量。

每个测试用例的第一行包含三个整数 $n$ 、 $m$ 和 $k$ （ $1 \le k \le m \le n \le 2 \cdot 10^5$ ），分别表示数组 $a$ 和 $b$ 的长度，以及要求匹配的元素个数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ （ $1 \le a_i \le 10^6$ ），表示数组 $a$ 的元素。数组 $a$ 的元素不一定互不相同。

每个测试用例的第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$ （ $1 \le b_i \le 10^6$ ），表示数组 $b$ 的元素。数组 $b$ 的元素不一定互不相同。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$ ， $m$ 的总和也不超过 $2 \cdot 10^5$ 。

输出格式

对于每个测试用例，输出一个整数，表示数组 $a$ 中好的子段的数量，每个测试用例输出一行。

输入输出样例

输入#1

5
7 4 2
4 1 2 3 4 5 6
1 2 3 4
7 4 3
4 1 2 3 4 5 6
1 2 3 4
7 4 4
4 1 2 3 4 5 6
1 2 3 4
11 5 3
9 9 2 2 10 9 7 6 3 6 3
6 9 7 8 10
4 1 1
4 1 5 6
6

输出#1

说明/提示

在第一个样例中，所有子段都是好的。

在第二个样例中，好的子段起始于位置 $1$ 、 $2$ 和 $3$ 。

在第三个样例中，好的子段起始于位置 $1$ 和 $2$ 。

由 ChatGPT 4.1 翻译

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

首页