枚举算法

定义：在某个可能的解的集合中，按某个顺序依次检索元素，用题目给定的条件进行校验或计算

问题分类：

  • 是否存在 any of
  • 找到第n个 find if / all of / none of
1
2
//stl中也有对应函数，只需要自己写条件即可
any_of(arr.begin(), arr.end(), [](int x){ return x & 1; });//all_of,none_of同理

stl提供了很多枚举函数any of all_of none_of find_if max_element min_element accumulate

子串转化：寻找子数组等于目标

无限集枚举：初始化关键信息，再无限集中枚举，维护关键信息，关键信息符合条件时停止

枚举的优化：裁剪枚举集

前缀和

前缀和基础

定义：表示从开头到当前位置所有元素的和，通过两处前缀和相加来获得区间和

公式： sum(L, R) = prefix[R] - prefix[L - 1]

满足结合律，且存在可逆运算时可以推广到其他运算中：前缀积，前缀异或

前缀积

公式：mul(L, R) = prefix[R] / prefix[L - 1]

注意前缀积不要溢出，但是前缀积在计算过程中很容易变得很大，因此为了避免高精度的运算，通常会对结果进行取模 prefix[i] = (prefix[i] * arr[i]) % mod 但是此时他的逆运算就不是除法那么简单 —> 乘法逆元（费马小定理 快速幂）

前缀异或

公式：xor(L, R) = prefix[R] ^ prefix[L- 1]

1
2
3
4
partial_sum(arr.begin(), arr.end(), xorsum.begin(),
           [](int prev, int cur){
              return prev ^ cur; 
           });

二维前缀

计算方法：先对行进行前缀和计算，再对列进行前缀和计算

当前元素表示从左上角到当前位置所有元素的和，求某个子矩阵的和

左上 上
x x
左 x 目标元素

计算目标子矩阵（图中2x2矩阵，可推广至大矩阵）公式：

目标 - 左 - 上 + 左上 —> 容斥原理（可扩展到三维甚至更高维度的前缀和）

差分

基础

差分是用于快速处理区间加减的算法，它是前缀和的逆运算

差分表示后一个元素减去前一个元素，也就是当前位置元素减去前一个元素（i = 0时即ai）

可调用stl中的adjacent_difference(a.begin(), a.end(), d.begin());

而手动遍历时记得从后往前遍历，避免覆盖

性质

对[l, r]区间的每一个元素都加k <=> 对差分数组l的位置加k，r+1的位置减k（r+1会越界，可以多开一个位置），再进行一次前缀和运算得到目标数组

a[l, r] + k <=> d[l] + k , d[r + 1] - k

二维差分

计算方法：先计算每一列的差分，再计算每一行的差分

公式：当前元素 - 左 - 上 + 左上
（x1, y1） - -
- - -
- - (x2, y2)

对（x1, y1）到（x2，y2）的区间矩阵元素进行加减操作（例如+k）
（x1, y1） + k - - -k
- - -
- - (x2, y2)
-k +k

也可以根据容斥原理推广到三维甚至更高维的差分算法

扩展

适用于前缀和的运算也适用差分，例如异或，乘法取模

对原数组某一个位置进行异或某个值，等价于对l和r+1的位置分别进行异或

然后进行一次前缀异或和

乘法取模也类似，但计算时需要用到乘法逆元

有规律的差分=> 多重差分

多项式累加=>多重差分

差分正负性=>原数组增减性

单调性枚举

单调双端队列