link
CCF 目前在 CSP-J 出过的唯一蓝题，也是个 nggyu 题。
题目大意
n 个人进行接龙游戏，每人有一个长为 \(l_i\) 的序列 \(S_i\)。
规则
-
接龙起始序列为 \(\{1\}\)。
-
每轮进行接龙的人不能是上一轮的人。
-
当前玩家在自己的序列中选出一个满足接龙条件的连续子序列。
-
选出的子序列长度必须在 [2,k] 范围内，k 是定值。
有 q 次询问，每次询问给出 \(r_i\ ,c_i\)
求恰好进行 \(r_i\) 轮接龙的情况下，是否存在一种情况，使最终接龙序列的末位字符为 \(c_i\)，存在输出 1，不存在输出 0。
正解
奶龙题就懒得说部分分了，直接考虑 dp。
状态设计
考虑设计一个二维 dp[i][j]，表示接龙序列末位字符为 j 时可以进行第 i 轮接龙的玩家，如果有多位就用 0 表示，所以初始值全部设为 -1。
看一眼题目范围发现时间空间都卡的刚刚好，且询问时可 O(1) 回答，所以这就是正解
标签：int,玩家,2024,接龙,序列,CSP,dp From： https://www.cnblogs.com/hypixel/p/18567171