题解：P11230 [CSP-J 2024] 接龙

xufanen · 2024-10-27 11:20:40 · 题解

思路

1. 首先我们找出词库中所有的数字 1 作为可能的出发点。
2. 因为限制了单词长度，所以接下来我们只能将可能的出发点后面 k−1 个数标记为可能的终止点。
3. 我们开一个和词库一样大的动态数组 b，若 S_{i,j} 可能为出发点，就将 a_{i,j+1} 赋值为 k−1，按照 a_{i,j}=\max(a_{i,j},a_{i,j−1}−1) 的转移方程，只要 b_{i,j}>0，该点就可能成为终点。如果现在已经经历了 x−1 轮循环并执行了以上操作，我们就可以将接龙长度为 x 的问题全部解决掉了。
4. 再次找出那些下一轮接龙的出发点。如果 x 在至少两个人的词库中作为可能的终止点出现，那么所有人的词库中的 x 都可以作为下一轮的出发点；如果 x 只在一个人的词库中出现，那么除这个人以外的其他人词库中的 x 都可以作为下一轮的出发点。统计每一个数字成为终止点的次数，以及出现的位置。
5. 这就算是一次完整的操作，我们继续回到操作 3 进行下一轮循环。重复执行 \max r 次即可.