CF1845C Strong Password

思路

这场 edu 爆炸了，特此记录。

由于 \(m \le 10\)，因此可以直接考虑搜索。对于定义状态为 \((idx, cur)\)，表示当前在填密码的第 \(idx\) 位，且使用了 \(s\) 中的前 \(cur\) 个字符。首先注意到对于同一个数字，如果其在 \(s\) 中出现了不止一次，那么出现在前边的显然比出现在后边的潜力大，即可以组成更多的子序列。于是可以写出一个很简单的搜索。对于每一个 \(i \in [l_{idx + 1}, r_{idx + 1}]\)，找到其在 \(s[cur:]\) 中的第一个出现位置 \(p\)，然后将状态转移到 \((idx + 1, p)\) 即可。如果不存在这样的 \(p\) 的话，则意味着一组合法解，直接退出即可。而对于查询后继位置的部分，可以提前预处理出每一个数字在 \(s\) 中的出现位置，然后二分查找即可。

但是像这样直接搜的话复杂度是 \(O(10 ^ m \log \operatorname{len}(s))\) 级别的。这不够好，因此需要优化。一个比较显然的优化是对 \(m\) 折半搜索。具体做法就是先按上边的方式找出所有长度小于 \(\frac{m}{2}\) 的子序列的最大 \(cur\) 值，记为 \(max\)，然后再用类似于上边的方法处理 \((\frac{m}{2}, m]\) 的子序列，不过初始状态为 \((m - 1, n)\)，即从后往前找，然后找的时候找一个数字在 \(s[:cur]\) 的最后一次出现位置，这是为了保证构造出的字符串其起始位置最大，方便后边的答案处理。

在第二次搜索时，每查到一个子串，记其起始位置为 \(st\)，如果 \(st \le max\)，即存在前后字符串的重叠的话，那么意味着存在合法解。这是因为上述的搜索过程保证了第一次搜索得到的子序列结束位置最小，第二次搜索得到的子序列结束位置最大。如果这样仍然存在重叠的话，那么一定存在一种子序列的构造方案使得其无法在 \(s\) 中被找到。

于是这样的时间复杂度为 \(O(10 ^ {\frac{m}{2}} \log \operatorname{len}(s))\)。

然后注意到每次二分出来的答案是具有单调性的，于是可以去二分化，做到 \(O(10 ^ {\frac{m}{2}})\)。

代码

link

我写的是没有去掉二分的版本。