倍增（也叫二分倍增）通常被叫做“树上倍增”，是因为这种方法最初用于树形结构中，特别是在树的上升路径查询、LCA（最近公共祖先）问题等场景中非常有效。在树上倍增的过程中，树的结构天然适合这种操作，因为树是无环的，且每个节点的父节点可以通过倍增逐步上升，直到找到需要的节点或信息。 对于树上的倍增，最常见的应用是处理树中节点到根节点的路径，或者查询某个节…

单调栈我的痛点，不像模板类那样直接套用即可，更多地像贪心一样捉摸不定。 求最短 https://leetcode.cn/problems/next-greater-element-i/description/ class Solution: def nextGreaterElement(self, nums1: List[int], nums2: …

http://blog.csdn.net/ac_gibson/article/details/41624623 一. 巴什博奕（Bash Game）： A和B一块报数，每人每次报最少1个，最多报4个，看谁先报到30。这应该是最古老的关于巴什博奕的游戏了吧。 其实如果知道原理，这游戏一点运气成分都没有，只和先手后手有关，比如第一次报数，A报k个数，那…

MOD = 1_000_000_007 # a @ b，其中 @ 是矩阵乘法 def mul(a: List[List[int]], b: List[List[int]]) -> List[List[int]]: return [[sum(x * y for x, y in zip(row, col)) % MOD for col in zi…

O(n)时间处理查询回文串问题 # 将 dfsStr 改造为 t，这样就不需要讨论 n 的奇偶性，因为新串 t 的每个回文子串都是奇回文串（都有回文中心） # dfsStr 和 t 的下标转换关系： # (dfsStr_i+1)*2 = ti # ti/2-1 = dfsStr_i # ti 为偶数，对应奇回文串（从 2 开始） # ti 为奇数，…

字符串哈希, 一般都是写困难题的, 学会上大分. 同类型的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(…

状态压缩是一种常用于动态规划问题的技术，尤其适用于解决涉及多个状态的组合问题。它通过使用一个整数的位表示多个状态，从而大幅降低空间和时间复杂度。 状态压缩是用二进制进行压缩的,你需要了解位运算的基本运用:从集合论到位运算,当我们遇到处理数据很小的时候,比如n<20以内,可以考虑下状压。其中状压dp有相邻相关,相邻无关等类型，下面我会概述一下这…