P3426 [POI2005] SZA-Template

_32_qwq · 2024-10-22 16:10:42 · 题解

upd on 2024.11.17：发现讨论区有 hack，经测试可以通过，当然也欢迎各位 hack。

先枚举 border 长度 L。

定义 f_i 表示 s_{1,i} 是否能被表示出来。

如果 s_{1,L}=s_{i-L+1,L}，那么我们可以在前面接，即 f_i\gets\cup_{j=i-L}^{i-1} f_j，其中 \cup 表示逻辑或，这一步可以用前缀和优化到 O(1) 的转移；否则因为 s_i 一定不会被覆盖到，所以 f_i\gets0。

上述做法是 O(n^2) 的，考虑剪枝。

注意到 L 是定长，如果 f 中出现了连续 L 个 0，那么后面一定都是 0，因为转移只根前 L 个有关。

这样就能过掉洛谷上的所有数据，但是仍然会存在 hack，如果我们是一车 a 后面跟了个 b，那么我们会找 a、aa 等，但是发现 a 一定强于 aa，所以由一个 border 复制若干遍得到的 border 一定是不优的。

但是这样也仍然有锅，如果我们复制若干遍 ab，最后接上个 c，会发现所有长度为奇数的串都会被查询！但是注意到 ababa 能表示的 aba 一定能表示。这样我们就得到一个比刚才更强的结论：如果一个 border 能被其它 border 表示出来，那么它一定不优。

实现方面就是如果 f_i=1，我们就给 i 打上个标记，然后枚举到长度 i 的时候就直接跳过。

这样做在洛谷目前的数据下非常优秀，最慢点仅 11ms。