文章目录
前言
由于本篇博客相较而言都是算法中最基础的模板,包括快速排序、归并排序、二分、高精度加减乘除法、离散化。这些基础模板多与其他算法混合考察,这些模板是许多算法的实现基础。
Part 1:排序
1.分成子问题
2.递归处理子问题
3.子问题合并
一、快速排序
- 核心思想是:是将问题划分为子问题的过程中不断解决。不断根据一个分割点,交换前后数据,使得前一部分小于分割点,后一部分大于分割点,分割点在两部分中间,再根据分割位置将其分为两部分重新进行此操作,直到无法再分
void quick_sort(int q[], int l, int r)
{
//递归的终止情况
if(l >= r) return;
//第一步:分成子问题
int i = l - 1, j = r + 1, x = q[l + 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);
//第三步:子问题合并.快排这一步不需要操作,但归并排序的核心在这一步骤
}
二、归并排序
- 核心思想:不断将问题划分为子问题,再从子问题开始操作,累加出问题的答案。将数组不断划分为两部分,在无法划分时,将每个分治最后一次划分的两部分合并排序,重复从小问题向原问题操作,合并为排序答案
void merge_sort(int q[], int l, int r)
{
//递归的终止情况
if(l >= r) return;
//第一步:分成子问题
int mid = l + r >> 1;
//第二步:递归处理子问题
merge_sort(q, l, mid ), merge_sort(q, mid + 1, r);
//第三步:合并子问题
int k = 0, i = l, j = mid + 1, tmp[r - l + 1];
while(i <= mid && j <= r)
if(q[i] <= q[j]) tmp[k++] = q[i++];
else tmp[k++] = q[j++];
while(i <= mid) tmp[k++] = q[i++];
while(j <= r) tmp[k++] = q[j++];
for(k = 0, i = l; i <= r; k++, i++) q[i] = tmp[k];
}
Part 2:二分
一般二分应用于无非下面这四种情况:
1:找大于等于数的第一个位置 (满足某个条件的第一个数)- 左边界
2:找小于等于数的最后一个数 (满足某个条件的最后一个数)- 右边界
3.查找最大值 (满足该边界的右边界)- 右边界
4.查找最小值 (满足该边界的左边界) - 左边界
一、二分 - 查找左边界
//查找左边界 SearchLeft 简写SL
int SL(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
二、二分 - 查找右边界
//查找右边界 SearchRight 简写SR
int SR(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1; //需要+1 防止死循环
if (check(mid)) l = mid;
else r = mid - 1;
}
return r;
}
总结以下记忆方式:有加必有减!!!
int mid = l + r + 1 >> 1; //+1为加
if (check(mid)) l = mid;
else r = mid - 1; //-1为减
Part 3:高精度
一、高精度加法
#include <iostream>
#include <vector>
using namespace std;
vector<int> add(vector<int> &A, vector<int> &B)
{
//为了方便计算,让A中保存较长的数字, B中保存较短的数字
if (A.size() < B.size()) return add(B, A);
//保存结果的数组
vector<int> C;
//进位,开始时是0
int t = 0;
//依次计算每一位
for (int i = 0; i < A.size(); i ++ )
{
t += A[i];//加上 A 的第 i 位上的数字
if (i < B.size()) t += B[i];//加上 B 的第 i 位上的数字
C.push_back(t % 10); //C 中放入结果
t /= 10;//t 更新成进位
}
//最后如果进位上有数,放进结果数组
if (t) C.push_back(t);
return C;//返回结果
}
int main()
{
string a, b;//以字符串形式保存输入的两个整数
vector<int> A, B;//保存两个整数的数组
cin >> 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];//倒序输出C中的数字
cout << endl;
return 0;
}
二、高精度减法
#include <iostream>
#include <vector>
using namespace std;
bool cmp(vector<int>& A, vector<int> &B)
{
if(A.size() != B.size()) return A.size() > B.size(); //直接ruturn 了就不用else
for(int i = A.size(); 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 ); // 合而为1
if(t < 0) t = 1;
else t = 0;
}
while(C.size() > 1 && C.back() == 0) C.pop_back(); //去掉前导0
return C;
}
int main()
{
string a ,b;
vector<int> A, B;
cin >> 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--) printf("%d", C[i]);
return 0;
}
else
{
auto C = sub(B, A);
printf("-");
for(int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
return 0;
}
}
三、高精度乘法
高精度 X 低精度
#include <iostream>
#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(); i ++)
{
t += A[i] * b; // t + A[i] * b = 7218
C.push_back(t % 10); // 只取个位 8
t /= 10; // 721 看作 进位
}
// 处理最后剩余的 t
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;
int b;
cin >> a >> b;
vector <int> A;
for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');
auto C = mul(A, b);
for (int i = C.size() - 1; i >= 0; i --)
{
cout << C[i];
}
return 0;
}
高精度 X 高精度
#include <iostream>
#include <vector>
using namespace std;
vector<int> mul(vector<int> &A, vector<int> &B)
{
vector<int> C(A.size() + B.size() + 7, 0); // 初始化为 0,C的size可以大一点
for (int i = 0; i < A.size(); i++)
for (int j = 0; j < B.size(); j++)
C[i + j] += A[i] * B[j];
int t = 0;
for (int i = 0; i < C.size(); i++) // i = C.size() - 1时 t 一定小于 10
{
t += C[i];
C[i] = t % 10;
t /= 10;
}
while (C.size() > 1 && C.back() == 0) C.pop_back(); // 必须要去前导 0,因为最高位很可能是 0
return C;
}
int main()
{
string a, b;
cin >> a >> b; // a = "1222323", b = "2323423423"
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 = mul(A, B);
for (int i = C.size() - 1; i >= 0; i--)
cout << C[i];
return 0;
}
大数相加A+B和大数相乘A*B通用模板
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> add(vector<int> A, vector<int> B)
{
// A: 4 3 2 1
// B: 6 5
vector<int> C(max(A.size(), B.size()) + 7, 0); // 数组C开大一点没事,反正可以去前导零的
for (int i = 0; i < A.size(); i ++) C[i] += A[i];
for (int i = 0; i < B.size(); i ++) C[i] += B[i];
// 处理进位
for (int i = 0; i + 1 < C.size(); i ++)
{
C[i + 1] += C[i] / 10;
C[i] %= 10;
}
// 处理前导零
while (C.size() > 1 && C.back() == 0) C.pop_back();
reverse(C.begin(), C.end());
return C;
}
vector<int> mul(vector<int> A, vector<int> B)
{
// A: 4 3 2 1
// B: 6 5
vector<int> C(A.size() + B.size() + 7, 0); // 数组C开大一点没事,反正可以去前导零的
for (int i = 0; i < A.size(); i ++)
{
for (int j = 0; j < B.size(); j ++)
{
C[i + j] += A[i] * B[j];
}
}
// 处理进位
for (int i = 0; i + 1 < C.size(); i ++)
{
C[i + 1] += C[i] / 10;
C[i] %= 10;
}
// 处理前导零 "0000" 去掉前导零
while (C.size() > 1 && C.back() == 0) C.pop_back();
reverse(C.begin(), C.end());
return C;
}
int main()
{
string s1 = "9899", s2 = "100";
vector<int> A, B;
for (int i = s1.size() - 1; i >= 0; i --) A.push_back(s1[i] - '0');
for (int i = s2.size() - 1; i >= 0; i --) B.push_back(s2[i] - '0');
vector<int> C = add(A, B);
cout << s1 << "+" << s2 << "=";
for (int i = 0; i < C.size(); i ++) cout << C[i];
cout << endl;
C = mul(A, B);
cout << s1 << "*" << s2 << "=";
for (int i = 0; i < C.size(); i ++) cout << C[i];
cout << endl;
return 0;
}
四、高精度除法
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//int r=0;
vector<int> div(vector<int> &A,int B,int &r)//r传入r的地址,便于直接对余数r进行修改
{
vector<int> C;
//对A从最高位开始处理
for(int i=0;i<A.size();i++)
{
r=r*10+A[i];//将上次的余数*10在加上当前位的数字,便是该位需要除的被除数
C.push_back(r/B);//所得即为商在这一位的数字
r=r%B;
}
//由于在除法运算中,高位到低位运算,因此C的前导零都在vector的前面而不是尾部,vector只有删除最后一个数字pop_back是常数复杂度,而对于删除第一位没有相应的库函数可以使用,而且删除第一位,其余位也要前移,
//因此我们将C翻转,这样0就位于数组尾部,可以使用pop函数删除前导0
reverse(C.begin(),C.end());
while(C.size()>1&&C.back()==0) C.pop_back();
return C;
}
int main()
{
string a;
int B,r=0; //代表余数
cin>>a>>B;
vector<int> A;
for(int i=0;i<a.size();i++) A.push_back(a[i]-'0');//注意这次的A是由高为传输至低位,由于在除法的手算过程中,发现从高位进行处理
//for(int i=0;i<A.size();i++) cout<<A[i];
//cout<<B;
auto C = div(A,B,r);
for(int i=C.size()-1;i>=0;i--) cout<<C[i];//将C从最高位传给最低位
cout<<endl<<r;//输出余数
cout<<endl;
return 0;
}
Part 4:离散化
一、区间和
题目描述:假定有一个无限长的数轴,数轴上每个坐标上的数都是 0。现在,我们首先进行 n 次操作,每次操作将某一位置 x 上的数加 c。接下来,进行 m 次询问,每个询问包含两个整数 l 和 r,你需要求出在区间 [l,r] 之间的所有数的和。
输入:第一行包含两个整数 n 和 m。接下来 n 行,每行包含两个整数 x 和 c。再接下来 m 行,每行包含两个整数 l 和 r。
输出:共 m 行,每行输出一个询问中所求的区间内数字和。
- 离散化的本质,是映射,将间隔很大的点,映射到相邻的数组元素中。减少对空间的需求,也减少计算量
- 该题解决办法就是开辟额外的数组存放原来的数组下标,或者说下标标志,本文是原来上的数轴上的非连续点的横坐标。此处的做法是是对原来的数轴下标进行排序,再去重,根据二分得到该数在开辟的连续数组中的位置
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 300010; //n次插入和m次查询相关数据量的上界
int n, m;
int a[N];//存储坐标插入的值
int s[N];//存储数组a的前缀和
vector<int> alls; //存储(所有与插入和查询有关的)坐标
vector<pair<int, int>> add, query; //存储插入和询问操作的数据
//返回的是输入的坐标的离散化下标
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 r + 1;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
int x, c;
scanf("%d%d", &x, &c);
add.push_back({x, c});
alls.push_back(x);
}
for (int i = 1; i <= m; i++)
{
int l , r;
scanf("%d%d", &l, &r);
query.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());
//执行前n次插入操作
for (auto item : add)
{
int x = find(item.first);
a[x] += item.second;
}
//前缀和
for (int i = 1; i <= alls.size(); i++) s[i] = s[i-1] + a[i];
//处理后m次询问操作
for (auto item : query)
{
int l = find(item.first);
int r = find(item.second);
printf("%d\n", s[r] - s[l-1]);
}
return 0;
}