【蓝桥杯】蓝桥杯算法复习（一）

😀大家好，我是白晨，一个不是很能熬夜😫，但是也想日更的人✈。如果喜欢这篇文章，点个赞👍，关注一下👀白晨吧！你的支持就是我最大的动力！💪💪💪

前言

---

本文适合有一定算法基础，但是由于各种原因已经很久没有敲代码的同学。本文以复习+练习为主，旨在通过练习算法题快速复习已经遗忘的算法。即使不是参加蓝桥杯的同学，如果符合上面的条件，依然可以参考本文进行复习。

如果你是新手，可以参考白晨的算法专栏进行学习。

---

蓝桥杯复习（一）

---

一、二分

---

复习

// 模板一
// 求满足check条件的最左下标
#include <iostream>using namespace std;template<class T>
int binary_search1(T* v, int l, int r)
{while (l < r){int mid = l + r >> 1;if (check(v[mid])) // check中 v[mid] 永远放在前面，eg. v[mid] >= ar = mid;elsel = mid + 1;}return mid;
}// 模板二
// 求满足check条件的最右下标
#include <iostream>using namespace std;template<class T>
int binary_search1(T* v, int l, int r)
{while (l < r){int mid = l + r + 1 >> 1; // 必须加一，避免死循环if (check(v[mid])) // eg.v[mid] <= al = mid;elser = mid - 1;}return mid;
}

练习

🍬题目链接：借教室

🍎算法思想：

由于题目中给出了n为$10^6$，也即百万级别，所以应该使用时间复杂度为O(n)或者O(mlogn)（m较小），所以就不能直接模拟。

此题使用了差分和二分的思想，差分这里简单提一下：

一维差分数组是一种处理区间修改和查询的方法，它可以在O(1)的时间内实现对原数组某个区间内所有元素加上一个常数。具体来说，如果原数组是a[]，差分数组是b[]，那么有以下关系：

• a[i] = b[1] + b[2] + … + b[i]
• b[i] = a[i] - a[i-1]

详细差分算法的介绍可见：【算法】算法基础入门详解

本题目订单为先来后到，并且订单都是正整数，所以每分配一个订单的教室，剩余的教室会越来越少，订单1到订单m具有单调性。所以将其转化为查找最多可以满足多少订单，这样就可以使用二分查找来确定能够处理的最大订单数量。在二分查找的过程中，将订单数量的上下界初始化为 0 和 m，然后在每次迭代中计算中间值 mid，并通过 check 函数来判断是否能够处理 mid 个订单。

要注意二分的模板分为两个，我们这次求得是满足check的最右下标，所以使用模板二。

🍊具体实现：

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;typedef long long LL;const int N = 1000010;int n, m;
int w[N];
int d[N], s[N], t[N];
LL b[N];bool check(int mid) 
{memset(b, 0, sizeof b);// 先差分，求出分配前mid订单后的差分数组for (int i = 1; i <= mid; ++i) {b[s[i]] += d[i];b[t[i] + 1] -= d[i];}// 判断此时是否满足条件LL cnt = 0;for (int i = 1; i <= n; ++i) {cnt += b[i];if (cnt > w[i]) return false;}return true;
}int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);for (int i = 1; i <= m; i ++ ) scanf("%d%d%d", &d[i], &s[i], &t[i]);// 求满足最多订单的订单编号int l = 0, r = m;while (l < r) {int mid = l + r + 1 >> 1;if (check(mid)) l = mid;else r = mid - 1;}if (r == m) printf("0");else printf("-1\n%d", r + 1);return 0;
}

---

二、前缀和

---

复习

前缀和是指：

如果有一个数组s[N]，那么其前缀和数组a[N]的定义为
$$a[i]=s[1]+s[2]+s[3]+...+s[i]$$
也即，前缀和就是数组s前i个数的总和，前缀和数组就是数组s前i个数的总和组成的数组。

有了这个数组，就可以以O(1)的时间复杂度算出s[l]~s[r]这段区间的总和：

$$\begin{gathered} sum(s[l:r])=a[r]-a[l-1] \\ =s[1]+...+s[l-1]+s[l]+...+s[r]-s[1]-...s[l-1] \\ =s[l]+...+s[r] \end{gathered}$$

练习

🍬题目链接：壁画

🍎算法思想：

这个题的要点是被毁掉的墙段一定只与一段还未被毁掉的墙面相邻，所以被毁掉的墙壁一定是边缘的，不能是中间的，如果是中间的，就与两段未毁掉的墙壁相邻了。

理解了这个以后，还有几个点比较重要：

1. 每天是先绘画，后毁坏，所以绘画的墙最后一定大于或等于被毁掉的墙；
2. 绘画的墙一定是连续的，这就给使用前缀和创造了条件。

所以绘画的墙壁数量为$\lceil \frac{n}{2}\rceil$，现在如果证明出所有$\lceil \frac{n}{2}\rceil$的连续墙壁都可以取到就可。

现在，假设我们有长度为 $n$ 的连续墙壁，考虑以下两种情况：

1. 如果 $n$ 是偶数，那么 $\lceil \frac{n}{2}\rceil =\frac{n}{2}$。在这种情况下，由于人有先手优势，第一个可以涂你选定的那一段中间两个随便一个，接下来，如果墙从左边被毁下一次就涂上一次刚才涂画的左边的墙进行涂画，反之右边被毁就选上一次刚才涂画的右边的墙进行涂画，就是按照对称的方式走，这样走结果必然可以将选定的一段涂完。
2. 如果 $n$ 是奇数，那么 $\lceil \frac{n}{2}\rceil =\frac{n+1}{2}$。在这种情况下，先涂选定的一段中间的墙，后面同上，如果墙从左边被毁下一次就涂上一次刚才涂画的左边的墙进行涂画，反之右边被毁就选上一次刚才涂画的右边的墙进行涂画，也可以保证一定能涂完。

因此，无论 $n$ 是偶数还是奇数，我们都可以选择任意一段 $\lceil \frac{n}{2}\rceil$ 个连续的墙壁进行涂色，所以问题转化为了求一段固定长度的连续区间的最大值，这里使用滑动窗口也可以做，但是今天复习的是前缀和，就拿前缀和做就可以了。

🍊具体实现：

#include <iostream>
#include <cstring>
#include <algorithm>const int N = 5000010;int t, n;
char s[N];
int a[N];int main()
{scanf("%d", &t); // 输入测试用例数量for (int i = 1; i <= t; ++i){scanf("%d", &n); // 输入字符串长度scanf("%s", s + 1); // 输入字符串int res = 0;int cnt = (n + 1) / 2; // 滑动窗口的大小，取n的一半向上取整for (int j = 1; j <= n; ++j) {a[j] = a[j - 1] + s[j] - '0'; // 计算前缀和，即当前位置之前的数字和if (j >= cnt) res = std::max(res, a[j] - a[j - cnt]); // 更新结果，保证滑动窗口内数字的和最大}printf("Case #%d: %d\n", i, res); // 输出结果}return 0;
}

---

三、差分

---

复习

一维差分数组是一种处理区间修改和查询的方法，它可以在O(1)的时间内实现对原数组某个区间内所有元素加上一个常数。具体来说，如果原数组是a[]，差分数组是b[]，那么有以下关系：

• a[i] = b[1] + b[2] + … + b[i]
• b[i] = a[i] - a[i-1]

详细差分算法的介绍可见：【算法】算法基础入门详解

练习

🍬题目链接：空调

🍎算法思想：

针对每个位置，计算初始温度和目标温度之间的差值 a，然后利用 insert 函数将这个差值插入到差分数组 b 中。这个函数用来更新差分数组，以便跟踪累积的变化。

据题意，将一段区间升高或者降低1度在差分数组中就是将一个位置的数+1，另一个位置的数-1（这里注意如果到总区间最后一个也要改变，则可以理解为将其中一个位置+1或-1即可）。

所以，要将差分数组变为全0，也就是要将差分数组中全部正数和负数都通过-1和+1的操作变为0。最小的操作次数为 正数之和 和 负数之和的绝对值 中的最大值。

🍊具体实现：

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 100010;int n;
int p[N], t[N];
int b[N];void insert(int e, int l, int r) 
{b[l] += e;b[r + 1] -= e;
}int main()
{scanf("%d", &n);for (int i = 1; i <= n; i++) scanf("%d", &p[i]);for (int i = 1; i <= n; i++) scanf("%d", &t[i]);for (int i = 1; i <= n; i++) {// 求温差int a = p[i] - t[i];insert(a, i, i);}int pos = 0, neg = 0;for (int i = 1; i <= n; ++i) {if (b[i] > 0) pos += b[i];else neg -= b[i];}printf("%d", max(pos, neg));return 0;
}

---

四、双指针

---

复习

练习

🍬题目链接：牛的学术圈 I

🍎算法思想：

依题意，h满足两个条件：

1. 引用次数最小为h - 1

2. 值为h - 1的文章数 <= L

所以，最好先将文章的引用次数从大到小排序，i代表h的枚举，j代表从右到左第一个大于等于i的数的下标，第一个条件非常好判断，只用每次枚举的时候判断第i个数是否大于等于i - 1，第二个条件可以在输入的时候就用哈希表统计出每个数出现的次数，也可以使用双指针判断。

本次使用双指针判断，j代表从右到左第一个大于等于i的数的下标，也即下标大于j的数都小于i，而i必须满足第一个条件，也即a[i] >= i - 1，所以当a[i] = i - 1时i - j的数就是值为i - 1的数的个数。

🍊具体实现：

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 100010;int n, L;
int a[N];int main()
{scanf("%d%d", &n, &L);for (int i = 1; i <= n; i++) scanf("%d", &a[i]);sort(a + 1, a + 1 + n, greater<int>()); // 从大到小排序int res = 0;for (int i = 1, j = n; i <= n; i++){while (j && a[j] < i) j--; // 找到从右到左第一个大于等于i的数的下标// 判断此时的i是否满足上面提到的两个条件if (a[i] >= i - 1 && i - j <= L) res = i;}printf("%d", res);return 0;
}

---

五、归并

---

复习

• 逆序对个数

🍬题目链接：逆序对的数量

// 逆序对个数#include <iostream>using namespace std;typedef long long ll;const int N = 100010;// 不开longlong见祖宗
int v[N], tmp[N];ll merge_sort(int v[], int l, int r)
{if (l >= r) return 0;int mid = l + r >> 1;ll res = merge_sort(v, l, mid) + merge_sort(v, mid + 1, r);int k = 0, i = l, j = mid + 1;while (i <= mid && j <= r){if (v[i] <= v[j])tmp[k++] = v[i++];else{tmp[k++] = v[j++];// 逆序对的个数res += mid - i + 1; // v[i,mid] 都可以与 v[j] 组成逆序对}}while (i <= mid) tmp[k++] = v[i++];while (j <= r) tmp[k++] = v[j++];// 往原数组中还原for (i = l, j = 0; i <= r; ++i, ++j){v[i] = tmp[j];}return res;
}int main()
{int n;cin >> n;for (int i = 0; i < n; ++i)cin >> v[i];cout << merge_sort(v, 0, n - 1) << endl;return 0;
}

练习

🍬题目链接：火柴排队

🍎算法思想：

首先，简化一下问题，一个升序的序列a[]和一个随机序列b[]，怎么调整第二个序列的顺序才能让$\sum (a_i-b_i{)}^2$最小，当然我们可以猜一下，当两个序列都是升序时，$\sum (a_i-b_i{)}^2$最小。

可以反证一下，当第二个序列不是升序时，必然存在$b_i>b_{i+1}$，此时得到的值为$(a_i-b_i{)}^2+(a_{i+1}-b_{i+1}{)}^2$，将其交换顺序可得，$(a_i-b_{i+1}{)}^2+(a_{i+1}-b_i{)}^2$，两者相减得到$2\ast (a_i-a_{i+1})(b_{i+1}-b_i)>0$，所以交换后得到的值小，所以第二个序列必须为升序序列。

其次，一个升序的序列a[]和一个随机序列b[]，最少要相邻交换多少次才能将b[]调整到升序？

b[]中逆序对的个数就是最少要相邻的次数。

因为相邻交换只会改变$b_i,b_{i+1}$之间的位置关系，并不会影响到$b_i,b_{i+1}$和其他数的位置关系，所以交换一次，要么就是逆序对的数量减一，要么就是逆序对的数加一（不存在相同的数）。所以，最小交换次数大于等于逆序对的个数。

在b[]中必然存在$b_i>b_{i+1}$，也即相邻的逆序对，如果不满足，那么b[]就是升序的，所以每次交换必然可以交换一对逆序对。这样就可以得到，最小交换次数等于逆序对的个数。

最后，回到原问题，如果是a[]不是升序序列，那么应该怎么办？

我们可以对a[]做一个映射，将其映射为升序序列，再以对a[]做的映射为规则，对b[]做映射，只用求出b[]中的逆序对数量，就是最小的交换次数。

但是，这里有一个问题，a[]和b[]的数不相同呀，怎么进行映射？由于本题目并不涉及数组中的具体值，只涉及到数组间的相对大小（逆序对），所以可以将其进行离散化，按照其数组中的相对大小将其离散化到1~10000上，这样就可以保证a[]和b[]可以相互映射。

🍊具体实现：

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 100010, mod = 99999997;int n;
int a[N], b[N];
int q[N], map[N];int merge_sort(int l, int r) 
{if (l >= r) return 0;int mid = l + r >> 1;int res = (merge_sort(l, mid) + merge_sort(mid + 1, r)) % mod;int i = l, j = mid + 1, k = 0;while (i <= mid && j <= r) {// 统计逆序对个数if (b[i] > b[j]) q[k++] = b[j++], res = (res + mid - i + 1) % mod;else q[k++] = b[i++];}while (i <= mid) q[k++] = b[i++];while (j <= r) q[k++] = b[j++];for (i = l, j = 0; i <= r; ++i, ++j) b[i] = q[j];return res;
}void handler(int t[])
{for (int i = 1; i <= n; ++i) q[i] = i;// 按照数组数据大小排下标，排到前面的是小数的下标sort(q + 1, q + n + 1, [&](int x, int y){return t[x] < t[y];});for (int i = 1; i <= n; ++i) t[q[i]] = i;
}int main()
{scanf("%d", &n);for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);// 离散化handler(a), handler(b);// 对a数组的数做映射，使其成为升序数组// 并按照此映射规则映射b数组for (int i = 1; i <= n; ++i) map[a[i]] = i;for (int i = 1; i <= n; ++i) b[i] = map[b[i]];// 现在只要求出b数组的逆序对数，就是最小交换次数printf("%d", merge_sort(1, n));return 0;
}

---

六、多路归并

---

复习

多路归并（Multiway Merge）是一种常用的排序算法，用于合并多个已经排序的序列。它通常被用作外部排序算法，特别是在处理大型数据集时。

在多路归并中，假设有 k 个已经排好序的序列，每个序列包含 n 个元素。该算法将这 k 个序列合并成一个排序好的序列。多路归并的基本思路是维护一个大小为 k 的堆，每次从堆中选择最小的元素输出，并从相应的序列中取出下一个元素放入堆中，直到所有序列中的元素都被输出。

多路归并的时间复杂度取决于输入序列的总长度以及序列的个数。如果输入序列的总长度为 N，序列的个数为 k，那么多路归并的时间复杂度为 O(N * log(k))。

练习

🍬题目链接：鱼塘钓鱼

🍎算法思想：

枚举+多路归并：

钓鱼真正的有效时间 = 总时间 - 在路上的时间，在路上的时间就是到第i个鱼池所用的时间，在一个鱼池钓到鱼的数量只与呆在这个鱼池的时间有关，而鱼池的鱼的数量不会随着时间进行恢复，所以可以在一个鱼池利益最大化以后再走，不需要回头。

可以枚举最远到达第i个鱼池，再求出在有效时间内，前i个鱼池最多可以钓多少鱼。由于每个鱼池每分钟可获得的鱼数只与在本鱼池呆的时间有关，所以在每个鱼池每分钟获得鱼的数量就是一个递减的序列，i个递减序列，要求有限时间内获得鱼的最大值，就直接使用多路归并的思想，从前i鱼池中每次选择获得鱼数最多的池子进行钓鱼，最后得到的就是在有效时间内，前i个鱼池最多可以钓到的鱼数。

🍊具体实现：

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 110;int n, t;
int a[N], d[N], w[N], s[N];// 求出此时第k个鱼池能获取的鱼数
int get(int k)
{return max(0, a[k] - d[k] * s[k]);
}int multi_merge(int k, int m)
{int res = 0;memset(s, 0, sizeof s);// 多路归并，求出前k个鱼池前m分钟的钓鱼的最大值for (int i = 1; i <= m; ++i) {int r = 1;// 直接循环求出最大值，如果是正规多路归并，应该使用堆，但是这里直接暴力循环也可以过for (int j = 2; j <= k; ++j) if (get(j) > get(r))r = j;res += get(r);s[r]++; //第r个鱼池呆的时长+1}return res;
}int main()
{scanf("%d", &n);for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);for (int i = 1; i <= n; ++i) scanf("%d", &d[i]);for (int i = 2; i <= n; ++i) {scanf("%d", &w[i]);w[i] += w[i - 1];}scanf("%d", &t);int res = 0;// 枚举最远到哪个鱼池for (int i = 1; i <= n; ++i) {// 求出前n个鱼池在t分钟内钓到最大鱼数// 钓鱼真正的有效时间 = t - 在路上的时间res = max(res, multi_merge(i, t - w[i]));}printf("%d", res);return 0;
}

---

七、贡献法

---

复习

贡献法就是计算每个元素对最终答案的贡献是多少，在枚举的过程中加起来。所以这类题目的关键是想到如何在枚举的过程中计算各个元素的贡献。

练习

🍬题目链接：孤独的照片

🍎算法思想：

贡献法+枚举+乘法原理：

枚举每一个字符为一段连续字符串中唯一的字符，如果我们能快速求出以此字符为唯一的字符串有多少个，就能快速求出要丢掉的照片有多少个。

统计每一个字符左右各有多少个连续的与自身不同字符的数量，例如

HGGGH
下标从1开始s[5]='H'，其左边有3个连续的G，l[5]=3，右边没有字符，r[5]=0
s[3]='G'，左边为G，没有连续的H，所以l[3]=0，同理r[3]=0  

有了这些数据以后，
$$以s[i]为唯一的字符串数量=l[i]\ast r[i]+max(l[i]-1,0)+max(r[i]-1,0)$$
也即左边连续的串和右边连续的串排列组合，可以拼成的串的数量，左(1…n)和右(1…n)组合以及只有左或者只有右。

🍊具体实现：

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 500010;typedef long long LL;int n;
char s[N];
// 统计s[i]左右各有多少个连续与s[i]不同的字符
int l[N], r[N];int main()
{scanf("%d", &n);scanf("%s", s + 1);// 从左统计s[i]的左侧有多少连续的与s[i]不同的字符，eg. HGGGH l[2]=1,l[5]=3 for (int i = 1, h = 0, g = 0; i <= n; ++i)if (s[i] == 'G') l[i] = h, h = 0, g++;else l[i] = g, g = 0, h++;// 从右统计s[i]的右侧有多少连续的与s[i]不同的字符，eg. HGGGH r[1]=3,r[4]=1 for (int i = n, h = 0, g = 0; i >= 1; --i)if (s[i] == 'G') r[i] = h, h = 0, g++;else r[i] = g, g = 0, h++;LL res = 0;for (int i = 1; i <= n; ++i) res += (LL)l[i] * r[i] + max(l[i] - 1, 0) + max(r[i] - 1, 0);printf("%lld", res);return 0;
}

---