P3960 - 接龙 [CSP-J 2024](chain)

内存限制：512 MB 时间限制：20.000 S

评测方式：文本比较命题人：

提交：8 解决：4

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

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

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

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

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

从文件 chain.in 中读入数据。

本题有多组测试数据。

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

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

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

接下来 $�$ 行：

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

接下来 $�$ 行：

第 $�$ 行包含两个整数 $�_{�}, �_{�}$ ，描述一个任务。

输出到文件 chain.out 中。

对于每个任务：输出一行包含一个整数，若任务可以完成输出 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 解释】

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

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

$7$ ，因此任务显然不可完成。
附件下载
chain.zip

CSP-J

提交提交记录统计露一手!

3960: 接龙 [CSP-J 2024](chain)

题目描述

输入

输出

样例输入复制

样例输出复制

提示

附件下载

来源/分类