Camp Schedule 题解

思路

从直接枚举全部排列开始，可以把“排列”逐步压缩为“已经使用的字符数量与当前模式匹配状态”，最后再利用最优相邻出现必然采用最长 Border 的性质，把整个状态空间消去。

做法

子任务 1：枚举所有排列

当两个字符串长度都不超过 $10$ 时，可以枚举 $s$ 的所有不同排列，逐一统计 $t$ 的出现次数，并保留出现次数最大的任意排列。二进制串中有大量相同字符，用回溯时只需决定每个位置放 0 还是 1，不会重复枚举相同字符串。

这一做法直接按照定义判断最优性，时间复杂度为 $O\!\left(\binom{|s|}{c_0}|s||t|\right)$，其中 $c_0$ 是 $s$ 中 0 的数量。

子任务 2：KMP 自动机上的计数动态规划

设已经使用了 $i$ 个 0、$j$ 个 1，当前构造串与 $t$ 的最长前缀匹配长度为 $k$。预处理 KMP 自动机后，向末尾放入一个字符就能在 $O(1)$ 时间得到新的匹配长度，并判断是否新形成一次完整出现。

以 $(i,j,k)$ 为状态记录最多出现次数，并保存一条最优转移，即可在用完 $s$ 的全部字符后恢复任意一个最优排列。状态数至多为 $O(|s|^2|t|)$，每个状态只有两条转移，适用于第二个子任务。

子任务 3：利用最长 Border 构造

先统计 $s$ 中 0、1 的数量。若连一个完整的 $t$ 都无法放入，则最优出现次数为零，直接输出 $s$ 的任意排列即可。

否则先放入一个完整的 $t$。设 $b$ 是 $t$ 的最长真 Border 长度，即 $t$ 的长度为 $b$ 的前缀和后缀相同。两个相邻的 $t$ 若要尽量重叠，第二次出现只需追加后缀 $t[b\ldots |t|-1]$。于是只要剩余的 0、1 足够，就不断追加这段后缀，最后再补上所有未使用字符。

正确性来自两个事实：

1. 两次出现发生重叠时，重叠部分必是 $t$ 的一个 Border；最长 Border 给出的追加段最短。
2. 任意更短的 Border 所对应的追加段，都包含最长 Border 的追加段以及若干额外字符，因此对 0 和 1 的消耗都不会更少。完全不重叠时的消耗也不会更少。

所以每新增一次出现，当前方案在两种字符上的消耗都最小。能追加的次数达到全局上界，构造出的排列最优。

复杂度

子任务 1 的时间复杂度为 $O\!\left(\binom{|s|}{c_0}|s||t|\right)$；子任务 2 的时间、空间复杂度均为 $O(|s|^2|t|)$；满分做法的时间复杂度为 $O(|s|+|t|)$，空间复杂度为 $O(|s|+|t|)$。