行业知识
【蓝桥杯】蓝桥杯算法复习(一)
2026-11-20 21:52:09
来源:互联网转载
大家好,���是白晨,一个不是很能熬夜,但是也想日更的人✈。如果喜欢这篇文章,点个赞,关注一下白晨吧!你的支持就是我最大的动力!
文章目录
- 前言
- 蓝桥杯复习(一)
- 一、二分
- 复习
- 练习
- 二、前缀和
- 复习
- 练习
- 三、差分
- 复习
- 练习
- 四、双指针
- 复习
- 练习
- 五、归并
- 复习
- 练习
- 六、多路归并
- 复习
- 练习
- 七、贡献法
- 复习
- 练习
前言
本文适合有一定算法基础,但是由于各种原因已经很久没有敲代码的同学。本文以复习+练习为主,旨在通过练习算法题快速复习已经遗忘的算法。即使不是参加蓝桥杯的同学,如果符合上面的条件,依然可以参考本文进行复习。
如果你是新手,可以参考白晨的算法专栏进行学习。
蓝桥杯复习(一)
一、二分
复习
// 模板一// 求满足check条件的最左下标#include using namespace std;templateint binary_search1(T* v, int l, int r){while (l > 1;if (check(v[mid])) // check中 v[mid] 永远放在前面,eg. v[mid] >= ar = mid;elsel = mid + 1;}return mid;}// 模板二// 求满足check条件的最右下标#include using namespace std;templateint binary_search1(T* v, int l, int r){while (l > 1; // 必须加一,避免***循环if (check(v[mid])) // eg.v[mid] memset(b, 0, sizeof b); // 先差分,求出分配前mid订单后的差分数组 for (int i = 1; i b[s[i]] += d[i]; b[t[i] + 1] -= d[i]; } // 判断此时是否满足条件 LL cnt = 0; for (int i = 1; i cnt += b[i]; if (cnt w[i]) return false; } return true;}int main(){ scanf("%d%d", &n, &m); for (int i = 1; i 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;} scanf("%d", &t); // 输入测试用例数量 for (int i = 1; i scanf("%d", &n); // 输入字符串长度 scanf("%s", s + 1); // 输入字符串 int res = 0; int cnt = (n + 1) / 2; // 滑动窗口的大小,取n的一半向上取整 for (int j = 1; 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;} b[l] += e; b[r + 1] -= e;}int main(){ scanf("%d", &n); for (int i = 1; i // 求温差 int a = p[i] - t[i]; insert(a, i, i); } int pos = 0, neg = 0; for (int i = 1; i if (b[i] 0) pos += b[i]; else neg -= b[i]; } printf("%d", max(pos, neg)); return 0;} scanf("%d%d", &n, &L); for (int i = 1; i while (j && a[j]最后,回到原问题,如果是a[]不是升序序列,那么应该怎么办?
我们可以对a[]做一个映射,将其映射为升序序列,再以对a[]做的映射为规则,对b[]做映射,只用求出b[]中的逆序对数量,就是最小的交换次数。
但是,这里有一个问题,a[]和b[]的数不相同呀,怎么进行映射?由于本题目并不涉及数组中的具体值,只涉及到数组间的相对大小(逆序对),所以可以将其进行离散化,按照其数组中的相对大小将其离散化到1~10000上,这样就可以保证a[]和b[]可以相互映射。
具体实现:
#include #include #include 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 // 统计逆序对个数 if (b[i] b[j]) q[k++] = b[j++], res = (res + mid - i + 1) % mod; else q[k++] = b[i++]; } while (i for (int i = 1; i return t[x]
上一篇:连接家用服务器怎么连接?
下一篇:服务器购买之后怎么办?