资料来源:
算法竞赛进阶指南
活动 - AcWing
1、倍增
倍增:"成倍增长",指进行递推时,如果状态空间很大,通常的线性递推无法满足时间和空间复杂度的要求,就可以通过成倍增长的方式,只递推状态空间中在2的整数次幂位置上的值作为代表。当需要其他位置上的值时,通过"任意整数可以表示成若干个2的次幂项的和"这一性质,使用之前求出的代表值拼成所需的值。所以使用倍增算法也要求递推的问题的状态空间关于2的次幂具有可划分性。
倍增思想与二进制划分思想相互结合,可以降低求解很多问题的时间和空间复杂度。例如:“快速幂”
//求 m^ k mod p,时间复杂度 O(logk)。int qmi(int m, int k, int p) {int result = 1;int t = m;while (k){if (k & 1)result = result * t % p;t = t * t % p;k >>= 1;}return result; }
1.1 问题一
给定一个长度为N的数列A,进行若干次询问,每次给定一个整数T,求出最大的k,满足,你的算法必须时在线的(必须即时回答每一个询问,不能等待收到所有询问后再统一处理),假设。
朴素做法:
从前向后枚举k位,最坏情况位O(N) 。
前缀和+二分:
O(N)处理前缀和,每次询问通过二分比较S[k]与T的大小来确定二分上下界的变化,每次询问花费的时间都是O(log N)。
平均情况下该算法很好,但缺点就是如果每次询问给定的整数T都非常小,造成答案k也非常小,那么该算法可能还不如从前向后枚举更优。
前缀和+倍增算法:
- 令p=1,k=0,sum=0
- 比较“A数组中k之后的p个数的和”与T的关系,也就是说,如果sum+S[k+p]-S[k]<=T,则令sum+=S[k+p]-S[k],k+=p,p*=2,即累加上这p个数的和,然后把p的跨度增长一倍。如果sum+S[k+p]-S[k]>T,则令 p/=2
- 重复上一步,直到p的值变为0,此时k就是答案
通过若干个长度为2次幂的区间拼成最后的k,时间复杂度级别为答案的对数,能够应对T的各种大小情况。
#include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int N = 1e6 + 10; LL S[N];//前缀和 int n,m;//n为数组个数,m表示询问次数int main() {cin >> n >> m;for(int i = 1; i <= n; i++){int a;cin >> a;S[i] = S[i - 1] + a;}while(m--){int t;cin >> t;int p = 1, k = 0, sum = 0; //A数组中k之后的p个数的和while(p) //p为0结束{//注意越界问题if(k + p <= n && sum + S[k+p] - S[k] <= t)sum += S[k+p] - S[k], k = k + p <= n ? k + p : n, p *= 2;else //sum + S[k+p] - S[k] > tp /= 2;}cout << k << endl;}return 0; }
1.2 题目 -- 天才ACM
109. 天才ACM - AcWing题库
思路:
- 对于一个集合S,显然应该取S中最大的M个数和最小的M个数,最大和最小的构成一对,次大和次小构成一对...这样求得的"校验值"最大。
- 求校验值需要进行排序,选取其中最大和最小分别M个值进行计算。
- 为了让数列A分成的段数最少,每一段都应该在"校验值"不超过T的情况下,尽量包含更多的数,所以从头开始对A进行分段,让每一段尽量长,到达结尾时分成的段数就是答案。
- 转化问题为:当确定一个左端点L之后,右端点R在满足A[L]~A[R]的"校验值'不超过T的前提下,最大能取到多少。
- 求某一段的"校验值"需要排序配对,时间复杂度为O(N log N)
- 利用倍增算法:
令p=1,R=L
求出[L,R+p]区间的"校验值",若"校验值"<=T,则R += p,p *= 2;否则,p /= 2
重复上一步,直到p的值为0,此时R即为所求。
上述过程至多循环O(log N)次,每次循环需要排序,完成整个题目的求解累计扩展长度为N,所以总体时间复杂度为。可以通过归并排序,只对新增的长度部分排序,然后合并新旧两端,这样总体时间复杂度降低到O(N log N)。#include <iostream> #include <algorithm>using namespace std;typedef long long ll;const int N = 500005;int n, m; int ans; ll T; ll w[N], t[N]; ll tmp[N];ll sq(ll x) {return x * x; }bool check(int l, int mid, int r) // 判断区间 [l, r) 是否合法,并将 t 中的 [l, mid) 区间和 [mid, r) 区间合并到 tmp 中 {for (int i = mid; i < r; i ++ ) // 将 w 数组的 [l, r) 区间复制到 t 的 [l, r) 区间中t[i] = w[i];sort(t + mid, t + r); // 将 t 的 [mid, r) 排序int i = l, j = mid, k = 0; // 双指针进行区间合并while (i != mid && j != r) // 当 i 不到 mid 且 j 不到 r 时,执行循环if (t[i] < t[j]) // 如果 t[i] 比 t[j] 小,那么将 t[i] 放入 tmp 中tmp[k ++ ] = t[i ++ ]; else // 否则将 t[j] 放入 tmp 中tmp[k ++ ] = t[j ++ ];while (i != mid) tmp[k ++ ] = t[i ++ ]; // 处理剩下的元素while (j != r) tmp[k ++ ] = t[j ++ ];ll sum = 0; // 计算校验值for (i = 0; i < m && i < k; i ++ , k -- )sum += sq(tmp[i] - tmp[k - 1]);return sum <= T; // 返回当前区间 [l, r) 是否合法 }int main() {int K;scanf("%d", &K);while (K -- ){scanf("%d %d %lld\n", &n, &m, &T);for (int i = 0; i < n; i ++ )scanf("%lld", &w[i]);ans = 0;int len;int start = 0, end = 0;while (end < n){len = 1;while (len){if (end + len <= n && check(start, end, end + len)) // 如果 w 的 [start, end + len) 区间合法{end += len, len <<= 1;if (end >= n) break ; // 一个小剪枝,如果 end >= n,那么直接跳出for (int i = start; i < end; i ++ ) // 在 check 时,已经将 t 数组的 [start, end + len) 这段区间归并在 tmp 中了。现在只需要将 tmp 中的有序数组复制到 t 中即可t[i] = tmp[i - start]; // 复制的时候注意下标变换,tmp 是从 0 开始存的,t 是从 start 开始存的}else len >>= 1;}start = end;ans ++ ;}printf("%d\n", ans);}return 0; }
2、ST算法
在区间最值问题(RMQ)中,ST算法就是倍增的产物。给定一个长度为N的数列A,ST算法能在O(N log N)时间的预处理后,以O(1)的时间复杂度在线回答"数列A中下标在"l~r"之间的数的最值是多少"。
设F[i,j]表示数列A中下标在子区间[i,i + 2^j - 1]里的数的最大值,也就是从i开始的2^j个数的最大值。递推边界显然是F[i,0] = A[i],即数列A在子区间[i,i]里的最大值。
在递推时,把子区间的长度成倍增长,有公式:,即长度为2^j的子区间的最大值是左右两半长度为2^(j-1)的子区间的最大值中较大的一个。void ST_prework() {for(int i = 1; i <= n; i++)f[i][0] = a[i];int t = log(n) / log(2) + 1; //利用对数换底公式,将底数e换成2;for(int j = 1; j < t; j++)for(int i = 1; i <= n - (1 << j) + 1; i++)f[i][j] = max(f[i][j-1],f[i + (1<<(j-1))][j-1]); }
当询问任意区间[l,r]的最值时,需要先计算一个k,满足,使2的k次方小于区间长度的前提下最大的k,那么“从l开始的2^k个数”和“以r结尾的2^k个数”这两段覆盖了整个[l,r],这两段的最大值分别是F[l,k]和F[r-2^k+1,k],二者中较大的那个就是整个区间[l,r]的最值。
int ST_query(int l, int r) {int k = log(r - l + 1) / log(2); //对数换底:log 2 (r - l + 1)return max(f[l][k],f[r - (1 << k) + 1][k]); }