恩阳建设局网站,在大网站做网页广告需要多少钱,企业网站建设需要提供什么材料,福州企业如何建网站#x1f600;大家好#xff0c;我是白晨#xff0c;一个不是很能熬夜#x1f62b;#xff0c;但是也想日更的人✈。如果喜欢这篇文章#xff0c;点个赞#x1f44d;#xff0c;关注一下#x1f440;白晨吧#xff01;你的支持就是我最大的动力#xff01;#x1f4…大家好我是白晨一个不是很能熬夜但是也想日更的人✈。如果喜欢这篇文章点个赞关注一下白晨吧你的支持就是我最大的动力 文章目录前言算法基础一、快速排序二、归并排序三、二分算法四、高精度算法五、前缀和与差分六、双指针算法七、位运算八、离散化九、区间合并后记前言 大家好呀我是白晨这段时间身边的人挺多的白晨就老老实实在家摸鱼真不是有意拖更的bushi。本次白晨想要分享的是新手学习必会的几种基础算法由于这篇文章是新手向的所以白晨这次对于算法思想尽量讲解的细致生动代码实现尽量简洁易懂同时我会贴上练习算法的题目链接大家看完算法思路一定要自己去动手敲一遍争取能把基础算法背下来。
算法的代码风格是偏向于快速实用的没有像工程向代码一样严谨缜密、缩进和换行严格要求两种代码风格各有优势本篇文章大多数算法代码采用算法风格。
本篇文章内容分享的算法有
快速排序归并排序二分算法高精度算法前缀和与差分双指针算法位运算离散化区间合并 算法基础 一、快速排序 快速排序是一种高效且使用广泛的排序算法。它的基本思想是选取一个记录作为枢轴经过一趟排序将整段序列分为两个部分其中一部分的值都小于枢轴另一部分都大于枢轴。然后再对左右区间重复这个过程直到各区间只有一个数。 实现快速排序算法的关键在于先在待排序的数组中选择一个数字作为枢轴然后把数组中的数字分成两部分比枢轴小的数字移动到数组的左边比枢轴大的数字移动到数组的右边之后用递归的思路分别对左右两边进行排序。 下面用两道例题带领大家快速理解掌握快速排序 题目链接快速排序
算法思想 快速排序的通用思路 选择一个枢轴元素通常选择数组的第一个元素或者中间的元素。将数组中小于枢轴元素的值移动到它的左边将大于枢轴元素的值移动到它的右边。对枢轴元素左右两边的子数组递归执行步骤1和2直到子数组只剩下一个元素。 模板快速实现详解 定义 quick_sort 函数接受数组指针、左边界和右边界作为参数。在 quick_sort 函数中首先判断左右边界是否合法如果不合法则直接返回。选择一个枢轴元素 key这里选择的是数组中间的元素。使用双指针 i 和 j 分别从左右两端开始扫描数组当 i 指向的元素小于枢轴元素时i 向右移动当 j 指向的元素大于枢轴元素时j 向左移动。当 i j 时交换两个指针所指向的元素。最后递归对枢轴元素左右两边的子数组进行快速排序。
具体实现
#include iostreamusing namespace std;const int N 100010;int q[N];void quick_sort(int* q, int left, int right)
{if (left right) // 如果左右边界不合法直接返回return;int i left - 1, j right 1;int key q[left right 1]; // 选择枢轴元素while (i j){do i; while (q[i] key); // i之前的数全部小于等于keydo j--; while (q[j] key); // j之后的数全部大于等于keyif (i j) swap(q[i], q[j]); // 如果ij交换两个指针所指向的元素}quick_sort(q, left, j); // 对左边子数组进行快速排序quick_sort(q, j 1, right); // 对右边子数组进行快速排序
}int main()
{int n;scanf(%d, n);for (int i 0; i n; i) scanf(%d, q[i]);quick_sort(q, 0, n - 1); // 对整个数组进行快速排序for (int i 0; i n; i) printf(%d , q[i]);return 0;
}二、归并排序 题目链接归并排序
归并排序是一种分治算法它将一个大数组分成两个小数组然后递归地对这两个小数组进行排序最后将两个排好序的小数组合并成一个有序的大数组。在merge_sort函数中首先判断待排序区间长度是否小于等于1如果是则直接返回。否则计算中点mid然后对左半部分和右半部分分别进行归并排序。在对左右两部分排好序之后使用双指针技术将两个有序的小数组合并成一个有序的大数组。具体来说定义三个指针i、j和k其中i和j分别指向左右两部分的起始位置而k指向辅助数组tmp的起始位置。当i和j都在各自的区间内时比较v[i]和v[j]的大小关系并将较小者放入tmp中并移动相应的指针。当其中一个区间内所有元素都已经放入tmp中时则依次将另一个区间内剩余元素放入tmp中。最后将排好序的tmp复制回原数组v中。
#include iostreamusing namespace std;const int N 1e5 10; // 定义常量N为100010int v[N], tmp[N]; // 定义整型数组v和tmp大小均为N// 归并排序函数参数为待排序数组v以及待排序区间[left, right]
void merge_sort(int v[], int left, int right)
{if (left right) // 如果待排序区间长度小于等于1则直接返回return;int mid left right 1; // 计算中点midmerge_sort(v, left, mid); // 对左半部分进行归并排序merge_sort(v, mid 1, right); // 对右半部分进行归并排序int i left, j mid 1, k left; // 定义三个指针i、j、kwhile (i mid j right) // 当i和j都在各自的区间内时{if (v[i] v[j]) tmp[k] v[i]; // 如果v[i] v[j]则将v[i]放入tmp中并移动指针i和kelse tmp[k] v[j]; // 否则将v[j]放入tmp中并移动指针j和k}while (i mid) // 如果左半部分还有剩余元素则依次放入tmp中tmp[k] v[i];while (j right) // 如果右半部分还有剩余元素则依次放入tmp中tmp[k] v[j];for (i left; i right; i) // 将排好序的tmp复制回原数组v中v[i] tmp[i];
}int main()
{int n;cin n; // 输入元素个数nfor (int i 0; i n; i)scanf(%d, v[i]); // 输入n个元素merge_sort(v, 0, n - 1); // 对整个数组进行归并排序for (int i 0; i n; i)printf(%d , v[i]); // 输出排好序的结果return 0;
}三、二分算法 二分法即二分搜索法是通过不断缩小解可能存在的范围从而求得问题最优解的方法。例如如果一个序列是有序的那么可以通过二分的方法快速找到所需要查找的元素相比线性搜索要快不少。此外二分法还能高效的解决一些单调性判定的问题。 // 模板一
// 求满足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;
}数的范围 题目链接数的范围
// 数的范围#include iostream
#include vectorusing namespace std;int main()
{int n, m;cin n m; // 输入元素个数n和查询次数mvectorint v(n); // 定义整型向量v大小为nfor (int i 0; i n; i)cin v[i]; // 输入n个元素while (m--) // 循环执行m次查询操作{int num;cin num; // 输入要查询的元素num// 先找等于num的最左下标int l 0, r n - 1; // 定义双指针l和rwhile (l r) // 当lr时循环执行以下操作{int mid l r 1; // 计算中点midif (v[mid] num) // 如果v[mid] num则在左半部分继续查找r mid;else // 否则在右半部分继续查找l mid 1;}if (v[l] ! num) // 如果没有找到num则输出-1 -1{cout -1 -1 endl;continue;}else{cout l ; // 输出最左下标ll 0, r n - 1; // 重新定义双指针l和r// 再找等于num的最右下标while (l r) // 当lr时循环执行以下操作{int mid l r 1 1; // 计算中点midif (v[mid] num) // 如果v[mid] num则在右半部分继续查找l mid;else r mid - 1;}cout l endl;}}return 0;
}四、高精度算法 高精度算法是用计算机对于超大数据的一种模拟加减乘除乘方阶乘等运算的方法它用于处理大数字的数学计算。 比如C的long long类型最多处理2642^{64}264这么大的数再大的数则无法处理。 高精度加法
我们可以模拟正常的加法从个位开始逐位相加模拟过程中要注意的是
我们取出字符串的每一个元素都是字符所以不能直接将其相加必须要减去0 才能得到这个数的真实值。当一个数的每一位都已经遍历完了如果另一个数还没遍历完则在这个数的高位补0。如果两个数字之和大于等于10要进位。每次向要返回字符串插入一个本次相加得到的个位数。最后得到的返回字符串是反的我们要将其反转。 题目链接高精度加法
// 高精度加法#include iostream
#include iostream
#include vector
#include stringusing namespace std;vectorint add(vectorint a, vectorint b)
{int t 0; // 进位vectorint c;// 当ab大数没有遍历完或者进位不为0时继续循环for (int i 0; i a.size() || i b.size() || t ! 0; i){// 数字没有遍历完才加if (i a.size()) t a[i];if (i b.size()) t b[i];c.push_back(t % 10);t / 10;}return c;
}int main()
{string a, b;cin a b;vectorint a, b;// 字符串接收数据用数组来保存数据其实也可以直接使用字符串计算为了方便理解以及美观好记// 暂时使用数组来存储大数的每一位但是有一点要注意数组存储大数时最好反着存也即0下标存最低位高下标存高位类似于小端// 因为加法可能要进位如果0下标存最高位进位必须整体向后移动一位这样太耗费时间for (int i a.size() - 1; i 0; --i)a.push_back(a[i] - 0);for (int i b.size() - 1; i 0; --i)b.push_back(b[i] - 0);vectorint c add(a, b);for (auto rit c.rbegin(); rit ! c.rend(); rit)printf(%d, *rit);return 0;
}压位优化版了解即可 它首先定义了一个常量 base 为 1e9表示每个元素存储9位数。然后定义了一个 add 函数用于计算两个大数的和。在主函数中首先读入两个字符串 a 和 b然后将它们转换为大数存储在向量 A 和 B 中。最后调用 add 函数计算它们的和并输出结果。 #include iostream
#include vector
#include stringusing namespace std;const int base 1e9;vectorint add(vectorint A, vectorint B)
{int t 0; // 进位vectorint C;// 当AB大数没有遍历完或者进位不为0时继续循环for (int i 0; i A.size() || i B.size() || t ! 0; i){// 数字没有遍历完才加if (i A.size()) t A[i];if (i B.size()) t B[i];C.push_back(t % base);t / base;}if (t) C.push_back(t);return C;
}int main()
{string a, b;cin a b;vectorint A, B;// 压位一次将9个数字存储到一个位置可以节省空间以及加快运算for (int i a.size() - 1, s 0, t 1, j 0; i 0; --i){s (a[i] - 0) * t;j, t * 10;if (j 9 || i 0){A.push_back(s);j 0, s 0, t 1;}}for (int i b.size() - 1, s 0, t 1, j 0; i 0; --i){s (b[i] - 0) * t;j, t * 10;if (j 9 || i 0){B.push_back(s);j 0, s 0, t 1;}}vectorint C add(A, B);cout C.back();// 高位为0的需要用前导0填充for (int i C.size() - 2; i 0; --i) printf(%09d, C[i]);return 0;
}高精度减法
和加法大体思路相同不过要先判断被减数和减数的大小确定结果的正负。 题目链接高精度减法
// 高精度减法#include iostream
#include vector
#include stringusing namespace std;// a大于等于b返回true反之返回false
bool compare(string a, string b)
{if (a.size() ! b.size())return a.size() b.size();for (int i 0; i a.size(); i)if (a[i] ! b[i])return a[i] b[i];return true;
}vectorint sub(vectorint a, vectorint b)
{vectorint c;int t 0; // 借位for (int i 0; i a.size(); i){t a[i] - t;if (i b.size())t - b[i];// 无论借没借位先加上10再模10就是这一位的值c.push_back((t 10) % 10);// 如果没有借位a[i] - t b[i]那么t最后是大于等于0// 反之小于0if (t 0) t 1;else t 0;}while (c.size() 1){if (c.back() ! 0)break;c.pop_back();}return c;
}int main()
{string a, b;cin a b;vectorint a, b;for (int i a.size() - 1; i 0; --i)a.push_back(a[i] - 0);for (int i b.size() - 1; i 0; --i)b.push_back(b[i] - 0);vectorint c;if (compare(a, b))c sub(a, b);else{c sub(b, a);cout -;}for (int i c.size() - 1; i 0; --i){printf(%d, c[i]);}return 0;
}高精度乘法
先来看乘法用竖式如何计算 我们发现从右到左 num2 每一位都需要乘以 num1 并且每乘完一次 num1 所得的数字的权重要乘10。 num2 每一位乘 num1 都是个位数* num1 ,所以我们可以先把个位数乘 num1 的结果保存起来用的时候直接调用。 得到 num2 每一位乘 num1 的字符串后保存起来最后和竖式一样依次相加每一位的结果得到最后的答案。 题目链接高精度乘法
题目中 B 的值小于等于 10000可以直接用 A 的每一位乘 B具体实现见代码。
// 高精度乘法#include iostream
#include vector
#include stringusing namespace std;vectorint mul(vectorint A, const int b)
{int t 0; // 进位vectorint C;for (int i 0; i A.size() || t ! 0; i){if (i A.size()) t A[i] * b;C.push_back(t % 10);t / 10;}// 删去前导0防止乘0的特殊情况while (C.size() 1){if (C.back() ! 0)break;C.pop_back();}return C;
}int main()
{string a;int b;cin a b;vectorint A;for (int i a.size() - 1; i 0; --i)A.push_back(a[i] - 0);vectorint C mul(A, b);for (int i C.size() - 1; i 0; --i)printf(%d, C[i]);return 0;
}
高精度除法
思路和上述高精度算法大体相同具体见代码。 题目链接高精度除法
// 高精度除法
#include iostream
#include vector
#include string
#include algorithmusing namespace std;vectorint div(vectorint A, const int b, int r)
{int t 0;vectorint C;// 除法要从高位开始for (int i A.size() - 1; i 0; --i){t t * 10 A[i];C.push_back(t / b);t % b;}r t;// 由于C是从高位开始记录的返回时需要反转一下恢复低位存低位高位存高位的标准reverse(C.begin(), C.end());// 除去前导0while (C.size() 1 C.back() 0)C.pop_back();return C;
}int main()
{string a;int b;cin a b;vectorint A;for (int i a.size() - 1; i 0; --i)A.push_back(a[i] - 0);int r 0; // 余数vectorint C div(A, b, r);for (int i C.size() - 1; i 0; --i)printf(%d, C[i]);printf(\n%d, r);return 0;
}五、前缀和与差分 一维前缀和 题目链接前缀和
首先定义一个函数 get_part_sum用于计算区间和。在主函数中首先读入两个整数 n 和 m然后读入一个长度为 n 的数组 v。接着计算前缀和数组 prefix最后循环读入查询区间的左右端点 l 和 r并输出区间和。
// 一维前缀和
#include iostream
#include vector
using namespace std;// 计算区间和
int get_part_sum(vectorint prefix, int l, int r)
{// 区间和 前缀和[r] - 前缀和[l - 1]return prefix[r] - prefix[l - 1];
}int main()
{int n, m;cin n m;vectorint v(n 1);for (int i 1; i n; i)scanf(%d, v[i]);// 计算前缀和数组vectorint prefix(n 1);for (int i 1; i n; i)// 前缀和[i] 前缀和[i - 1] v[i]prefix[i] prefix[i - 1] v[i];int l, r;while (cin l r){// 输出区间[l,r]的区间和cout get_part_sum(prefix, l, r) endl;}return 0;
}二维前缀和 题目链接子矩阵的和
// 二维前缀和
#include iostream
#include vectorusing namespace std;int get_part_sum(vectorvectorint prefix, int x1, int y1, int x2, int y2)
{return prefix[x2][y2] - prefix[x1 - 1][y2] - prefix[x2][y1 - 1] prefix[x1 - 1][y1 - 1];
}int main()
{int n, m, q;cin n m q;vectorvectorint vv(n 1, vectorint(m 1, 0));for (int i 1; i n; i)for (int j 1; j m; j)scanf(%d, vv[i][j]);vectorvectorint prefix(n 1, vectorint(m 1, 0));for (int i 1; i n; i)for (int j 1; j m; j)prefix[i][j] prefix[i - 1][j] prefix[i][j - 1] - prefix[i - 1][j - 1] vv[i][j];// 二维前缀和计算公式// sum(x1, y1, x2, y2) prefix(x2, y2) - prefix(x1 - 1, y2) - prefix(x2, y1 - 1) prefix(x1 - 1, y1 - 1)int x1, y1, x2, y2;while (q--){scanf(%d%d%d%d, x1, y1, x2, y2);cout get_part_sum(prefix, x1, y1, x2, y2) endl;}return 0;
}一维差分 差分算法是一种利用原数组和差分数组的关系来快速地对数组中某个区间进行同一操作的方法。例如如果要对原数组a[]中[l,r]之间的每个数加上c只需要对差分数组b[]中的b[l]加上cb[r1]减去c然后重新求出a[]即可。 如何构造差分数组呢 构造差分数组的方法很简单只需要用原数组的相邻元素的差来赋值即可。例如如果原数组a[]为{1,2,4,6}那么差分数组b[]为{1,1,2,2}因为b[1]a[1]-a[0]b[2]a[2]-a[1]以此类推。 反之从差分数组求原数组就为a[i] a[i - 1] b[i](i 0)。 题目链接差分
一维差分数组是一种处理区间修改和查询的方法它可以在O(1)的时间内实现对原数组某个区间内所有元素加上一个常数。具体来说如果原数组是a[]差分数组是b[]那么有以下关系
a[i] b[1] b[2] … b[i]b[i] a[i] - a[i-1]
// 一维差分
#include iostream
#include vectorusing namespace std;void insert(vectorint dif, int l, int r, int c)
{dif[l] c;dif[r 1] - c;
}int main()
{int n, m;cin n m;vectorint v(n 2);for (int i 1; i n; i)scanf(%d, v[i]);// 差分公式mod(l, r, c) : dif(l) c and dif(r 1) - c vectorint dif(n 2, 0);// 差分数组初始化假设 前缀和 和 差分数组 都是0开始前缀和数组(i位置)每插入一个数字相当于 在差分数组(i, i)位置插入v[i]for (int i 1; i n; i)insert(dif, i, i, v[i]);int l, r, c;while (m--){cin l r c;insert(dif, l, r, c);}for (int i 1; i n; i)v[i] v[i - 1] dif[i];for (int i 1; i n; i)printf(%d , v[i]);return 0;
}二维差分 题目链接差分矩阵
// 二维差分
#include iostream
#include vectorusing namespace std;const int N 1010;int v[N][N];
int dif[N][N];// 二维差分公式 insert(x1, y1, x2, y2, c)
// dif[x1][y1] c dif[x2 1][y1] - c dif[x1][y2 1] - c dif[x2 1][y2 1] c
// 定义一个函数用于对差分数组进行修改
void insert(int x1, int y1, int x2, int y2, int c)
{dif[x1][y1] c;dif[x2 1][y1] - c;dif[x1][y2 1] - c;dif[x2 1][y2 1] c;
}// 二维差分: dif[n][m] 会直接影响 v[n][m] 及右下方的值
int main()
{int n, m, q;cin n m q;for (int i 1; i n; i)for (int j 1; j m; j)scanf(%d, v[i][j]);// 初始化差分数组for (int i 1; i n; i)for (int j 1; j m; j)insert(i, j, i, j, v[i][j]);int x1, y1, x2, y2, c;while (q--){cin x1 y1 x2 y2 c;insert(x1, y1, x2, y2, c);}for (int i 1; i n; i)for (int j 1; j m; j)v[i][j] v[i - 1][j] v[i][j - 1] - v[i - 1][j - 1] dif[i][j];for (int i 1; i n; i){for (int j 1; j m; j)printf(%d , v[i][j]);printf(\n);}return 0;
}六、双指针算法 双指针算法是一种在重复遍历对象的过程中使用两个指针进行访问的方法。它可以利用对象的某种单调性减少不必要的遍历次数从而优化时间复杂度。双指针算法有两种常见的类型快慢指针和对撞指针。 快慢指针是指两个指针以不同的速度或步长在同一个方向上移动通常用于解决链表中的问题比如判断链表是否有环找到链表的中点或倒数第k个结点等。对撞指针是指两个指针从相反的方向上移动直到相遇或满足某个条件为止通常用于解决数组或字符串中的问题比如寻找两数之和等于目标值的下标判断一个字符串是否是回文串等。 模板
// 双指针模板
bool check(int i, int j);void two_pointer()
{int n;for (int i 0, j 0; i n; i){while (j i check(i, j)){// ......j;// ......}// .....}
}最长连续不重复子序列 题目链接最长连续不重复子序列
#include iostreamusing namespace std;const int N 100010; int v[N]; // 存储输入的数组
int book[N];//判重数组用于记录每个数字出现的次数int main()
{ int n; // 数组的长度 cin n; for (int i 0; i n; i) cin v[i]; int Max 0; // 记录最长不重复子数组的长度for (int i 0, j 0; i n; i) // i和j是两个指针分别指向子数组的右端点和左端点{book[v[i]]; // 将当前数字的计数加一// 当有重复数字时while (j i book[v[i]] 1) // 如果当前数字出现了两次以上说明子数组中有重复元素需要缩小左边界{// j指向的数字计数--并且j直到数组中没有重复数字book[v[j]]--;j;}Max max(Max, i - j 1); // 更新最长不重复子数组的长度}cout Max endl; // 输出结果return 0;
}数组元素目标和 题目链接数组元素的目标和
#include iostreamusing namespace std;const int N 100010;int v1[N]; // 存储第一个有序数组
int v2[N]; // 存储第二个有序数组int main()
{ int n, m, t; // n和m分别是两个数组的长度t是目标值 cin n m t; for (int i 0; i n; i) cin v1[i]; for (int i 0; i m; i) cin v2[i];int i 0, j m - 1; // i和j是两个指针分别指向第一个数组的左端点和第二个数组的右端点while (i n j 0) // 当两个指针没有越界时{if (v1[i] v2[j] t) // 如果两个指针指向的数字之和等于目标值输出下标对并将左指针右移{cout i j endl;i;}else if (v1[i] v2[j] t) // 如果两个指针指向的数字之和大于目标值说明右边的数字太大需要将右指针左移j--;else // 如果两个指针指向的数字之和小于目标值说明左边的数字太小需要将左指针右移i;}return 0;
}七、位运算 获取n的二进制表示中第k位最低位从0开始
int n;
int k;
int bitk n k 1;获取n的二进制表示中最右边的1
// lowbit获取n的二进制表示中最右边的1eg. 输入 10010 返回 00010
int rightbit1 n -n; // 等价于 n (~n 1) 二进制中1的个数 题目链接二进制中1的个数
#include iostreamusing namespace std;const int N 1e5 10;
int v[N];int main()
{int n;cin n;for (int i 0; i n; i)cin v[i];for (int i 0; i n; i){int num v[i];int cnt 0;while (num){int x num -num; // lowbitcnt;num ^ x; // 去除最后一个1}cout cnt ;}cout endl;return 0;
}八、离散化 离散化定义
整数保序离散化
将数据范围很大但是数字个数很少的数据按照升序对数字坐标进行映射
如数据范围 10^9 数字个数 10^5 1 200000 88888888 1e9
将上述数据映射到 0 1 2 3
简而言之就是一种哈希区间和 题目链接区间和
// 区间和// 原版
#include iostream
#include vector
#include algorithmusing namespace std;const int N 3 * 1e5 1;vectorint alls; // 存放所有坐标将其离散化
vectorpairint, int operates; // 所有操作
vectorpairint, int query; // 所有查询int Hash[N]; // 离散化坐标对应的值
int psum[N]; // 前缀和数组// 以原坐标值查询映射后的坐标值
int find(int x)
{// 二分查找int l 0, r alls.size() - 1;while (l r){int mid l r 1;if (alls[mid] x)r mid;elsel mid 1;}return l 1;
}int main()
{int n, m;cin n m;for (int i 0; i n; i){int x, c;cin x c;operates.emplace_back(x, c);alls.push_back(x);}for (int i 0; i m; i){int l, r;cin l r;query.emplace_back(l, r);alls.push_back(l);alls.push_back(r);}sort(alls.begin(), alls.end()); // 坐标排序alls.erase(unique(alls.begin(), alls.end()), alls.end());// 去重去除重复坐标for (int i 0; i n; i){// 由于前缀和数组的下标要从1开始所有所有映射坐标1int x find(operates[i].first), c operates[i].second;Hash[x] c;}// 构造前缀和数组for (int i 1; i alls.size(); i)psum[i] psum[i - 1] Hash[i];for (int i 0; i m; i){int l find(query[i].first), r find(query[i].second);cout psum[r] - psum[l - 1] endl;}return 0;
}九、区间合并 区间合并 区间合并算法是一种用于把给定的、可以合并的区间合并的算法。它的基本思想是 将所有区间按照左边界值进行从小到大排序。遍历所有区间如果第i1区间的左边界值比第i区间的右边界值小即可合并更新i1区间的边界值并且将第i区间打上标记表示该区间被i1合并过。最后输出没有被标记过的区间即为合并后的结果。 题目链接区间合并
#include iostream
#include vector
#include algorithmusing namespace std;typedef pairint, int PII;
vectorPII v;int main()
{int n;cin n;for (int i 0; i n; i){int l, r;cin l r;v.emplace_back(l, r);}sort(v.begin(), v.end());int l -2e9, r -2e9; // 初始化变量 l 和 r 的值为 -2e9int cnt 0; // 初始化计数器 cnt 的值为 0for (auto e : v) // 遍历 vector 中的每个元素 e{int nl e.first, nr e.second; if (nl r) // 如果新区间与当前区间不相交{cnt; // 区间计数器加一l nl; }r max(nr, r); // 更新当前区间右端点}cout cnt endl;return 0;
}后记 在这篇文章中我们介绍了算法基础的一些概念和方法包括算法的定义、特征、分类、设计和分析等。我们也通过一些例子展示了如何运用算法解决实际问题并且分析了算法的效率和优化。我们希望这篇文章能够给你提供一个对算法基础的初步认识和兴趣让你感受到算法的魅力和价值。 如果解析有不对之处还请指正我会尽快修改多谢大家的包容。
如果大家喜欢这个系列还请大家多多支持啦
如果这篇文章有帮到你还请给我一个大拇指 和小星星 ⭐️支持一下白晨吧喜欢白晨【算法】系列的话不如关注白晨以便看到最新更新哟
我是不太能熬夜的白晨我们下篇文章见。
