题解：P11230 [CSP-J 2024] 接龙（民间数据）

WaTleZero_pt · 2024-10-27 08:43:41 · 题解

这道题萌新居然想了 90\texttt{ min} 实在是太菜了

我们注意到 r_{i} 的数据范围非常小好吧，很容易想到一个 O(T(\max r \sum l)) 的做法。具体是如何操作的呢？

1. 首先我们找出词库中所有的数字 1 作为可能的出发点。

2. 接下来我们将可能的出发点后面 k-1 个数标记为可能的终止点。为了避免重复计算被卡到 n^{2} 级别，我们开一个和词库一样大的动态数组 b，若 S_{i,j} 可能为出发点，将 b_{i,j+1} 赋值为 k-1，这样按照 b_{i,j} = \max(b_{i,j},b_{i,j-1}-1) 的转移方法，只要 b_{i,j} > 0 该点就可能成为终止点。

3. 如果现在已经经历了 x-1 轮循环并执行了操作 2，我们就可以将接龙长度为 x 的问题全部回答掉了。

4. 然后我们要做的就是再次找出那些可能是下一轮接龙的出发点。如果 x 在至少两个人的词库中作为可能的终止点出现，那么所有人的词库中的 x 都可以作为下一轮的出发点；如果 x 只在一个人的词库中出现，那么除这个人以外的其他人词库中的 x 都可以作为下一轮的出发点。这也是很好做的，只需要我们统计每一个数字成为终止点的次数，以及出现的位置即可。

这就算是一次完整的操作，我们继续回到操作 2 进行下一轮循环。重复执行 \max r 次即可。