一、基础算法
前言:基础算法无选修
<1>.高精度
前言:高精度算法的要点是模拟列竖式,核心算法是进位和去除前导零
1.大数+,-大数
加法
vector<int> add(vector<int> &A,vector<int> &B)
{
int t=0;vector<int> C;
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;//t不清零,保留进位
}
if(t)C.push_back(1);//结束后判断最高位是否要进位
return C;
}
减法
vector<int> sub(vector<int>& A, vector<int>& B)
{
//A>B,否则cout "-sun(B,A)"
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;//不够减则向高位借'1'
else t = 0;
}
while (C.size() > 1 && C.back() == 0)C.pop_back();
//去除前导‘0’
return C;
}
2.大数*,/小数
乘法:
vector<int> mul(vector<int> &A, int b)
{
vector<int> C;
int t = 0;
for (int i = 0; i < A.size() || t; i ++ )
{
if (i < A.size()) t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
除法:
vector<int> div(vector<int> &A, int b, int &r)
{
vector<int> C;
r = 0;
for (int i = A.size() - 1; i >= 0; 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;
}
<2>.排序
前言:记住原理,平常可用sort()进行O(nlogn)的排序
用法:sort(begin,end,cmp)
//考点:结构体排序
/*
bool cmp(type name.a,type name.b)
{
return a<b;
}
*/
1.快速排序
每次选择一个基准元素,将所有小于(或大于)它的元素放到它的左边,将所有大于(或小于)它的元素放到它的右边,然后对左右两边分别进行快速排序,直到所有元素都被排序为止.
void quick_sort(int a[],int l,int r)
{
//选择数组中间的数mid,左右双指针移动,使得mid左边全部小于a[mid],右边全部大于a[mid]
if(l>=r)return;
int x=a[(r+l)/2],i=l-1,j=r+1;
while(i<j)
{
do i++;while(a[i]<x);
do j--;while(a[j]<x);
if(i<j)swap(a[i],a[j]);
}
quick_sort(a,l,j);
quick_sort(a,j+1,r);
}
2.归并排序
每次将一个序列分成两个子序列,分别对它们进行归并排序,然后将两个有序的子序列合并成一个有序的序列,直到所有元素都被排序为止.
可用于求逆序对
void merge_sort(int a[],int l,int r)
{
if(l>=r)return;
int mid=(r+l)/2;//确定分界点
merge_sort(a,l,mid), merge_sort(a,mid+1,r);//递归分解排序左右两段
int k=0,i=l,j=mid+1;
while(i<=mid&&j<=r)//读写头移动比较两段,较小者读入临时数组
{
if(a[i]<=a[j])tmp[k++]=a[i++];
else tmp[k++]=a[j++];
}
while(i<=mid)tmp[k++]=a[i++];//剩下的按顺序全部移入临时数组
while(j<=r)tmp[k++]=a[j++];
for(i=l,j=0;i<=r;i++,j++)a[i]=tmp[j];//临时数组返回
}
<3>.二分
1.整型
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
bool check(int x) {/* ... */} // 检查x是否满足某种性质
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
2.浮点
bool check(double x) {/* ... */} // 检查x是否满足某种性质
double bsearch_3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度,取决于题目对精度的要求
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
<4>.前缀和&&差分
1.一维
前缀和:
初始化:for (int i = 1; i <= n; i++)a[i] += a[i - 1]; //O(n)
输出:a[r]-a[l];//(l,r]的区间和 O(1)
差分:
void insert(int l,int r,int q){b[l]+=q;b[r+1]-=q;} //[l,r]间加上q
2.二维
前缀和:
初始化:for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
输出:cout<<a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];
差分:
void insert(int x1,int y1,int x2,int y2,int c)
{b[x1][y1]+=c;b[x2+1][y1]-=c;b[x1][y2+1]-=c;b[x2+1][y2+1]+=c;}
//(x1,y1),(x2,y2)间加上c
<5>.递推&&递归
递推和递归是两种常用的解决问题的方法,它们都是利用已知的条件来推导出未知的结果,但是它们的思路和方向是相反的。
递推:由已知推未知,即从一个或多个初始状态出发,按照一定的规律或公式,逐步推导出目标状态。递推的优点是简单直观,不需要额外的空间;缺点是有些问题难以找到递推公式,或者递推公式过于复杂。
递归:自己调用自己(从未知回溯到已知),即将一个复杂的问题分解为一个或多个相同或相似的子问题,然后对子问题进行同样的分解,直到达到一个可以直接求解的基本问题。递归的优点是可以简化问题的结构,使得代码更加简洁优雅;缺点是需要额外的空间来保存递归调用栈,且有可能出现栈溢出或重复计算的问题。
<6>.位运算
位运算指直接操作type的二进制表示,即对每个二进制位进行运算。位运算有以下几种基本操作:
• &:按位与,对应位都为1则结果为1,否则为0;
• |:按位或,对应位有一个为1则结果为1,否则为0;
• ^:按位异或,对应位不同则结果为1,否则为0;
• ~:按位取反,每个位取反;
• >>:右移,将二进制数向右移动指定位数,左边补0或符号位;
• <<:左移,将二进制数向左移动指定位数,右边补0。
位运算的优点是速度快,可以实现一些高效的算法和技巧;缺点是可读性差,容易出错。位运算的常见应用场景有:
• 判断某个数是否为2的幂次:n > 0 && (n & (n - 1)) == 0;
• 求某个数的二进制表示中1的个数:while (n) { n = n & (n - 1); count ++ ; };
• 交换两个数的值:a = a ^ b; b = a ^ b; a = a ^ b;
• 实现加法运算:while (b) { int c = a & b; a = a ^ b; b = c << 1; }。
<7>.离散化
离散化是一种常用的处理数据的方法,它可以将一些不连续或范围很大的数据映射到一个较小的区间,从而简化问题的复杂度,节省空间和时间。离散化的基本思想是:对于一些只关心数据之间的相对大小或顺序的问题,我们可以将数据按照从小到大的顺序排序,然后用它们在排序后的序列中的位置来代替它们的原始值,这样就可以将数据压缩到一个较小的区间,同时保持数据之间的相对大小或顺序不变。离散化的常见应用场景有:
• 处理离线查询问题,如区间修改和查询、扫描线算法等;
• 处理树状数组、线段树等数据结构的下标问题,如求逆序对、区间修改和查询等;
• 处理哈希表、集合等容器的空间问题,如去重、查找等。
离散化的具体实现方法有:
• 使用排序+二分查找,先将数据排序去重,然后对每个数据进行二分查找,找到它在排序后的序列中的位置,作为它的新值;
• 使用排序+双指针,先将数据排序去重,然后用一个指针遍历原始数据,另一个指针遍历排序后的数据,当两个指针指向的值相等时,将排序后的数据的位置作为原始数据的新值;
• 使用哈希表或集合,先将数据放入哈希表或集合中去重,然后遍历哈希表或集合中的数据,按照从小到大的顺序给每个数据赋予一个新值。
<8>.区间最值问题(RMQ): st表
区间最值问题(RMQ)是一类常见的查询问题,它要求在一个序列中快速地找出某个区间内的最大值或最小值。st表是一种解决RMQ问题的高效算法,它可以在O(nlogn)的时间内预处理出一个二维数组st[i][j],表示从第i个元素开始长度为2j的区间内的最大值或最小值。然后对于任意一个查询区间[l,r],我们可以将它分成两个长度相等且互不重叠的子区间[l,mid]和[mid+1,r],其中mid=l+2k-1,k是满足2k<=r-l+1的最大整数。这样我们就可以用st[l][k]和st[r-2k+1][k]表示这两个子区间内的最大值或最小值,然后取二者中较大或较小者作为整个区间内的最大值或最小值。这样就可以在O(1)的时间内回答每个查询。st表的优点是预处理和查询都很快,且支持在线查询;缺点是占用较多空间,并且不支持修改操作。
//预处理st数组
for (int i = 1; i <= n; i ++ ) st[i][0] = a[i]; //长度为1的区间最小值就是自身
for (int j = 1; j <= log(n) / log(2); j ++ ) //枚举区间长度的指数部分
for (int i = 1; i + (1 << j) - 1 <= n; i ++ ) //枚举区间起点,注意不要越界
st[i][j] = min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]); //利用状态转移方程
//处理m个查询
while (m -- )
{
int l, r;
scanf("%d%d", &l, &r);
int k = log(r - l + 1) / log(2); //计算区间长度的指数部分
//输出区间[l,r]内的最小值
printf("%d\n", min(st[l][k], st[r - (1 << k) + 1][k]));
}
Orz