3940 - 接龙 [CSP-J 2024]-东方博宜OJ

3940 - 接龙 [CSP-J 2024]

题目描述

在玩惯了成语接龙之后，小 J 和他的朋友们发明了一个新的接龙规则。

总共有 $n$ 个人参与这个接龙游戏，第 $i$ 个人会获得一个整数序列 $S_i$ 作为他的词库。

一次游戏分为若干轮，每一轮规则如下：

$n$ 个人中的某个人 $p$ 带着他的词库 $S_p$ 进行接龙。若这不是游戏的第一轮，那么这一轮进行接龙的人不能与上一轮相同，但可以与上上轮或更往前的轮相同。
接龙的人选择一个长度在 [2, k] 的 S_p 的连续子序列 A 作为这一轮的接龙序列，其中 k 是给定的常数。若这是游戏的第一轮，那么 A 需要以元素 1 开头，否则 A 需要以上一轮的接龙序列的最后一个元素开头。
- 序列 $A$ 是序列 $S$ 的连续子序列当且仅当可以通过删除 $S$ 的开头和结尾的若干元素（可以不删除）得到 $A$ 。

为了强调合作，小 J 给了 $n$ 个参与游戏的人 $q$ 个任务，第 $j$ 个任务需要这 $n$ 个人进行一次游戏，在这次游戏里进行恰好 $r_j$ 轮接龙，且最后一轮的接龙序列的最后一个元素恰好为 $c_j$ 。为了保证任务的可行性，小 J 请来你判断这 $q$ 个任务是否可以完成的，即是否存在一个可能的游戏过程满足任务条件。

输入

本题有多组测试数据。

输入的第一行包含一个正整数 $T$ ，表示数据组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

第一行包含三个整数 $n, k, q$ ，分别表示参与游戏的人数、接龙序列长度上限以及任务个数。

接下来 $n$ 行：

第 $i$ 行包含 $(l_i + 1)$ 个整数 $l_i, S_{i,1}, S_{i,2}, \dots , S_{i,l_i}$ ，其中第一个整数 $l_i$ 表示序列 $S_i$ 的长度，接下来 $l_i$ 个整数描述序列 $S_i$ 。

接下来 $q$ 行：

第 $j$ 行包含两个整数 $r_j, c_j$ ，描述一个任务。

输出

对于每个任务：输出一行包含一个整数，若任务可以完成输出 1，否则输出 0。

样例

输入

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

输出

说明

【样例 1 解释】

在下文中，我们使用 ${A_i} = {A_1, A_2, \dots , A_r}$ 表示一轮游戏中所有的接龙序列， ${p_i} = {p_1, p_2, \dots , p_r}$ 表示对应的接龙的人的编号。由于所有字符均为一位数字，为了方便我们直接使用数字字符串表示序列。

对于第一组询问， $p_1 = 1$ 、 $A_1 = 12$ 是一个满足条件的游戏过程。
对于第二组询问，可以证明任务不可完成。注意 $p_1 = 1$ 、 $A_1 = 1234$ 不是合法的游戏过程，因为此时 $|A_1| = 4 > k$ 。
对于第三组询问， ${p_i} = {2, 1}$ 、 ${A_i} = {12, 234}$ 是一个满足条件的游戏过程。
对于第四组询问，可以证明任务不可完成。注意 ${p_i} = {2, 1, 1}、{A_i} = {12, 23, 34}$ 不是一个合法的游戏过程，因为尽管所有的接龙序列长度均不超过 $k$ ，但第二轮和第三轮由同一个人接龙，不符合要求。
对于第五组询问， ${p_i} = {1, 2, 3, 1, 2, 3}$ 、 ${A_i} = {12, 25, 51, 12, 25, 516}$ 是一个满足条件的游戏过程。
对于第六组询问，可以证明任务不可完成。注意每个接龙序列的长度必须大于等于 $2$ ，因此 $A_1 = 1$ 不是一个合法的游戏过程。
对于第七组询问，所有人的词库均不存在字符 $\tt 7$ ，因此任务显然不可完成。

【样例 2】

见选手目录下的 chain/chain2.in 与 chain/chain2.ans。

该样例满足测试点 1 的特殊性质。

【样例 3】

见选手目录下的 chain/chain3.in 与 chain/chain3.ans。

该样例满足测试点 2 的特殊性质。

【样例 4】

见选手目录下的 chain/chain4.in 与 chain/chain4.ans。

该样例满足特殊性质 A，其中前两组测试数据满足 $n \leq 1000$ 、 $r \leq 10$ 、单组测试数据内所有词库的长度和 $\leq 2000$ 、 $q \leq 1000$ 。

【样例 5】

见选手目录下的 chain/chain5.in 与 chain/chain5.ans。

该样例满足特殊性质 B，其中前两组测试数据满足 $n \leq 1000$ 、 $r \leq 10$ 、单组测试数据内所有词库的长度和 $\leq 2000$ 、 $q \leq 1000$ 。

【样例 6】

见选手目录下的 chain/chain6.in 与 chain/chain6.ans。

该样例满足特殊性质 C，其中前两组测试数据满足 $n \leq 1000$ 、 $r \leq 10$ 、单组测试数据内所有词库的长度和 $\leq 2000$ 、 $q \leq 1000$ 。

【数据范围】

对于所有测试数据，保证：

$1 \leq T \leq 5$ ；
$1 \leq n \leq 10^5$ ， $2 \leq k \leq 2 \times 10^5$ ， $1 \leq q \leq 10^5$ ；
$1 \leq l_i \leq 2 \times 10^5$ ， $1 \leq S_{i,j} \leq 2 \times 10^5$ ；
$1 \leq r_j \leq 10^2$ ， $1 \leq c_j \leq 2 \times 10^5$ ；
设 $\sum l$ 为单组测试数据内所有 $l_i$ 的和，则 $\sum l\leq 2\times 10^5$ 。

测试点	$n\leq$	$r\leq$	$\sum l\leq$	$q\leq$	特殊性质
$1$	$10^3$	$1$	$2000$	$10^3$	无
$2,3$	$10$	$5$	$20$	$10^2$	无
$4,5$	$10^3$	$10$	$2000$	$10^3$	A
$6$	$10^5$	$10^2$	$2\times 10^5$	$10^5$	A
$7,8$	$10^3$	$10$	$2000$	$10^3$	B
$9,10$	$10^5$	$10^2$	$2\times 10^5$	$10^5$	B
$11,12$	$10^3$	$10$	$2000$	$10^3$	C
$13,14$	$10^5$	$10^2$	$2\times 10^5$	$10^5$	C
$15\sim 17$	$10^3$	$10$	$2000$	$10^3$	无
$18\sim 20$	$10^5$	$10^2$	$2\times 10^5$	$10^5$	无

特殊性质 A：保证 $k = 2 \times 10^5$ 。

特殊性质 B：保证 $k \leq 5$ 。

特殊性质 C：保证在单组测试数据中，任意一个字符在词库中出现次数之和均不超过 $5$ 。

来源

CSP-J 2024

标签

CSP-J 2024 图论

题目参数

时间限制	2 秒
内存限制	512 MB
提交次数
通过人数
金币数量
难度

上一题下一题