基础算法

• 快速排序
• 归并排序
• 二分
• 前缀和
• 差分
• 双指针算法
• 位运算
• 离散化
• 区间合并
• 高精度加法
• 高精度减法
• 高精度乘法
• 高精度除法

快速排序

算法思想：在数组中选择一个数$x$，使得所有$>=x$的数在右边，$<=x$的数在左边，并将$x$放到排序之后应该所在的位置，然后递归处理左右两边，直到所有的数都被放在正确的位置。
边界问题：当只有两个数时，选择$x$时注意是左边界还是有边界，若是左边界，则$i$指向左边界，递归时选取[$i$，$r$]时，会陷入死循环，同理选择右边界时，$j$指向右边界，递归时选择[$l$，$j$]时，会陷入死循环。此外还需注意会出现$j$在$i$之前的交叉情况，这时选择递归条件应为[$l$, $j$],因为$i$此时已经递增到$x$的下一个元素，因此不可以选取[$l$, $i$]作为递归条件，该范围内的数无法保证一定小于等于$x$.
因此，选择$x$时，取左边界使用$j$递归，取右边界时，使用$i$递归
算法实现：

#include <iostream>
using namespace std;const int N = 100010;int q[N];void quick_sort(int q[], int l, int r)
{if(l >= r) return;int x = q[l + r >> 1], i = l - 1, j = r + 1;while(i < j){do i ++; while(q[i] < x);do j --; while(q[j] > x);if(i < j) swap(q[i], q[j]);}quick_sort(q, l, j);quick_sort(q, j + 1, r);return;
}int main()
{int n;cin >> n;for(int i = 0; i < n; i ++) cin >> q[i];quick_sort(q, 0, n - 1);for(int i = 0; i < n; i ++) cout << q[i] << ' ';return 0;
}

归并排序

算法思想：不断递归将数组分成两段，直到分成可以判断大小的两个数，然后再进行合并，将两个有序数组合并成一个有序数组，不断向上合并直到整个数组合并完成
算法实现：

#include <iostream>
using namespace std;const int N = 100010;int q[N], temp[N];void merge_sort(int q[], int l, int r)
{if(l >= r) return;int mid = l + r >> 1, i = l, j = mid + 1;merge_sort(q, l, mid);merge_sort(q, mid + 1, r);int k = 0;while(i <= mid && j <= r){if(q[i] <= q[j]) temp[k ++] = q[i ++];else temp[k ++] = q[j ++];// while(q[i] <= q[j] && i <= mid) temp[k ++] = q[i ++];// while(q[j] < q[i] && j <= r) temp[k ++] = q[j ++];}while(i <= mid) temp[k ++] = q[i ++];while(j <= r) temp[k ++] = q[j ++];for(int i = 0, j = l; j <= r; i ++, j ++) q[j] = temp[i];return;
}
int main()
{int n;cin >> n;for(int i = 0; i < n; i ++) cin >> q[i];merge_sort(q, 0, n - 1);for(int i = 0; i < n; i ++) cout << q[i] << ' ';return 0;
}

二分

算法思想：某个问题具有两种可以一分为二的性质，那我们就可以不断地去判断这两种性质，更新边界，最后把临界点找出来。
例如：

给定一个按照升序排列的长度为 n 的整数数组，返回一个元素 k 的起始位置和终止位置，如果数组中不存在该元素，则返回 -1 -1。

边界问题：整数二分中更新边界时，如果左边界$l=mid$，则$mid$应向上取整，当只有两个数时，若右边界是我们的答案，则会陷入死循环，同理更新右边界时也是一样。所以，当我们更新左边界$l=mid$时，说明答案在右边，因此$mid$应向上取整，当更新右边界时，说明答案在左边，因此$mid$应向下取整。
算法实现:

#include <iostream>
using namespace std;const int N = 100010;int q[N];int main()
{int n, m;cin >> n >> m;for(int i = 0; i < n; i ++) cin >> q[i];while (m -- ){int x;cin >> x;int l = 0, r = n - 1;while(l < r){int mid = l + r >> 1;if(q[mid] >= x) r = mid;else l = mid + 1;}if(q[l] != x) cout << "-1 -1" << endl;else{cout << l << ' ';l = 0, r = n - 1;while(l < r){int mid = l + r + 1 >> 1;if(q[mid] <= x) l = mid;else r = mid - 1;}cout << l << endl;}}return 0;
}

前缀和

算法思想：通过计算前缀和，我们可以很方便的求出某一段区间的和，不需要每次都对区间中的所有数求和，只需将其前缀和相减即可
一维前缀和：$S[i]=S[i-1]+a[i]$，为了方便计算我们定义$S[0]=0$
二维前缀和：$S[i,j]=S[i-1,j]+S[i,j-1]-S[i-1,j-1]+a[i,j]$，同样的，为了方便计算我们定义$S[0,j]=S[i,0]=0$
算法实现：
一维前缀和

输入一个长度为 n 的整数序列。接下来再输入 m 个询问，每个询问输入一对 l,r。

#include <iostream>
using namespace std;const int N = 100010;int a[N], S[N];int main()
{int n, m;scanf("%d%d", &n, &m);for(int i = 1; i <= n; i ++) {scanf("%d", &a[i]);S[i] = S[i - 1] + a[i];}while(m --){int l, r;scanf("%d%d", &l,&r);printf("%dn",S[r] - S[l - 1]);}return 0;}

二维前缀和

#include <iostream>
using namespace std;const int N = 1010;int a[N][N], s[N][N];int main()
{int n, m, q;scanf("%d%d%d",&n, &m, &q);for(int i = 1; i <= n; i ++)for(int j = 1; j <= m; j ++){scanf("%d", &a[i][j]);s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];}while(q --){int x1, y1, x2, y2;scanf("%d%d%d%d", &x1, &y1, &x2, &y2);printf("%dn", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);}return 0;
}

差分

算法思想：通过构造原数组的差分数组，我们可以实现对某一区间中所有数加减某个值而不需要遍历这个区间中的所有值，当面对大量的修改操作时，可以在$O(1)$的时间内实现
一维差分：对于原数组$a[i]$，我们构造差分数组$b[i]$，使得原数组$a[i]$是$b[i]$数组的前缀和，即$a[i]=b[i]+b[i-1]+\dots +b[1]$，当要对数组$a$中的$[l,r]$中的数加上或减去某一个数$c$时只需要将$b[l]+c,b[r+1]-c$即可。构造差分数组$b[i]=a[i]-a[i-1]$,但实际构造时，可认为原数组全部为$0$,此时$b$数组也全部为$0$，因此只需要考虑插入即可，$a[i]$可认为是在$[i,i]$处插入了值$a[i]$
算法实现：
一维差分：

#include <iostream>
using namespace std;const int N = 100010;int a[N],b[N];void insert(int l, int r, int c)
{b[l] += c;b[r + 1] -= c;
}int main()
{int n, m;scanf("%d%d",&n,&m);for(int i = 1; i <= n; i ++) scanf("%d",&a[i]), insert(i, i, a[i]);while (m -- ){int l, r, c;scanf("%d%d%d", &l, &r, &c);insert(l, r, c);}for(int i = 1; i <= n; i ++) b[i] += b[i - 1], printf("%d ", b[i]);return 0;
}

二维差分：

#include <iostream>
using namespace std;const int N = 1010;int a[N][N], b[N][N];void insert(int x1, int y1, int x2, int y2, int c)
{b[x1][y1] += c;b[x1][y2 + 1] -= c;b[x2 + 1][y1] -= c;b[x2 + 1][y2 + 1] += c;
}int main()
{int n, m, q;scanf("%d%d%d", &n, &m, &q);for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++){scanf("%d", &a[i][j]);insert(i, j, i, j, a[i][j]);}}while(q --){int x1, y1, x2, y2, c;scanf("%d%d%d%d%d", &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 ++){b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];//求前缀和printf("%d ", b[i][j]);}printf("n");}return 0;}

双指针算法

算法思想：双指针算法主要是利用问题的某种性质，主要是单调性，将原本O(n2)O(n^2)O(n2)的时间复杂度优化到$O(n)$，之前快速排序和归并排序中都用到了该思想。
算法实现：

给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

#include <iostream>
using namespace std;const int N = 100010;int a[N],s[N];int main()
{int n;cin >> n;for(int i = 0; i < n; i ++) cin >> a[i];int res = 0;for(int i = 0, j = 0; i < n; i ++){s[a[i]] ++;while(s[a[i]] > 1){s[a[j]] --;j ++;}res = max(res,  i - j + 1);}cout << res << endl;return 0;
}

位运算

算法思想：位运算主要是求二进制中第$i$位是$0$还是$1$，实现方式为将二进制右移$i$位再$\&1$
$lowbit$操作是返回一个二进制数中最后一个$1$的位置，实现方式为$x\&-x$，即一个数的原码与上补码，补码为(~$x$+1)，即取反再加1

算法实现：

给定一个长度为 n 的数列，请你求出数列中每个数的二进制表示中 1 的个数

#include <iostream>
using namespace std;int lowbit(int x)
{return x & -x;
}int main()
{int n;cin >> n;while (n -- ){int x;cin >> x;int res = 0;while(x){x -= lowbit(x);res ++;}cout << res << ' ';}return 0;
}

离散化

算法思想：离散化其实就是在做映射，若值域范围很大，而我们所需要的点很少，就会出现间隔很大的点，若我们直接存储就会浪费很多空间，因此我们将其映射到相邻的数组元素中，减少空间和计算量。

$unique$函数实现：

算法实现：

假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;typedef pair<int, int> PII;
const int N = 300010;int a[N],s[N];
vector<int> alls;
vector<PII> p, q;//坐标映射
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;else l = mid + 1;}return l + 1; //从1开始方便求前缀和
}// vector<int>::iterator unique(vector<int> &a)
// {
//     int j = 0;
//     for (int i = 0; i < a.size(); i ++ )
//         if (!i || a[i] != a[i - 1])
//             a[j ++ ] = a[i];
//     // a[0] ~ a[j - 1] 所有a中不重复的数//     return a.begin() + j;
// }int main()
{int n, m;cin >> n >> m;for(int i = 0; i < n; i++){int x, c;cin >> x >> c;p.push_back({x,c});alls.push_back(x);}for(int i = 0; i < m; i ++){int l, r;cin >> l >> r;q.push_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 < p.size(); i ++){a[find(p[i].first)] += p[i].second;}//求前缀和for(int i = 1; i <= alls.size(); i ++) s[i] = s[i - 1] + a[i];//输出查询结果for(int i = 0; i < q.size(); i ++){cout << s[find(q[i].second)] - s[find(q[i].first) - 1] << endl;}return 0;}

区间合并

算法思想：区间合并是将有交集的区间合并成一个区间

算法实现：

给定 n 个区间，要求合并所有有交集的区间。注意如果在端点处相交，也算有交集。输出合并完成后的区间个数。例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;const int N = 100010;typedef pair<int, int> PII;vector<PII> segs;void merge(vector<PII> &segs)
{vector<PII> res;int l = -2e9, r = -2e9;for(auto seg : segs){if(seg.first > r){if(r != -2e9) res.push_back({l, r});l = seg.first;r = seg.second;}else r = max(r, seg.second);}if(l != -2e9) res.push_back({l,r});segs = res;return;
}
int main()
{int n;cin >> n;while (n -- ){int l, r;cin >> l >> r;segs.push_back({l,r});}sort(segs.begin(), segs.end());merge(segs);cout << segs.size() << endl;return 0;
}

高精度加法

算法思想：依次从低位到高位计算，判断是否进位
算法实现：

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;const int N = 100010;vector<int> add(vector<int> &A, vector<int> &B)
{vector<int> C;int t = 0;for(int i = 0; i < A.size() || i < B.size(); i ++){if(i < A.size()) t += A[i];if(i < B.size()) t += B[i];C.push_back(t % 10);t /= 10;}if(t) C.push_back(t);return C;
}int main()
{string a,b;cin >> a >> b;vector<int> 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');auto C = add(A, B);for(int i = C.size() - 1; i >= 0; i --) cout << C[i];cout << endl;return 0;
}

高精度减法

算法思想：从低位到高位依次相减，判断是否需要借位
算法实现：

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;bool cmp(vector<int> A, vector<int> B)
{if(A.size() != B.size()) return A.size() > B.size();else{for(int i = A.size() - 1; i >= 0; i --){if(A[i] != B[i]) return A[i] > B[i];}}return true;
}vector<int> sub(vector<int> &A, vector<int> &B)
{vector<int> C;int t = 0;for(int i = 0; i < A.size(); i ++){t = A[i] - t;if(i < B.size()) t -= B[i];C.push_back((t + 10) % 10);if(t < 0) t = 1;else t = 0;}while(C.size() > 1 && C.back() == 0) C.pop_back();return C;
}
int main()
{string a, b;cin >> a >> b;vector<int> 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');if(cmp(A,B)){auto C = sub(A, B);for(int i = C.size() - 1; i >= 0; i --) cout << C[i];}else{cout << '-';auto C = sub(B, A);for(int i = C.size() - 1; i >= 0; i--) cout << C[i];}return 0;
}

高精度乘法

算法思想：将高精度的每一位乘上较小的数，再向前进位
算法实现：

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;vector<int> mul(vector<int> &A, int &b)
{vector<int> C;int t = 0;for(int i = 0; i < A.size() || t; i ++){t += A[i] * b;C.push_back(t % 10);t /= 10;}// while(t) // {//     C.push_back(t % 10);//     t /= 10;// }while(C.size() > 1 && C.back() == 0) C.pop_back();return C;
}
int main()
{string a;cin >> a;vector<int> A;for(int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');int b;cin >> b;auto C = mul(A, b);for(int i = C.size() - 1; i >= 0; i --) cout << C[i];return 0;
}

高精度除法

算法思想：从高位开始，取每一位除以较小的数，每次取余数$\ast 10$再加上下一位
算法实现：

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;vector<int> div(vector<int> &A, int &b, int &r)
{vector<int> C;r = 0;for(int i = 0; i < A.size(); i ++){r = r * 10 + A[i];C.push_back(r / b);r %= b;}reverse(C.begin(), C.end());   //方便去除前导零while(C.size() > 1 && C.back() == 0) C.pop_back();return C;
}int main()
{string a;cin >> a;vector<int> A;for(int i = 0; i < a.size(); i ++) A.push_back(a[i] - '0');int b;cin >> b;int r;auto C = div(A, b, r);for(int i = C.size() - 1; i >= 0; i --) cout << C[i];cout << endl << r;return 0;
}