接龙（chain）

本题为 CSP-J 2024 第二轮真题。本 OJ 采用标准输入输出评测，无需文件重定向。

【题目描述】 在玩惯了成语接龙之后，小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 个任务是否可以完成的， 即是否存在一个可能的游戏过程满足任务条件。 【输入格式】 从文件chain.in 中读入数据。 .本.题.有.多.组.测.试.数.据。 输入的第一行包含一个正整数T，表示数据组数。 接下来包含T 组数据，每组数据的格式如下： 第一行包含三个整数n, k, q，分别表示参与游戏的人数、接龙序列长度上限以及任 务个数。 接下来n 行： 第i 行包含(li + 1) 个整数li, Si,1, Si,2, · · · , Si,li，其中第一个整数li 表示序列Si 的 长度，接下来li 个整数描述序列Si。 接下来q 行： 第j 行包含两个整数rj, cj，描述一个任务。 【输出格式】 输出到文件chain.out 中。 对于每个任务：输出一行包含一个整数，若任务可以完成输出1，否则输出0。 【样例1 输入】 1 1 2 3 3 7 3 5 1 2 3 4 1 4 3 1 2 5 5 3 5 1 6 6 1 2 7 1 4 8 2 4 9 3 4 10 6 6 11 1 1 12 7 7 【样例1 输出】 1 1 2 0 3 1 4 0 5 1 6 0 7 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，因此任务显然不可完成。 【样例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 ≤1000、r ≤10、单组测试数 据内所有词库的长度和≤2000、q ≤1000。 【样例5】 见选手目录下的chain/chain5.in 与chain/chain5.ans。 该样例满足特殊性质B，其中前两组测试数据满足n ≤1000、r ≤10、单组测试数 据内所有词库的长度和≤2000、q ≤1000。 【样例6】 见选手目录下的chain/chain6.in 与chain/chain6.ans。 该样例满足特殊性质C，其中前两组测试数据满足n ≤1000、r ≤10、单组测试数 据内所有词库的长度和≤2000、q ≤1000。 【数据范围】 对于所有测试数据，保证： • 1 ≤T ≤5； • 1 ≤n ≤105，2 ≤k ≤2 × 105，1 ≤q ≤105； • 1 ≤li ≤2 × 105，1 ≤Si,j ≤2 × 105； • 1 ≤rj ≤102，1 ≤cj ≤2 × 105； • 设! l 为.单.组.测.试.数.据.内所有li 的和，则! l ≤2 × 105。 测试点 n ≤ r ≤ ! l ≤ q ≤ 特殊性质 1 103 1 2,000 103 无 2, 3 10 5 20 102 4, 5 103 10 2,000 103 A 6 105 102 2 ×105 105 7, 8 103 10 2,000 103 B 9, 10 105 102 2 ×105 105 11, 12 103 10 2,000 103 C 13, 14 105 102 2 ×105 105 15 ∼17 103 10 2,000 103 无 18 ∼20 105 102 2 ×105 105 特殊性质A：保证k = 2 × 105。 特殊性质B：保证k ≤5。 特殊性质C：保证在单组测试数据中，任意一个字符在词库中出现次数之和均不超 过5。

📦 本题含官方测试数据（CC BY-NC，noi.cn 发布），共 12 个测试点。