T4 接龙
1 题目大意
* 有 nnn 个同学，每人一行“数字表”（一串整数）。
* 一共接 rrr 轮。每一轮一个同学在自己那一行里，选一段连续子串，长度在 [2,k][2,k][2,k]。
* 第一轮这段必须“以 1 开头”；之后每一轮这段必须“以上一轮的结尾数字开头”。
* 相邻两轮不能是同一个同学出手。
* 问很多次：给定 (r,c)(r,c)(r,c)，能不能恰好接 rrr 轮，且第 rrr 轮的最后一个数字是 ccc？
2 解题思路
1. 状态定义：
* dp[r][j] 表示在第 r 轮能否以数字 j 作为结尾。
* dp[r][j] 的取值：
* -1：不能接龙。
* 0：可以从任意行接龙。
* i：上一轮由第 i 个人接龙。
2. 预处理：
* 初始化 dp[0][1] = 0，表示第一轮可以从 1 开始。
* 对于每一轮 r，遍历每个人 i 的词库：
* 维护一个计数器 cnt，表示当前可以接龙的数字个数。
* 遍历词库中的每个数字 now：
* 如果 cnt > 0，则 now 可以作为接龙的结尾，更新 dp[r][now]。
* 如果 dp[r-1][now] 不为 -1 且上一轮不是 i，则设置 cnt = k - 1，表示接下来的 k-1 个数字可以作为接龙的结尾。
3. 查询处理：
* 对于每个查询 (r, c)，检查 dp[r][c] 是否为 -1，输出 1 或 0。
3 难点与核心想法
难点有两个：
1. 既要看“数能不能接上”，还要看“相邻两轮不能同一个人”；
2. 查询多，需要一次预处理，之后 O(1)O(1)O(1) 回答。
核心想法是做一张“可达数字表”，按轮数一层一层推：
* 设 dp[r][x]dp[r][x]dp[r][x] 表示“接到第 rrr 轮时，以数字 xxx 结尾的情况”，并且用取值记录“上一轮是谁”：
* −1-1−1：不可达；
* iii：只知道必须由第 iii 个人把 xxx 接出来（否则会违背相邻不同人）；
* 000：有人能，也不止一个人能（“任意人可接”状态，方便下一轮规避同人）。
* 初始化：dp[0][1]=0dp[0][1]=0dp[0][1]=0，表示“第 0 轮相当于已经在数字 1 上（不限谁）”。让dp[0][1]=0dp[0][1]=0dp[0][1]=0是为了保证“第一轮以1开头的时候”任何人都能接。
为什么要记录“上一轮是谁”？
相邻两轮不能同一个人。如果上一层把 xxx 接到手上的只有人 iii，那下一层人 iii就不能从 xxx 开始；
如果上一层把 xxx 能由至少两个人接到（记成 000），那下一层无论你选谁，总能挑到“与上一轮不同的人”。（比如第三轮3号和4号都可以接，那么第四轮需要3号接的时候，可以使用第三轮4号接的情况；第四轮需要4号接的时候，可以使用第三轮3号接的情况。因此第r轮只要不止一个人能接，第r+1轮就可以让任何人接。）
“CNTCNTCNT” 是什么？（滑窗计数）
在代码中，cnt 是一个计数器，用于记录当前可以接龙的数字个数。具体来说，cnt 的作用如下：
1. 表示可接龙的数字个数：
* cnt 的值表示当前数字 u 之后还有多少个数字可以作为接龙的结尾。
* 例如，如果 cnt = 3，则表示接下来的 3 个数字可以作为接龙的结尾。
2. 控制接龙序列的长度：
* 题目要求接龙序列的长度必须在 [2, k] 之间。
* 当遇到一个可以作为接龙起点的数字 now 时，设置 cnt = k - 1，表示接下来的 k - 1 个数字都可以作为接龙的结尾数字。
* 这样，接龙序列的最长长度就是 k（起点 u 加上 k - 1 个后续数字）。
3. 更新 dp 状态：
* 如果 cnt > 0，说明当前数字 now 可以作为接龙的结尾。
* 更新 dp[r][now]：
* 如果now是第一次被接龙，设置为当前人 i。
* 如果不是第一次被接龙，设置为 0（代表“有人能且不止一人能”）。
* 每次更新后，cnt 减 1，表示已经处理了一个接龙的数字。
4 小例子手推（K=3K=3K=3）
假设 k = 3，当前人 i 的词库为 [a, b, c, d, e]，且 dp[r-1][a] != -1 且 dp[r-1][a] != i：
1. 遍历到 a：
* dp[r-1][a] 有效，且上一轮不是 i，因此设置 cnt = k - 1 = 2。
* 表示接下来的 2 个数字可以作为接龙的结尾。
2. 遍历到 b：
* cnt = 2 > 0，因此 b 可以作为接龙的结尾。
* 更新 dp[r][b]：
* 如果是第一次被接龙，设置为 i。
* 否则设置为 0。
* cnt 减 1，变为 1。
3. 遍历到 c：
* cnt = 1 > 0，因此 c 可以作为接龙的结尾。
* 更新 dp[r][c]。
* cnt 减 1，变为 0。
4. 遍历到 d 和 e：
* cnt = 0，不处理。
这样，a 可以作为接龙的起点，b 和 c 可以作为接龙的结尾，形成长度为 2 或 3 的接龙序列。
5 复杂度
设所有行的总长度为 MMM（全部数字个数之和）。
我们做 r=1∼100r=1\sim 100r=1∼100 层，每层把所有行扫一遍：时间 O(100⋅M)O(100\cdot M)O(100⋅M)；
6 代码
