第一章-基础算法
第二章以及其他还在整理ing~
学习路线：
- 课上听懂内容
- 学会写模板（能够背下来并且修改） tips:多参加AcWing的挑战模式
- 课下运用（大量刷题，洛谷+AcWing打卡）
01-排序和二分
Day1
排序只讲快排和归并（用的比较多且代码简短），其余算法暂时不说（基数排序后面会单独讲）
Quick_Sort
快排基于的是分治的思想
题目链接：785.快速排序
基本步骤
- 确定分界点x：左/右边界or随机选取
- 调整区间：使得左区间元素均小于等于x，右边界均大于等于x
- 递归：继续按照1、2、3步处理左右区间
[HTML_REMOVED]最为关键的一步就是如何优雅的调整区间[HTML_REMOVED]
调整区间
利用i、j两个指针，初始时i指向左边界，j指向右边界
- i右移，直到i指向元素大于等于x，j左移知道j指向元素小于等于x
- swap(i,j)，且i++,j–//交换i、j指针指向的元素（保证了i、j左右侧元素始终大于or小于x）
- 当i>=j时，跳出循环
- 细节注意看[HTML_REMOVED]注释[HTML_REMOVED]
PLUS：关于解决快排稳定性的问题
其实非常简单，只需要将下标加入快排比较的内容即可，
pair<int,int>first存储值，second存储下标，然后先比较值再比较下标。（当然这个没什么软用就是了😂）
代码模板1：选取左右边界为分界点
该类选取方式对于上面那道例题会TLE（因为存在超长倒序数组）
void Quick_Sort(int *arr,int l,int r){
if(l>=r)return;
int x=arr[l],i=l-1,j=r+1;//这里扩大边界的原因时因为每次指针调整的时候指针会向中间移动一次
while(i<j){
do i++;while(arr[i]<x);
do j--;while(arr[j]>x);
if(i<j)swap(arr[i],arr[j]);
}
//此时i可能等于j也可能大于j
//注意i和j能保证的只有左侧和右侧是大于等于x的
Quick_Sort(arr,l,j);//注意j不能写成j-1,因为j的右侧均大于等于x,-1会漏掉一个
Quick_Sort(arr,j+1,r);
}//可以思考一下分治的时候如何选取i
//比较对称的写法Quick_Sort(arr,l,i-1);Quick_Sort(arr,j+1,r);
//注意一下x和i、j的选取问题(否则会出现Se)
代码模板2：选取中心为分界点
void Quick_Sort(int *arr,int l,int r){
if(l>=r)return;
int i=l-1,j=r+1,x=arr[l+r>>1];//随机选取版本:选中间的值即可
//这里扩大边界的原因时因为每次指针调整的时候指针会向中间移动一次
while(i<j){
do i++;while(arr[i]<x);
do j--;while(arr[j]>x);
if(i<j)swap(arr[i],arr[j]);
}
Quick_Sort(arr,l,j);//注意j不能写成j-1,因为j的右侧均大于等于x,-1会漏掉一个
Quick_Sort(arr,j+1,r);
}
拓展：选取排序后处于arr[k]的数
快排的简单应用，仔细思考即可
代码模板
int Quick_Sort(int *arr,int l,int r,int k){//保证k一定再l-r的范围内
if(r==l)return arr[k];
int i=l-1,j=r+1,x=arr[l+r>>1];
while(i<j){
do i++;while(arr[i]<x);
do j--;while(arr[j]>x);
if(i<j)swap(arr[i],arr[j]);
}
if(k<=j)return Quick_Sort(arr,l,j,k);
else Quick_Sort(arr,j+1,r,k);
}
Merge_Sort
同样基于的是分治的思想，只不过是先分治再合并
- 确定分界点：$m=(l+r)/2$ 确定的是下标的位置
- 分治左右数组
- 将有序的左右边界合并（要利用一临时数组tmp保存合并内容后再存回原数组）
归并排序注意点比较少，直接看代码模板即可
代码模板
void Merge_Sort(int *arr,int* tmp,int l,int r){
if(r<=l)return;
int mid=l+r>>1;
Merge_Sort(arr,tmp,l,mid), Merge_Sort(arr,tmp,mid+1,r);//合并
int k=l,i=l,j=mid+1;
//三目运算符缩短代码长度
while(i<=mid&&j<=r)tmp[k++]=(arr[i]<=arr[j])?arr[i++]:arr[j++];
while(i<=mid)tmp[k++]=arr[i++];
while(j<=r)tmp[k++]=arr[j++];
for(k=l;k<=r;k++)arr[k]=tmp[k];
}//简简单单
整数二分
非常蛋疼的一个东西，主要是因为有很多边界问题
二分的本质：注意二分的本质并不是单调性，而是一种性质边界的查找
只要某范围有一个性质，那么我们就可以通过二分来划分这个性质，最终得到的左半部分满足一种性质，右半部分满足另外一种性质，于是可以分别得到了两种性质的边界。
所以可以衍生出两种查找方法：查找符合条件的左边界、查找不符合条件的右边界（具体见下图）
二分书写的基本思路：
- 考虑清楚要查找的条件
- 根据条件确定应该查找条件的右边界还是左边界
- 考虑边界条件：左边界$mid=\frac{l+r}{2}$,右边界$mid=\frac{l+r+1}{2}$（参见上图）
- 考虑最左右端的边界条件（是否要返回-1？）
这里以查找数组内小于target的最大idx和大于等于target的最小idx为例
Plus：这里返回$l$还是$r$都是一样的
查找左半部分性质的边界：查找条件内最大idx
- 条件为小于target的最大idx
value<target - 所以应该查找右边界
- $mid=\frac{l+r+1}{2}$
inline bool Check(int value,int target){return value<target;}
//inline:声明为内联函数，可以大大减少函数栈的消耗,适用于代码长度短且调用频繁的函数
int B_Search(int *arr,int l,int r,int target){
int mid;
while(l<r){
mid=l+r+1>>1;//查找性质右边界(如果按照mid=l+r>>1,当l=r-1时，就会出现死循环)
if(Check(arr[mid],target))l=mid;
else r=mid-1;
}
return Check1(arr[l],target)?l:-1;//未找到返回-1
}
查找右半部分性质的边界：查找条件内最小idx
inline bool Check(int value,int target){return value>=target;}
int B_Search(int *arr,int l,int r,int target){
int mid;
while(l<r){
mid=l+r>>1;//查找性质左边界
if(Check(arr[mid],target))r=mid;
else l=mid+1;
}
return Check2(arr[l],target)?l:-1;
}//这种模板关键的点就是Check函数的使用非常棒！
浮点数二分
比较简单，因为不存在边界问题
就以一道题目为例好了：790.数的三次方根
浮点二分模板
#include<iostream>
#include<cmath>
using namespace std;
const double eps=1e-8;
double B_Search_Double(double target,double l=-100,double r=100){
//l,r可以根据题目适当调节范围
double mid;
while(r-l>eps){
mid=(l+r)/2;
if(pow(mid,3)>=target)r=mid;
else l=mid;
}
return mid;
}
int main(){
double x;
scanf("%lf",&x);
printf("%.6lf", B_Search_Double(x));
return 0;
}
02-高精度、前缀和与差分
Day2
高精度
Java中有大整数类，Python中自带整数无限大，唯有C++还是要苦逼的学高精度呜呜呜~
通俗来讲高精度就是各类大整数加减法、乘除法等等
常见考法：
- A+B：长度一般为$10^6$
- A-B：长度同样一般为$10^6$
- A*b：大整数（$len \le 10^6$）乘以小整数（$value\le 10^9$）
- A/b：数据范围同上
- A*B：大整数相乘，需要利用FFT（傅里叶变换，一般考的很少）
- A/B：这就更难了，估计不会考吧
注意点
- 数组从高到低存，相当于反向存储（避免进位时的数组平移）
[HTML_REMOVED]其实思路并不难想，关键是能否实现一个通用的模板[HTML_REMOVED]
大整数加法模板：采用动态数组vector实现，非常简洁优美
#include<iostream>
#include<vector> //一般使用vector来进行高精度乘法的运算
using namespace std;
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;
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--)printf("%d",C[i]);
return 0;
}
大整数减法模板：同样非常简洁
#include<iostream>
#include<vector> //一般使用vector来进行高精度乘法的运算
using namespace std;
bool Cmp(vector<int> &A,vector<int> &B){
if(A.size()!=B.size())return A.size()>B.size();
for(int i=A.size()-1;i>=0;i--)
if(A[i]!=B[i])return A[i]>B[i];
return true;//全相等
}//判断A是否大于等于B
vector<int> Sub(vector<int> &A,vector<int> &B){//注意这里不能返回局部对象的引用
//此时需要保证A是大于等于B的
vector<int> C;
int t=0;//记录是否需要进位
for(int i=0;i<A.size()||i<B.size();i++){
t=A[i]-t;
if(i<B.size())t-=B[i];
C.push_back((t+10)%10);
t=(t<0)?1: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');
//简化代码量
bool flag=Cmp(A,B);
auto C=(flag)?Sub(A,B):Sub(B,A);
if(!flag)putchar('-');
for(int i=C.size()-1;i>=0;i--)printf("%d",C[i]);
return 0;
}
大整数乘法模板：大整数A乘以小整数b
#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()||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();//去除前导0
return C;
}
int main(){
string a;
int b;//因为b不是大整数(b<1e8)，所以直接使用int保存即可
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);//auto好用啊
for(int i=C.size()-1;i>=0;i--)printf("%d",C[i]);
return 0;
}
大整数除法模板
#include<iostream>
#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=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();//去除前导0
return C;
}
int main(){
string a;
int b,r=0;
vector<int> A;
cin>>a>>b;
for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
vector<int> C=Div(A,b,r);
for(int i=C.size()-1;i>=0;i--)printf("%d",C[i]);
printf(" %d",r);
return 0;
}
前缀和
基本思想非常简单，简单到没有模板
比方说我这里有一个数组$arr[N]$,再定义一个$sum[N]$，定义$sum[i]$为$arr$数组的前$i$项之和（注意arr数组的存储从下标1开始，方便计算）
前缀和一般用于解决该类问题：查询一个数组再一块区间的和，并且一定是多次查询，不然前缀和没有意义
时间复杂度：$O(n)$
一维前缀和
模板（勉强算吧）
#include<iostream>
using namespace std;
const int N=1e6+10;
int arr[N],sum[N];
int main(){
int n,m,l,r;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&arr[i]);
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+arr[i];//构造前缀和数组
for(int i=0;i<m;i++){
scanf("%d %d",&l,&r);
printf("%d\n",sum[r]-sum[l-1]);
}
return 0;
}
二维前缀和
实例（模板题）：796.子矩阵的和
代码实现：不算太难，只要注意前缀和的构造和区间和的计算即可（之后在差分中还会用到）
#include<iostream>
using namespace std;
const int N=1e3+10;
int arr[N][N],sum[N][N];
//子矩阵的和:前缀和的二维应用(动态规划中也有出现)
int main(){
int i,j;
int n,m,q;
int x1,y1,x2,y2;
scanf("%d %d %d",&n,&m,&q);
for(i=1;i<=n;i++){
for(j=1;j<=m;j++)
scanf("%d",&arr[i][j]);
}//读取arr数组
for(i=1;i<=n;i++){
for(j=1;j<=m;j++)
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+arr[i][j];
}//构造前缀和数组
for(i=1;i<=q;i++){
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
printf("%d\n",sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]);
}//求解区间和
return 0;
}
差分
差分的概念：求前缀和的[HTML_REMOVED]逆运算[HTML_REMOVED]！！
假想一个数组A，如果B是A数组的前缀和，那么A就是B数组的差分
$A[i]=B[i]-B[i-1]$
那么差分有啥作用嘞？（参照线段树和树状数组）
用途（主要）：可以在$O(1)$的时间内给原数组在$[l,r]$的范围内的所有数+c
Plus：差分数组的初始化同样可以用上述的方式进行（简化代码量）
一维差分
模板题：797.差分
#include<iostream>
using namespace std;
const int N=1e6+10;
int a[N],b[N];
//a为前缀和数组，b为差分数组(只不过做题时一般只需要用到差分即可)
//差分数组的初始化+添加
inline void Insert(int l,int r,int c){b[l]+=c;b[r+1]-=c;}
int main(){
int i,n,m;
int l,r,c;
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=n;i++)Insert(i,i,a[i]);//差分
for(i=0;i<m;i++){
scanf("%d %d %d",&l,&r,&c);
Insert(l,r,c);
}
int sum=0;
for(i=1;i<=n;i++){//输出原数组
sum+=b[i];
printf("%d ",sum);
}
return 0;
}
二维差分
与一维的关系可以参照二维前缀和
就是注意添加的范围从$[l,r]$变为了从$[(x1,y1),(x2,y2)]$
模板题：798.差分矩阵
#include<iostream>
using namespace std;
const int N=1e3+10;
int A[N][N],B[N][N];//这里无法做到A,B混用的原因就是差分矩阵的初始化比较特殊
inline 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 i,j,n,m,q;
int x1,y1,x2,y2,c;
scanf("%d %d %d",&n,&m,&q);
for(i=1;i<=n;i++){
for(j=1;j<=m;j++)
scanf("%d",&A[i][j]);
}
for(i=1;i<=n;i++){
for(j=1;j<=m;j++)
Insert(i,j,i,j,A[i][j]);
}//差分矩阵初始化
for(i=1;i<=q;i++){
scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&c);
Insert(x1,y1,x2,y2,c);
}
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
A[i][j]=A[i][j-1]+A[i-1][j]-A[i-1][j-1]+B[i][j];
printf("%d%c",A[i][j],(j==m)?'\n':' ');
}
}
return 0;
}
03-双指针算法、位运算、离散化+区间合并
Day3
学习了双指针算法和位运算的一些操作
双指针算法
核心思想：不太好说，建议直接上题来理解
就是利用某些性质，将算法的时间复杂度从$O(n^2)$优化到$O(n)$
基本代码模板
cpp for(i=0;i<n;i++){ while(j<n&&Check(i,j))j++; i=j;(这一步看情况再写) }
模板题：799.最长连续不重复子序列
#include<iostream>
#include<cstring>
using namespace std;
#define Max(a,b) ((a)>(b)?(a):(b))
const int N=1e5+10;
int Arr[N],Hash[N];
//例题:最长连续不重复子序列
inline int Check(int j){//Check(j)=true代表从i-j中无重复子序列
if(Hash[Arr[j]]==0)return Hash[Arr[j]]=1,true;
else return false;
}
//双指针牛逼
int main(){
int i,j=0,n,maxn=0;
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d",&Arr[i]);
for(i=0;i<n;i++){
while(j<n&&Check(j))j++;
maxn=Max(maxn,j-i);
Hash[Arr[i]]=0;
}
printf("%d",maxn);
return 0;
}
位运算
只讲两种最常用的操作
- n的二进制表示中，第k位数字是$0\ or\ 1$（第k位是从个位开始算的，比方说$15$的第0位就是$1$）
- 查看lowbit（x的最后一位1，注意返回的不是idx,而是100…0）
操作1：
- 先将第k位移动到最后一位：
n>>k - 再查看个位：
n&1
inline value(int x,int k){x=x>>k;return x&1;}
操作2：树状数组的基本操作
inline lowbit(int x){return x&(-x);}//具体原因可以在CSDN上查，自己也比较容易想(注意补码和原码之间的关系即可)
Plus：利用^可以实现‘0’和‘1’的快速转换（不需要进行类型转换啥的，减少代码量）
char c='0';
c=c^1;//c='1'
c=c^1;//c='0'
//这是一位1和0的ascii分别为48和49，只有末尾位不同
小例子：801.二进制中1的个数
#include<iostream>
using namespace std;
inline int lowbit(int x){return x&(-x);}
int main(){
int x,n,cnt;
scanf("%d",&n);
for(int i=0;i<n;i++){
cnt=0;
scanf("%d",&x);
while(x>0){x-=lowbit(x);cnt++;}
printf("%d ",cnt);
}
return 0;
}
树状数组与离散化
树状数组
内容过多，暂时搁置
离散化
（这里指对整数进行离散化）
这里有一堆数
值域：$0-10^9$ 个数：$10^5$
此时我们需要把这个序列映射到[0,n-1]的自然数中（和hash思路一致，只不过是映射到下标）
例子：A[]={1,2,100,3000,10000000}$\rightarrow${0,1,2,3,4}
应用场景举例：超大区间和问题
问题：
- A中可能存在重复元素（所以需要先去重，为了方便去重，所以采用
vector来存储数组）- 如何快速算出A[i]离散化后的值是多少
模板题：802.区间和
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1e5+10;
const int inf=1e9+10;
pair<int,int> OP[N];//用于记录操作
vector<pair<int,int>> A;
int Find_L(int x){//左边界
int l=0,r=A.size()-1,mid;
while(l<r){
mid=l+r>>1;
if(A[mid].first>=x)r=mid;
else l=mid+1;
}
return l;
}
int Find_R(int x){//右边界
int l=0,r=A.size()-1,mid;
while(l<r){
mid=l+r+1>>1;
if(A[mid].first<=x)l=mid;
else r=mid-1;
}
return l;
}
int main(){
A.reverse(N);//预先分配N大小的空间，减少重新分配空间带来的额外开销，降低时间常数
//但是貌似没快多少，也就快了几十ms
int n,m,x,c,l,r;
scanf("%d %d",&n,&m);
A.push_back({inf,0});
A.push_back({-inf,0});//方便之后的查找
for(int i=0;i<n;i++){
scanf("%d %d",&x,&c);
OP[i]={x,c};
A.push_back({x,0});
}
sort(A.begin(),A.end());
A.erase(unique(A.begin(),A.end()),A.end());//排序+去重操作
for(int i=0;i<n;i++)
A[Find_L(OP[i].first)].second+=OP[i].second;
for(int i=1;i<A.size();i++)
A[i].second+=A[i-1].second;//构造前缀和
for(int i=0;i<m;i++){
scanf("%d %d",&l,&r);
l=Find_L(l);r=Find_R(r);//查找对应的左右边界
printf("%d\n",A[r].second-A[l-1].second);
}
return 0;
}
区间合并
非常简单，本质思想是贪心
下面直接给出代码
模板题：803.区间合并
#include<iostream>
#include<algorithm>
using namespace std;
#define Max(a,b) ((a)>(b)?(a):(b))
const int N=1e5+10;
const int inf=1e9+10;
pair<int,int> A[N];
int main(){
int n,s,t,cnt=0,pre_end=-inf;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d %d",&s,&t);
A[i]={s,t};
}
sort(A,A+n);
for(int i=0;i<n;i++){
if(A[i].first>pre_end)cnt++;
pre_end=Max(pre_end,A[i].second);
}
printf("%d",cnt);
return 0;
}
小结
寒假40天刷完算法基础+蓝桥杯A+B嗷，接着整理第二章去了~
说错了应该是等期末考完再整理第二章orz
