网站开发需求书,北京精兴装饰公司,专门网站建设,邢台#x1f600;大家好#xff0c;我是白晨#xff0c;一个不是很能熬夜#x1f62b;#xff0c;但是也想日更的人✈。如果喜欢这篇文章#xff0c;点个赞#x1f44d;#xff0c;关注一下#x1f440;白晨吧#xff01;你的支持就是我最大的动力#xff01;#x1f4…大家好我是白晨一个不是很能熬夜但是也想日更的人✈。如果喜欢这篇文章点个赞关注一下白晨吧你的支持就是我最大的动力 文章目录 前言蓝桥杯复习一一、二分复习练习 二、前缀和复习练习 三、差分复习练习 四、双指针复习练习 五、归并复习练习 六、多路归并复习练习 七、贡献法复习练习 前言 本文适合有一定算法基础但是由于各种原因已经很久没有敲代码的同学。本文以复习练习为主旨在通过练习算法题快速复习已经遗忘的算法。即使不是参加蓝桥杯的同学如果符合上面的条件依然可以参考本文进行复习。
如果你是新手可以参考白晨的算法专栏进行学习。 蓝桥杯复习一 一、二分 复习
// 模板一
// 求满足check条件的最左下标
#include iostreamusing namespace std;templateclass 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 iostreamusing namespace std;templateclass 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为 1 0 6 10^6 106也即百万级别所以应该使用时间复杂度为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 algorithmusing 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 ] a[i] s[1]s[2]s[3]...s[i] a[i]s[1]s[2]s[3]...s[i] 也即前缀和就是数组s前i个数的总和前缀和数组就是数组s前i个数的总和组成的数组。 有了这个数组就可以以O(1)的时间复杂度算出s[l]~s[r]这段区间的总和 s u m ( 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 ] 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] 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] 练习 题目链接壁画
算法思想
这个题的要点是被毁掉的墙段一定只与一段还未被毁掉的墙面相邻所以被毁掉的墙壁一定是边缘的不能是中间的如果是中间的就与两段未毁掉的墙壁相邻了。
理解了这个以后还有几个点比较重要
每天是先绘画后毁坏所以绘画的墙最后一定大于或等于被毁掉的墙绘画的墙一定是连续的这就给使用前缀和创造了条件。
所以绘画的墙壁数量为 ⌈ n 2 ⌉ \lceil \frac{n}{2} \rceil ⌈2n⌉现在如果证明出所有 ⌈ n 2 ⌉ \lceil \frac{n}{2} \rceil ⌈2n⌉的连续墙壁都可以取到就可。
现在假设我们有长度为 n n n 的连续墙壁考虑以下两种情况
如果 n n n 是偶数那么 ⌈ n 2 ⌉ n 2 \lceil \frac{n}{2} \rceil \frac{n}{2} ⌈2n⌉2n。在这种情况下由于人有先手优势第一个可以涂你选定的那一段中间两个随便一个接下来如果墙从左边被毁下一次就涂上一次刚才涂画的左边的墙进行涂画反之右边被毁就选上一次刚才涂画的右边的墙进行涂画就是按照对称的方式走这样走结果必然可以将选定的一段涂完。如果 n n n 是奇数那么 ⌈ n 2 ⌉ n 1 2 \lceil \frac{n}{2} \rceil \frac{n1}{2} ⌈2n⌉2n1。在这种情况下先涂选定的一段中间的墙后面同上如果墙从左边被毁下一次就涂上一次刚才涂画的左边的墙进行涂画反之右边被毁就选上一次刚才涂画的右边的墙进行涂画也可以保证一定能涂完。
因此无论 n n n 是偶数还是奇数我们都可以选择任意一段 ⌈ n 2 ⌉ \lceil \frac{n}{2} \rceil ⌈2n⌉ 个连续的墙壁进行涂色所以问题转化为了求一段固定长度的连续区间的最大值这里使用滑动窗口也可以做但是今天复习的是前缀和就拿前缀和做就可以了。
具体实现
#include iostream
#include cstring
#include algorithmconst 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 algorithmusing 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满足两个条件 引用次数最小为h - 1 值为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 algorithmusing 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, greaterint()); // 从大到小排序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 iostreamusing 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[]怎么调整第二个序列的顺序才能让 ∑ ( a i − b i ) 2 \sum(a_i -b_i)^2 ∑(ai−bi)2最小当然我们可以猜一下当两个序列都是升序时 ∑ ( a i − b i ) 2 \sum(a_i -b_i)^2 ∑(ai−bi)2最小。
可以反证一下当第二个序列不是升序时必然存在 b i b i 1 b_ib_{i1} bibi1此时得到的值为 ( a i − b i ) 2 ( a i 1 − b i 1 ) 2 (a_i-b_i)^2(a_{i1}-b_{i1})^2 (ai−bi)2(ai1−bi1)2将其交换顺序可得 ( a i − b i 1 ) 2 ( a i 1 − b i ) 2 (a_i-b_{i1})^2(a_{i1}-b_{i})^2 (ai−bi1)2(ai1−bi)2两者相减得到 2 ∗ ( a i − a i 1 ) ( b i 1 − b i ) 0 2*(a_i-a_{i1})(b_{i1}-b_{i})0 2∗(ai−ai1)(bi1−bi)0所以交换后得到的值小所以第二个序列必须为升序序列。
其次一个升序的序列a[]和一个随机序列b[]最少要相邻交换多少次才能将b[]调整到升序 b[]中逆序对的个数就是最少要相邻的次数。 因为相邻交换只会改变 b i , b i 1 b_i,b_{i1} bi,bi1之间的位置关系并不会影响到 b i , b i 1 b_i,b_{i1} bi,bi1和其他数的位置关系所以交换一次要么就是逆序对的数量减一要么就是逆序对的数加一不存在相同的数。所以最小交换次数大于等于逆序对的个数。
在b[]中必然存在 b i b i 1 b_ib_{i1} bibi1也即相邻的逆序对如果不满足那么b[]就是升序的所以每次交换必然可以交换一对逆序对。这样就可以得到最小交换次数等于逆序对的个数。
最后回到原问题如果是a[]不是升序序列那么应该怎么办
我们可以对a[]做一个映射将其映射为升序序列再以对a[]做的映射为规则对b[]做映射只用求出b[]中的逆序对数量就是最小的交换次数。
但是这里有一个问题a[]和b[]的数不相同呀怎么进行映射由于本题目并不涉及数组中的具体值只涉及到数组间的相对大小逆序对所以可以将其进行离散化按照其数组中的相对大小将其离散化到1~10000上这样就可以保证a[]和b[]可以相互映射。
具体实现
#include iostream
#include cstring
#include algorithmusing 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 algorithmusing 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个连续的Gl[5]3右边没有字符r[5]0
s[3]G左边为G没有连续的H所以l[3]0同理r[3]0 有了这些数据以后 以 s [ i ] 为唯一的字符串数量 l [ i ] ∗ r [ i ] m a x ( l [ i ] − 1 , 0 ) m a x ( r [ i ] − 1 , 0 ) 以s[i]为唯一的字符串数量 l[i]*r[i]max(l[i]-1,0)max(r[i]-1,0) 以s[i]为唯一的字符串数量l[i]∗r[i]max(l[i]−1,0)max(r[i]−1,0) 也即左边连续的串和右边连续的串排列组合可以拼成的串的数量左(1…n)和右(1…n)组合以及只有左或者只有右。
具体实现
#include iostream
#include cstring
#include algorithmusing 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;
}
