字符串哈希, 一般都是写困难题的, 学会上大分. 同类型的AC自动机,后缀数组都是较难的知识点 哈希分单模双模哈希: 单模哈希 根据生日攻击，设 M 为模数，仅仅计算大约 1.18⋅ sqrt(M)​个不同字符串的哈希值，就有 50% 的概率会发生哈希碰撞，也就是有两个不同的字符串，哈希值是一样的。 双模哈希 设 M1和 M2为模数，此时要计算大约…

曼哈顿距离应该是我们熟知的距离计算方式,两个单元格 (xi, yi) 和 (xj, yj) 之间的曼哈顿距离为 |xi - xj| + |yi - yj|。但他的绝对值经常干扰我们计算,我们可以把它转换成切比雪夫距离,具体原理可以看曼哈顿距离与切比雪夫距离的相互转化,结论就是：曼哈顿距离在坐标轴旋转 45 度后与切比雪夫距离等价。其中通过转轴公式,…

天天写惯了记忆化搜索,来个递推DP就老实了(已老实, 求放过) 这类问题用递推很简单, 但是记忆化就不行了, 主要是这类题目需要存取两个字符, 很容易爆内存, 但是用递推就很容易想,容易通过. 数组中最长的方波 1480 最长定差子序列 1597 最长等差数列 1759 找出有效子序列的最大长度 II ~1850 最长的斐波那契子序列的长度 191…

直径长度 def diameter(self, edges: List[List[int]]) -> int: g = [[] for _ in range(len(edges) + 1)] for x, y in edges: g[x].append(y) g[y].append(x) res = 0 # 用于存储树的直径 def dfs(…

Q：为什么灵茶山艾府喜欢用 Go 语言刷题？ A：我需要一个库函数丰富、有零拷贝切片、运行效率高且语法简单的语言，综合来看选了 Go。目前已基于 Go 实现了大部分竞赛算法，见 【算法竞赛模板库】 https://github.com/EndlessCheng/codeforces-go 【Go 语言相关资料】 快速入门 https://gobye…