[CSP 2024 J & COGS 4052] 接龙

  注意到本题在洛谷是一道蓝题。所以：论如何在比赛中场切蓝题？（注意，这里没有任何一个人因为没做过交互题而在某比赛中遇到蓝题却受到伤害！！！）

 引入

  有 \(n\) 个人，每个人手里有一个数字序列（词库）。玩一个接龙游戏：

- 第 \(1\) 轮：可以从任意一个人的序列中，选一个长度在 \([2, k]\) 之间的连续子序列，且子序列的第一个数必须是 \(1\)

- 第 \(2\) 轮及以后：选的子序列的第一个数，必须等于上一轮子序列的最后一个数，且不能连续两轮用同一个人的序列

有 \(q\) 个询问，每个询问给两个数 \(r\) 和 \(c\)，问能否恰好用 \(r\) 轮接龙，让最后一轮的最后一个数字是 \(c\)

分析

  这道题如果直接模拟，复杂度会非常高。需要一种高效的方法来判断“可行性”。

正解采用动态规划加滑动窗口的思路：

  状态定义：\(dp[r][x]\) 表示能否在 \(r\) 轮内，以数字 \(x\) 作为结尾

- \(dp[r][x] = -1\)：不可行

- \(dp[r][x] = i\)：可行，且最后一轮是由第 \(i\) 个人完成的

- \(dp[r][x] = 0\)：可行，且有多个人都能完成（用于后续判断）

  状态转移：从 \(dp[r-1][y]\) 到 \(dp[r][x]\)

- 如果存在某个人 \(i\)，他的序列中有以 \(y\) 开头、长度在 \([2,k]\) 内的子序列，且以 \(x\) 结尾

- 且 \(dp[r-1][y]\) 不是由 \(i\) 完成的（不能连续两轮用同一个人）

- 那么 \(dp[r][x]\) 就是可行的

  优化方法：

- 用滑动窗口在每个序列中快速找到所有可能的（开头，结尾）对

- 用 \(cnt\) 记录当前正在构建的子序列长度

后记

 1. 为什么 \(cnt\) 这样工作？

当遇到一个可以作为开头的数字时，我们允许它后面最多接 \(k-1\) 个数。\(cnt\) 就是“还能接几个数”的计数器。每遍历一个数，如果 \(cnt>0\)，说明当前数可以作为某个子序列的结尾，然后 \(cnt\) 减一。

 2. \(dp[r][x]\) 的三个值含义

- \(-1\)：不可行

- \(i\)：可行，且最后一轮是第 \(i\) 个人完成的（唯一）

- \(0\)：可行，但有多个人都能完成（用于判断不能连续两轮同一个人）

 3. 为什么最后要取 \(tot\) 的最大值？

因为数字的范围可能很大（\(10^9\)），但实际出现的数字有限。只开 \(tot+2\) 的数组，避免内存过大。

 复杂度分析

轮数 \(\leq 100\)，总序列长度 \(\leq 2\times 10^5\)，总复杂度 \(O(100 \times \text{总长度})\)，可以接受。

 注意事项

1. 读入要用 \(ios::sync\_with\_stdio(0);cin.tie(0);\) 加速

2. 文件输入输出不要忘：\(freopen\)

3. dp 数组要用 vector 动态分配，避免内存过大

更新日志：

2026.3.20 创建题解