结论

[Wizmann]

Table of Contents

• 基础数学
• 组合数学
• 基础算法
  • 尺取法
• 单调队列
• 动态规划
  • 动态规划的优化
• 图论
  • 树
• 解题思路
• 偷鸡摸狗
  • 位运算相关

基础数学

• 平方和公式：n * (n + 1) * (2n + 1) / 6
• 大于3的所有质数都可以表示为 6n - 1 或 6n + 1 (n >= 1)

组合数学

• 隔板法
  • N个球，M个盒子，不允许空盒子
    • 问题等价于求x1 + x2 + x3 ... xM =N (xi > 0) 的可行解数
    • C(N - 1, M - 1)
  • N个球，M个盒子，允许空盒子
    • C(N + M - 1, M - 1)

基础算法

尺取法

• 用来处理单调性区间问题的一种方法
• 相比于同样处理单调性问题的二分法，可以降低复杂度
• 例题1：Leetcode 1521. Find a Value of a Mysterious Function Closest to Target
  因为a[0] & a[1] & a[2]...的结果是单调不增的，所以可以使用尺取法求出与target值相近的区间

单调队列

• 一般用于处理连续元素的区间最值问题
• 维护一个递增（或递减）的队列，队列中的每个元素A[i]与其左右相邻元素<A[i - 1], A[i + 1]>，代表着一个最值区间
  • 意为A[i]所代表的元素，在开区间(A[i - 1], A[i + 1])中是一个最值
• 可以使用双端队列处理滑动窗口问题
• 例题
  • Leetcode 84. Largest Rectangle in Histogram
  • Leetcode 1793. Maximum Score of a Good Subarray

动态规划

• 解决无后效问题，重点是找到状态，以及状态之间的转移
• 同时要注意时间复杂度和空间复杂度

动态规划的优化

• 前辍和（前辍最大值/最小值）优化
  • 例题1：Leetcode 1872. Stone Game VIII
• 单调队列优化
  • 例题1：Leetcode 1687. Delivering Boxes from Storage to Ports
• etc.

图论

树

• 换根DP
• 树上的差分DP
  • 例题1：AtCoder Beginner Contest 202E - Count Descendants
    使用差分DP来统计每个子树对应的信息。避免DFS中申请额外的空间。

解题思路

• 缩小解的范围
  • 二分
  • 缩小上下界
    • 例题1：Leetcode 1674. Minimum Moves to Make Array Complementary
      下界的缩小范围和操作次数是有限的。所以缩小下界来推测上界。
• 从结论出发反推解法

偷鸡摸狗

位运算相关

• 对于区间xor，可以使用前辍和进行加速
• 对于区间and/or，可以考虑其值域会非常小，最多32步/64步就可以把所有bit位填成0/1
  • 例题1：Leetcode 1521. Find a Value of a Mysterious Function Closest to Target