526互联

CF1051C Vasya and Big Integers 题解

发布时间 2023-12-25 17:36:20作者: FOX_konata

Problem - 1051E - Codeforces

Vasya and Big Integers - 洛谷

  • 感谢女队提交记录推荐给我的一道题 \(Orz\)

  • 首先 \(O(n^2)\) 的 \(dp\) 是 simple 的，如果你没看出来你可能是像我一样把题目看错了

  • 设 \(dp_i\) 表示考虑前 \(i\) 个的方案数，转移枚举长度后比较字典序。虽然看起来是 \(O(n^3)\) 的，但长度不相等的可以直接 \(O(1)\) 判断

  • 一个重要的性质：比较字符串 \(a,b\) 字典序等价于比较 \(a_{lcp(a,b)+1},b_{lcp(a,b)+1}\)

  • 求 \(LCP\)？

    1. 哈希+二分

    2. \(ExKMP\)

  • 复杂度 \(O(n \log n)\) 或 \(O(n)\)

  • 综上，女队 \(tql\)