ABC312

__vector__ · 2023-07-29 22:06:12 · 题解

纪念第一次赛时过 Ex && 做出 atc 2400+ 题目，虽然是个大水题。

• 做法 1
  考虑暴力枚举 k，暴力判定。
  显然会寄掉。

• 做法 2
  显然同一个字符串出现两次，第二次的答案一定大于第一次。
  其实一个字符串，只会对所有的循环节产生影响，而它本身的循环节种类显然是 O(\sqrt{n}) 量级的，可以参考因数数量，设本字符串长度为 len，那么最终造成的时间消耗是 O(len \sqrt{len}) 级别的。
  复杂度瓶颈在于同一个字符串出现多次。
  所以可以对字符串进行记忆化，对输入的字符串存储答案字符串，对最终形成的字符串（答案字符串）进行存在性标记。
  但朴素实现复杂度不变，主要瓶颈在于存储最终的答案字符串。

• 做法 3
  考虑字典树，此时我们对于答案字符串的记忆化，不再直接存储字符串，转而使用字典树，而记忆方式则是同时记录 k 和答案字符串对应的字典树坐标。
  这样构造当前答案的时候，可以直接从原记录的字典树对应位置继续构造，而不用从头开始。
  复杂度 O(len \sqrt{len})。
  AC code
  另外由于循环节数量实际上一般远远少于根号，所以运行时间应该是接近 log 的。