310557: CF1851C. Tiles Comeback
Description
Vlad remembered that he had a series of $n$ tiles and a number $k$. The tiles were numbered from left to right, and the $i$-th tile had colour $c_i$.
If you stand on the first tile and start jumping any number of tiles right, you can get a path of length $p$. The length of the path is the number of tiles you stood on.
Vlad wants to see if it is possible to get a path of length $p$ such that:
- it ends at tile with index $n$;
- $p$ is divisible by $k$
- the path is divided into blocks of length exactly $k$ each;
- tiles in each block have the same colour, the colors in adjacent blocks are not necessarily different.
For example, let $n = 14$, $k = 3$.
The colours of the tiles are contained in the array $c$ = [$\color{red}{1}, \color{violet}{2}, \color{red}{1}, \color{red}{1}, \color{gray}{7}, \color{orange}{5}, \color{green}{3}, \color{green}{3}, \color{red}{1}, \color{green}{3}, \color{blue}{4}, \color{blue}{4}, \color{violet}{2}, \color{blue}{4}$]. Then we can construct a path of length $6$ consisting of $2$ blocks:
$\color{red}{c_1} \rightarrow \color{red}{c_3} \rightarrow \color{red}{c_4} \rightarrow \color{blue}{c_{11}} \rightarrow \color{blue}{c_{12}} \rightarrow \color{blue}{c_{14}}$
All tiles from the $1$-st block will have colour $\color{red}{\textbf{1}}$, from the $2$-nd block will have colour $\color{blue}{\textbf{4}}$.
It is also possible to construct a path of length $9$ in this example, in which all tiles from the $1$-st block will have colour $\color{red}{\textbf{1}}$, from the $2$-nd block will have colour $\color{green}{\textbf{3}}$, and from the $3$-rd block will have colour $\color{blue}{\textbf{4}}$.
InputThe first line of input data contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
The description of the test cases follows.
The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$)—the number of tiles in the series and the length of the block.
The second line of each test case contains $n$ integers $c_1, c_2, c_3, \dots, c_n$ ($1 \le c_i \le n$) — the colours of the tiles.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
OutputFor each test case, output on a separate line:
- YES if you can get a path that satisfies these conditions;
- NO otherwise.
You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as positive response).
ExampleInput10 4 2 1 1 1 1 14 3 1 2 1 1 7 5 3 3 1 3 4 4 2 4 3 3 3 1 3 10 4 1 2 1 2 1 2 1 2 1 2 6 2 1 3 4 1 6 6 2 2 1 1 4 2 2 1 1 1 2 1 1 2 3 2 2 2 2 4 1 1 1 2 2Output
YES YES NO NO YES YES NO YES YES YESNote
In the first test case, you can jump from the first tile to the last tile;
The second test case is explained in the problem statement.
Input
题意翻译
有 $n$ 块瓷砖和一个数字 $k$，瓷砖从左到右编号，第 $i$ 个瓷砖的颜色为 $a_{i}$ 。如果你站在第 $11$ 块瓷砖上，开始向右跳任意数量的瓷砖，你可以得到一条长度为 $p$ 的路径，路径的长度就是你经过瓷砖的数量。请判断是否有可能得到一条长度为 $p$ 的路径，使得: 1. 它在 $n$ 号瓷砖处结束且 $p$ 能被 $k$ 整除； 2. 每组瓷砖都由 $k$ 块瓷砖组成； 1. 每组中的瓷砖颜色相同。Output
Vlad 记得他有一系列 $ n $ 块瓦片和一个数字 $ k $。瓦片从左到右编号，第 $ i $ 块瓦片的颜色为 $ c_i $。
如果你站在**第一块**瓦片上，开始向**右**跳任意数量的瓦片，你可以得到一条长度为 $ p $ 的路径。路径的长度是你站过的瓦片数量。
Vlad 想知道是否有可能得到一条长度为 $ p $ 的路径，使得：
- 路径以编号为 $ n $ 的瓦片结束；
- $ p $ 能被 $ k $ 整除；
- 路径被划分为每个长度正好为 $ k $ 的块；
- 每块中的瓦片颜色相同，相邻块的颜色不一定要不同。
**输入数据格式：**
输入数据的第一行包含一个整数 $ t $ ($ 1 \le t \le 10^4 $) —— 测试用例的数量。
接下来是每个测试用例的描述。
每个测试用例的第一行包含两个整数 $ n $ 和 $ k $ ($ 1 \le k \le n \le 2 \cdot 10^5 $) —— 瓦片系列的数量和块长度。
每个测试用例的第二行包含 $ n $ 个整数 $ c_1, c_2, c_3, \dots, c_n $ ($ 1 \le c_i \le n $) —— 瓦片的颜色。
保证所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。
**输出数据格式：**
对于每个测试用例，输出一行：
- 如果可以得到满足这些条件的路径，输出 **YES**；
- 否则输出 **NO**。
你可以以任何大小写组合输出 **YES** 和 **NO**。**题目大意：** Vlad 记得他有一系列 $ n $ 块瓦片和一个数字 $ k $。瓦片从左到右编号，第 $ i $ 块瓦片的颜色为 $ c_i $。 如果你站在**第一块**瓦片上，开始向**右**跳任意数量的瓦片，你可以得到一条长度为 $ p $ 的路径。路径的长度是你站过的瓦片数量。 Vlad 想知道是否有可能得到一条长度为 $ p $ 的路径，使得： - 路径以编号为 $ n $ 的瓦片结束； - $ p $ 能被 $ k $ 整除； - 路径被划分为每个长度正好为 $ k $ 的块； - 每块中的瓦片颜色相同，相邻块的颜色不一定要不同。 **输入数据格式：** 输入数据的第一行包含一个整数 $ t $ ($ 1 \le t \le 10^4 $) —— 测试用例的数量。 接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $ n $ 和 $ k $ ($ 1 \le k \le n \le 2 \cdot 10^5 $) —— 瓦片系列的数量和块长度。 每个测试用例的第二行包含 $ n $ 个整数 $ c_1, c_2, c_3, \dots, c_n $ ($ 1 \le c_i \le n $) —— 瓦片的颜色。 保证所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。 **输出数据格式：** 对于每个测试用例，输出一行： - 如果可以得到满足这些条件的路径，输出 **YES**； - 否则输出 **NO**。 你可以以任何大小写组合输出 **YES** 和 **NO**。