2024 T4 接龙

主知识点：动态规划。交叉标签：动态规划、滑动窗口、前缀和、深搜。
暴力标注：DP 可用暴力拿部分分。
OJ 使用标准输入与标准输出。原比赛文件名为 chain.in / chain.out；下方如保留原文件约定，以本句的 OJ 约定为准。
时限 2 秒；内存 512 MiB；测试点 20；总分 100。
数据来源：公开存档数据；未逐文件对照官网下载包。

题目描述

$n$ 个人各有整数词库序列 $S_i$。每轮由一人选择自己词库中长度在 $[2,k]$ 的连续子序列作为接龙序列。第一轮的序列必须以 1 开头，之后每轮的首元素必须等于上轮的末元素。相邻两轮使用的人不能相同，隔一轮或更远则可重复使用同一个人。

给出 $q$ 个独立任务 $(r_j,c_j)$，判断能否进行恰好 $r_j$ 轮游戏，并使最后一轮末元素为 $c_j$。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 $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

输入：

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
0
1
0
1
0
0

数据范围与特殊性质

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

• $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$
$7,8$	$10^3$	$10$	$2000$	$10^3$	B
$9,10$	$10^5$	$10^2$	$2\times 10^5$	$10^5$
$11,12$	$10^3$	$10$	$2000$	$10^3$	C
$13,14$	$10^5$	$10^2$	$2\times 10^5$	$10^5$
$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 ≤ 5$。

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

附加样例

本题的公开样例整理在对应的“样例”ZIP 中。样例不计入评测测试点；题面中的样例也已保留。

暴力退路标注（教学补充）

DP 可用暴力拿部分分。DFS 状态为 (轮数,末字符,上轮人)，枚举其他人的所有长度 2..k 且首字符相同的连续子序列。小数据分支很多，建议缓存同状态并先枚举转移边；第 1 点可直接枚举一轮，第 2~3 点规模≤20、轮数≤5。

目标范围：第 1 点 5 分；2~3 点可尝试，纯 DFS 不保证 15 分。部分分按原题规模判断，不构成对任意实现或评测机的得分保证。

来源与整理说明

题目原作者/发布者：中国计算机学会 CCF / NOI。题意经过改写，保留公式、输入输出、样例及约束；知识点和暴力标注为本次整理补充。

• 题面及约束校对来源：洛谷 CCF_NOI 题目 P11230
• 赛事：CSP-J 第二轮入门级 2024。
• 详细数据来源、版本和哈希见总包 来源与校验/manifest.json。