题目链接

题意

字符集 $\Sigma=\{0, 1\}$.

给定不超过 $N$ 位的字符串集合 $S$, 求字符串满足它是 $S$ 中至少 $K$ 个串的子序列。

如果有多解，输出最长的；还有多解，输出字典序最小的。

串可以为空，保证 $0 \le N \le 20$, $K \le |S|$.

题解

先考虑如何判定字符串 $s$ 是 $t$ 的子串。

从左到右依次考虑 $s$ 的每个字符 $s_i$:

• 若 $t$ 中不含 $s_i$, 可得 $s$ 不是 $t$ 的子串；
• 否则将 $t$ 中第一个 $s_i$ 及之前的所有字符删去（记此处理后的字符串为 $\mathrm{trans}(t, s_i)$），继续枚举 $s_i$.

当 $s$ 的所有字符都考虑完毕时，可得 $s$ 是 $t$ 的子串。

考虑用动态规划描述上述过程，将 $\Sigma^* \times S$ 一并匹配。

因此记 $f(s, t)$ 表示 $S$ 中有多少元素按照上述操作依次匹配过 $s$ 中的字符后，余下的字符串为 $t$.

初值：对于 $t \in S$, $f(\epsilon, t)=1$, 其余为 $0$.

转移：对于 $s \in \Sigma^*, c \in \Sigma$ 以及含有 $c$ 的字符串 $t$, $f\big(sc, \mathrm{trans}(t, c)\big) \overset+\gets f(s, t)$.

关于 $s$ 的答案：$\sum_t f(s, t)$.

用二进制来压缩 $s$ 与 $t$ 并计算 $\mathrm{trans}(t, c)$.

由于 $|s|+|t| \le N$, 该算法的时空复杂度为 $O(N2^N)$.

代码链接