问题 D: 接龙（chain）

---

【题目描述】

【题目描述】 
在玩惯了成语接龙之后，小J和他的朋友们发明了一个新的接龙规则。
总共有n个人参与这个接龙游戏，第i个人会获得一个整数序列Si作为他的词库。一次游戏分为若干轮，每一轮规则如下： 
• n个人中的某个人p带着他的词库Sp进行接龙。若这不是游戏的第一轮，那么这一轮进行接龙的人不能与上一轮相同，但可以与上上轮或更往前的轮相同。 
• 接龙的人选择一个长度在[2,k] 的 Sp 的连续子序列 A 作为这一轮的 接龙序列，其中k是给定的常数。若这是游戏的第一轮，那么A需要以元素1开头，否则 A 需要以上一轮的接龙序列的最后一个元素开头。
– 序列A是序列S 的连续子序列当且仅当可以通过删除S 的开头和结尾的若干元素（可以不删除）得到A。 
为了强调合作，小J给了n个参与游戏的人q个任务，第j个任务需要这n个人进行一次游戏，在这次游戏里进行恰好rj 轮接龙，且最后一轮的接龙序列的最后一个元素恰好为cj。为了保证任务的可行性，小J请来你判断这q个任务是否可以完成的，即是否存在一个可能的游戏过程满足任务条件。

【输入】

本题有多组测试数据。 
输入的第一行包含一个正整数T，表示数据组数。 
接下来包含T 组数据，每组数据的格式如下： 
第一行包含三个整数n,k,q，分别表示参与游戏的人数、接龙序列长度上限以及任务个数。 
接下来n行： 
第i行包含(li+1) 个整数li,Si,1,Si,2,··· ,Si,li ，其中第一个整数 li 表示序列 Si 的长度，接下来li 个整数描述序列Si。 
接下来q行： 第j 行包含两个整数rj,cj，描述一个任务。

【输出】

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

【提示】

【样例1解释】 
在下文中，我们使用{Ai}={A1,A2,··· ,Ar}表示一轮游戏中所有的接龙序列，{pi}={p1,p2,··· ,pr}表示对应的接龙的人的编号。由于所有字符均为一位数字，为了方便我们直接使用数字字符串表示序列。
•对于第一组询问，p1=1、A1=12是一个满足条件的游戏过程。 
•对于第二组询问，可以证明任务不可完成。注意p1=1、A1=1234不是合法的游戏过程，因为此时|A1|=4>k。 
•对于第三组询问，{pi}={2,1}、{Ai}={12,234}是一个满足条件的游戏过程。 
•对于第四组询问，可以证明任务不可完成。注意{pi}={2,1,1}、{Ai}={12,23,34}不是一个合法的游戏过程，因为尽管所有的接龙序列长度均不超过k，但第二轮和第三轮由同一个人接龙，不符合要求。 
• 对于第五组询问，{pi} = {1,2,3,1,2,3}、{Ai} = {12,25,51,12,25,516} 是一个满足条件的游戏过程。 
• 对于第六组询问，可以证明任务不可完成。注意每个接龙序列的长度必须大于等于2，因此A1=1不是一个合法的游戏过程。 
• 对于第七组询问，所有人的词库均不存在字符7，因此任务显然不可完成。


【数据范围】 
对于所有测试数据，保证： 
• 1≤T ≤5； 
• 1≤n≤100000，2≤k≤2×100000，1≤q≤100000； 
• 1≤li ≤2×100000，1≤Si,j ≤2×100000；
•1≤rj≤100，1≤cj≤2×100000； 
•设∑l为单组测试数据.内所有li的和，则∑l≤2×100000。

测试点	n≤	r≤	∑l≤	q≤	特殊性质
1	1000	1	2000	1000	无
2,3	10	5	20	100	无
4,5	1000	10	2000	1000	A
6	100000	100	200000	100000	A
7,8	1000	10	2000	1000	B
9,10	100000	100	200000	100000	B
11,12	1000	10	2000	1000	C
13,14	100000	100	200000	100000	C
15~17	1000	10	2000	1000	无
18~20	100000	100	200000	100000	无

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

题目类型~

CSP-J2024T4 

咻咻~

提交答案 状态 返回作业