枚举算法

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

问题分类：

  • 是否存在 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的位置分别进行异或

然后进行一次前缀异或和

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

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

等差数列的累加，多重差分再进行两次前缀和

3 5 7 9 11 0 0
3 2 2 2 2 -11 0
3 -1 0 0 0 -13 11

规律： dL = a0; dL+1 = -a0 + d;

​ dR+1 = -a0 + d; dR+2 = a0 + d(n - 1);

多项式累加=>多重差分

addx = a + bx + cx^2 + dx^3 + ...

最高项加一次数的差分，再通过前缀和还原

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

  • 如果差分数组都是正数，原数组一定单调递增
  • 如果差分数组都是负数，原数组一定单调递减
  • 如果差分数组都是0，原数组一定是相同的元素

选择[L, R]让元素增加或减少 == 让差分数组的某一个位置一个加，一个减

数组变得递增，递减，相等 数组变成正数，负数，零

差分数组第一个位置和越界R+1位置不影响原数组增减性，因此任选一个位置加减进行操作可以实现目标

单调性枚举

Leetcode 209 单调递增枚举

给定一个含有 n 个正整数的数组和一个正整数 target
找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释:：子数组 [4,3] 是该条件下的长度最小的子数组。

朴素做法：枚举左端点和右端点，然后计算区间的和，比较并记录答案 -> O(n^3)
即使用前缀和优化，枚举两个点仍然需要O(n^2)

![[lc209.png]]

由图片不能发现，当[l, r]区间已经符合条件时有：
[l - 1, r]一定不是解 -> 即答案左边区间都不符合
[l, r + 1]一定不是更优解 -> 即答案右边区间都不符合
符合条件的下一个r一定大于或等于上一个r，因此枚举r可直接从上一个r开始枚举，而不是从i开始

由此当枚举到符合的右端点时可直接break，随后继续枚举左端点

1
2
3
4
5
6
7
8
9
10
11
vector<int> rightIndex(n);
for (int l = 0; l < n; l ++){
	int r = l == 0 ? 0 : rightIndex[l - 1];
	for( ; r < n; r ++){
		if(getSum(l, r) >= target){
			ans = min(ans, r - l + 1);
			break;
		}
	}
	rightIndex[l] = r;
}

优化，保证r不被重置，这样每次枚举右端点就可以自动从上次进行了

1
2
3
4
5
6
7
8
for(int l = 0, r = 0; l < n; l ++){
	for(; r < n; r ++){
		if (getSum(l, r) >= target){
			ans = min(ans, r - l + 1);
			break;
		}
	}
}

再进一步，不需要前缀和，在枚举时维护区间的关键值并判断其是否符合条件

1
2
3
4
5
6
7
8
int sum = 0;
for(int l = 0, r = 0; l < n; ){
	if(r < n && sum < target) sum += arr[r ++];
	else {
		if(sum >= target) ans = min(ans, r - l);
		sum -= arr[l ++];
	}
}

**滑动窗口：区间求和；时间、数轴的窗口、包含关系

公式化： 关键值，条件，维护，更新

  • 判断是否满足条件
  • r往后移动（添加一个元素），如何维护区间关键值
  • l往后移动（删除一个元素），如何维护区间关键值
  • 找到满足条件的区间时，如何更新答案

二元组满足条件的最小值，单调递增

**match判断是否匹配的条件

**insert, remove增加右端点和删除左端点时对关键信息的维护

update找到满足条件的区间时，如何更新答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<typename M, typename I, typename R, typename U>
void increaseEnumerate(int s, int e, const M& match,
const I& insert, const R& remove, const U& update){
	for (int l = s, r = s; l <= e; ) {
	    if (l < r && match(l, r - 1)) {
	        update(l, r - 2);
	        remove(l ++, r);
	    } else if (r <= e) {
	        insert(l, r++);
	    } else {
	        update(l, r - 1);
	        remove(l ++, r);
	    }
	}
}

此题用模板示例：

1
2
3
4
5
6
7
8
auto m = [&](int l, int r){ return sum >= target;};
  auto i = [&](int l, int r){ sum += nums[r];};
  auto r = [&](int l, int r){ sum -= nums[l];};
  auto u = [&](int l, int r){
    if(r + 1 == n) return;
    ans = min(ans, r - l + 2);
  };
  increaseEnumerate(0, n - 1, m, i, r, u);

Leetcode 3

Leetcode 611

Leetcode 167

总结

  • 单调递增枚举：二元组满足条件的最小值，单调递增
  • 单调递减枚举：二元组满足条件的最小值，单调递减
  • 四类求值：最小满足，最大不满足，满足/不满足的方案数
  • 公式化：关键值，条件，维护，更新
  • 单调性剪枝：左边或下边比当前“差”，不用枚举

单调双端队列