A - 道路
简单题。
题解
B - 影魔
场上每怎么想。
题解
C - 带子串包含约束LCS问题
赛时思路
考虑没有限制的 \(LCS\)：设 \(f_{i,j}\) 表示 \(A\) 串前 \(i\) 个，\(B\) 串前 \(j\) 个可以构成的最长公共子序列。\(f_{i,j}=max(f_{i-1,j},f_{i,j-1},f_{i-1,j-1}+[A_i=B_j])\)，其中中括号是艾弗森括号。
但是这个题目要求答案的字串包含所有约束集内的字符串。
先把约束集的 \(ACAM\) 建出来，设 \(f_{i,j,k,s}\) 表示 \(X\) 串前 \(i\) 个字符，\(Y\) 串前 \(j\) 个字符，公共子序列在 \(ACAM\) 上走到位置 \(k\)，约束集被覆盖的状态为 \(s\) 的最长公共子序列长度。
这样时间复杂度是 \(\mathcal O(n^22^k\sum|l_i|)\)，会 \(T\) 飞。
题解
由于没想到子序列自动机，赛时的做法难以优化常数，几乎是跑满的，无法通过。
总结
有一些题目看起来无法通过的复杂度游客能就是正解，当发现一道题一直想不到复杂度正确的做法时，可以考虑换成复杂度相同，但是常数更小，更容易优化的做法。