快速排序
模板题：785. 快速排序 - AcWing题库
思路：
定义一个x（一般喜欢用中间的），我们快速排序，让x左边的都比它小，同时让右边的都比它大。然后像二分一样不断细分，缩小范围进行同样的操作。
细节：让x左边的都比它小，同时让右边的都比它大。双指针算法，只要满足条件就移动指针，否则就交换两个数。
像二分一样不断细分，缩小范围进行同样的操作。递归操作。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,q[N];
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];//这里多一位的原因是下面的do-whilewhile(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);
}
signed main()
{cin>>n;for(int i=1;i<=n;i++){cin>>q[i];}quick_sort(q,1,n);for(int i=1;i<=n;i++){cout<<q[i]<<" ";}return 0;
}归并排序
模板题：787. 归并排序 - AcWing题库
思路：确定分界点，递归排序，归并--合二为一。
两段排好序后，用两个指针分别指向两端中最小的数。比较两个指针的大小，输出小的，移动指针。直到一段被输出完，直接按顺序输出另一段即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,q[N],tmp[N];
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=1,i=l,j=mid+1;while(i<=mid&&j<=r){if(q[i]<=q[j]) tmp[k++]=q[i++];else tmp[k++]=q[j++];}//退出了就说明，i>mid或j>r，就需要把剩下的数直接放进数组里 while(i<=mid) tmp[k++]=q[i++];while(j<=r) tmp[k++]=q[j++];for(i=l,j=1;i<=r;i++,j++){q[i]=tmp[j];}
}
signed main()
{cin>>n;for(int i=1;i<=n;i++) cin>>q[i];merge_sort(q,1,n);for(int i=1;i<=n;i++) cout<<q[i]<<" ";return 0;
}逆序对的数量
788. 逆序对的数量 - AcWing题库
看题解：AcWing 788. 逆序对的数量--图解 - AcWing
（这篇题解里很多大佬欸~看完评论才懂）
计算逆序对的数量，我们的思路是在归并过程中找出逆序对数量。
每次归并所使用的上次归并的结果数组都是有序的，所以如果[l,mid] 之间如果有q[i]大于右边数组q[j]的值，则[i,mid]之间的所有值都是大于q[j]的，可以用mid-i+1来计算
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,q[N],tmp[N];
long long res;
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=1,i=l,j=mid+1;while(i<=mid&&j<=r){if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];else{res += mid - i + 1;tmp[k ++ ] = q[j ++ ];}}while(i<=mid) tmp[k++]=q[i++];while(j<=r) tmp[k++]=q[j++];for(i=l,j=1;i<=r;i++,j++){q[i]=tmp[j];}
}
signed main()
{cin>>n;for(int i=1;i<=n;i++) cin>>q[i];merge_sort(q,1,n);cout<<res;return 0;
}二分
整数二分
789. 数的范围 - AcWing题库
注意这个板子在if里面最后给l或r赋值，必须要+1或者-1。用res记录时不用担心漏掉，不用res记录的情况正好需要-1/+1
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,q,a[N];
int sl(int x)//左边界
{int l=0,r=n-1,res=-1;while(l<=r){int mid=l+r>>1;if(a[mid]>=x){res=mid;r=mid-1;}else l=mid+1;}if(a[res]==x) return res;else return -1;
}
int sr(int x)
{int l=0,r=n-1,res=-1;while(l<=r){int mid=l+r>>1;if(a[mid]<=x){res=mid;l=mid+1;}else r=mid-1;} if(a[res]==x) return res;else return -1;
}
signed main()
{cin>>n>>q;for(int i=0;i<n;i++) cin>>a[i];while(q--){int k;cin>>k;cout<<sl(k)<<" "<<sr(k)<<endl;}return 0;
}个人喜欢用的板子：整数二分
int l=1,r=n,res=-1;
while(l<=r)
{int mid=l+r>>1;if(check(mid)){res=mid;l=mid+1;}else r=mid-1;
}实数二分
790. 数的三次方根 - AcWing题库
纯板子题
#include<bits/stdc++.h>
using namespace std;
double n;
signed main()
{cin>>n;double l=-1e4,r=1e4;for(int i=1;i<=100;i++)//二分100次 {double mid=(l+r)/2;if(pow(mid,3)<=n){l=mid;}else r=mid; }printf("%.6f",l);return 0;
}
放一个实数二分的模板：
double l=-1e4,r=1e4;//这里是数的范围for(int i=1;i<=100;i++)//二分100次，100次就够了很精细了 {double mid=(l+r)/2;if(check(mid)){l=mid;}else r=mid; }
//最后输出l或者r都行，因为我们已经很精细了，这俩值最后是相等的高精度
加法
791. 高精度加法 - AcWing题库
模拟题，可以参考之前写的一篇博客。
千万要记得字符数组到整型数组的转换!!
【算法】模拟，高精度_想七想八不如11408的博客-CSDN博客
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
string A,B;
int a[N],b[N],c[N];
signed main()
{cin>>A>>B;for(int i=A.length()-1,j=1;i>=0;i--,j++){a[j]=A[i]-'0'; } for(int i=B.length()-1,j=1;i>=0;i--,j++){b[j]=B[i]-'0'; } int len=max(A.length(),B.length());for(int i=1;i<=len;i++){c[i]+=a[i]+b[i];c[i+1]=c[i]/10;c[i]%=10;}if(c[len+1]) len++;for(int i=len;i>=1;--i) cout<<c[i];return 0;
}减法
792. 高精度减法 - AcWing题库
是一个模拟题。
我们主要写的是大数减小数的情况，因此前面要讨论：
如果完全一样，直接返回0。
再对长度进行讨论，主要是长度相同的情况。从高位到低位进行比较，如果a大，我们就可以放心了。如果相等就继续下一位讨论，最后一种情况就是a小了，直接交换。
减法就是加法的一种特殊形式，加上一个负数嘛。但是要注意加法是进位，相应的减法是减位。
最后也要记得去除前导0。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
string A,B;
int a[N],b[N],c[N];
int flag;//标记A,B是否交换过，也就代表是否有负号
signed main()
{cin>>A>>B;if(A.compare(B)==0){cout<<"0";return 0;}if(B.length()>A.length()){swap(A,B);flag=1;}else if(B.length()==A.length()){//长度相同 for(int i=0;i<A.length();i++){if((A[i]-'0')>(B[i]-'0'))//如果a大直接就结束循环了 {break;}else if((A[i]-'0')==(B[i]-'0')){continue;}else{swap(A,B);flag=1;}}} for(int i=A.length()-1,j=1;i>=0;i--,j++){a[j]=A[i]-'0';}for(int i=B.length()-1,j=1;i>=0;i--,j++){b[j]=B[i]-'0';b[j]=-b[j];}int len=max(A.length(),B.length());for(int i=1;i<=len;i++){c[i]+=a[i]+b[i];if(c[i]<0){a[i+1]--;c[i]+=10;}}while(!c[len]) len--;if(flag) cout<<"-";for(int i=len;i>=1;i--) cout<<c[i];return 0;
}乘法
793. 高精度乘法 - AcWing题库
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N],c[N];
signed main()
{string A,B;cin>>A>>B;int lena=A.length(),lenb=B.length();int len=lena+lenb;for(int i=lena-1,j=1;i>=0;j++,i--){a[j]=A[i]-'0';}for(int i=lenb-1,j=1;i>=0;j++,i--){b[j]=B[i]-'0';}for(int i=1;i<=lena;i++){for(int j=1;j<=lenb;j++){c[i+j-1]+=a[i]*b[j];}}for(int i=1;i<=len;i++){c[i+1]+=c[i]/10;c[i]%=10;}while(!c[len]) len--;for(int i=max(1,len);i>=1;i--) cout<<c[i];//注意0,0的情况 ,要输出一个0 return 0;
}除法
794. 高精度除法 - AcWing题库
模板是大数（高精度）除以小数
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int b,a[N],c[N];
int main()
{string A;cin>>A>>b;for(int i=0;i<A.length();i++){a[i]=A[i]-'0';}int r=0;for(int i=0;i<A.length();i++){r=r*10+a[i];c[i]=r/b;r%=b;}int k;for(int i=0;i<A.length();i++){if(!c[i]) continue;else{k=i;break;}}if(k==0&&c[0]==0)//说明都是0 {cout<<"0";}else{for(int i=k;i<A.length();i++) cout<<c[i];}cout << endl << r << endl;return 0;
}前缀和
【蓝桥杯】二分、前缀和、差分练习_想七想八不如11408的博客-CSDN博客
795. 前缀和 - AcWing题库
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],s[N];
signed main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]+a[i];}while(m--){int l,r;cin>>l>>r;cout<<s[r]-s[l-1]<<endl;}return 0;
}二维前缀和
796. 子矩阵的和 - AcWing题库
注意画图
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int a[N][N],s[N][N];
signed main()
{int n,m,q;cin>>n>>m>>q;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>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 x,y,xx,yy;cin>>x>>y>>xx>>yy;cout<<s[xx][yy]+s[x-1][y-1]-s[x-1][yy]-s[xx][y-1]<<endl;}return 0;
}差分
797. 差分 - AcWing题库
题解：AcWing 797. 算法基础班--第一章--11.一维差分模板 - AcWing
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N],m;
int b[N];//差分数组
signed main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];b[i]=a[i]-a[i-1];//构建差分数组 //这样的话，对b求前缀和就能得到a }while(m--){int l,r,c;b[l]+=c,b[r+1]-=c; //进行操作 }for(int i=1;i<=n;i++){a[i]=b[i]+a[i-1];//an = b1 + b2 + b3 + … + bncout<<a[i]<<" ";}return 0;
}二维差分
AcWing 798. 差分矩阵 - AcWing
#include<bits/stdc++.h>
using namespace std;
const int N =1010;
int n,m,q;
int a[N][N],b[N][N];
int main()
{cin>>n>>m>>q;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];}}while(q--){int x,y,xx,yy,c;cin>>x>>y>>xx>>yy>>c;b[x][y]+=c;b[xx+1][y]-=c;b[x][yy+1]-=c;b[xx+1][yy+1]+=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]+b[i][j]; } } for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<b[i][j]<<" ";}cout<<endl;}return 0;
}双指针
最长连续不重复子序列
799. 最长连续不重复子序列 - AcWing题库
#include<bits/stdc++.h>
using namespace std;
const int N =1e5+10;
int n;
int a[N],s[N];
int ans;//注意看题，是最长连续不重复的序列
int main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1,j=1;i<=n;i++){s[a[i]]++;while(s[a[i]]>1)//必须要注意这里是while，要把j移到能移到的最右边{s[a[j]]--;j++;}ans=max(ans,i-j+1); }cout<<ans;return 0;
}数组元素的目标和
800. 数组元素的目标和 - AcWing题库
#include<bits/stdc++.h>
using namespace std;
const int N =1e5+10;
int n,m,x;
int a[N],b[N];
signed main()
{cin>>n>>m>>x;for(int i=0;i<n;i++) cin>>a[i];for(int i=0;i<m;i++) cin>>b[i];int i=0,j=m-1;while(i<n&&j<m){if(a[i]+b[j]>x){j--;}else if(a[i]+b[j]<x){i++;}else{cout<<i<<" "<<j;return 0;}}return 0;
}判断子序列
2816. 判断子序列 - AcWing题库
#include<bits/stdc++.h>
using namespace std;
const int N =1e5+10;
int n,m;
int a[N],b[N];
signed main()
{cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=m;i++) cin>>b[i];if(n>m){cout<<"No"<<endl;return 0;}int i=1,j=1;while(i<=n&&j<=m){if(a[i]==b[j]){if(i==n){cout<<"Yes"<<endl;return 0;}j++;i++;}else{j++;}}cout<<"No"<<endl;return 0;
}位运算
把第k位移到最后一位 n>>k
看个位是几 x&1
举个栗子：
#include<bits/stdc++.h>
using namespace std;
const int N =1e5+10;
int n,m;
int a[N],b[N];
signed main()
{int n=10;//10的二进制表示是1010 for(int k=3;k>=0;k--){cout<<(n>>k&1)<<" ";}return 0;
}
lowbit操作（是树状数组的基本操作），是返回x的最后一位1
x=1010 lowbit(x)=10
x=101000 lowbit(x)=1000
lowbit(x)其实就是x&-x，
-x是原数的补码，是取反加1。-x=~x+1
x =101 0000 1000
~x =010 1111 0111
~x+1 = 010 1111 1000
x&-x=x&(~x+1) = 000 0000 1000
801. 二进制中1的个数 - AcWing题库
#include<bits/stdc++.h>
using namespace std;
const int N =1e5+10;
int lowbit(int x)
{return x&-x;
}
signed main()
{int n;cin>>n;while(n--){int x;cin>>x;int res=0;while(x) x-=lowbit(x),res++;cout<<res<<" ";}return 0;
}离散化
802. 区间和 - AcWing题库
“假定有一个无限长的数轴”，需要离散化。特点跨度很大，但非常稀疏。
#include<bits/stdc++.h>
using namespace std;
const int N =300010;
int n,m,a[N],s[N];typedef pair<int,int> PII;
vector<int> alls;//存所有待离散化的坐标
vector<PII> add,query;//存操作 int find(int x)
{int l=0,r=alls.size()-1,res=-1;while(l<=r){int mid=(l+r)>>1;if(alls[mid]>=x) r=mid-1,res=mid;else l=mid+1; } return res+1;//映射成从1开始
}
signed main()
{cin>>n>>m;for(int i=1;i<=n;i++){int x,c;cin>>x>>c;add.push_back({x,c});alls.push_back(x);}while(m--){int l,r;cin>>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());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];//处理前缀和for(auto item:query){int l=find(item.first),r=find(item.second);cout<<s[r]-s[l-1]<<endl;//前缀和 } return 0;
}区间合并
803. 区间合并 - AcWing题库
区间合并指的是合并两个有交集的区间。按区间左端点排序
#include<bits/stdc++.h>
using namespace std;
const int N =100010;
typedef pair<int,int> PII;
int n;
vector<PII> segs;
void merge(vector<PII> ®s)
{vector<PII> res;sort(segs.begin(),segs.end());int st=-2e9,ed=-2e9;for(auto seg:segs){if(ed<seg.first){if(st!=-2e9) res.push_back({st,ed});st=seg.first,ed=seg.second;}else ed=max(ed,seg.second);}if(st!=-2e9) res.push_back({st,ed});segs=res;
}
signed main()
{cin>>n;for(int i=1;i<=n;i++){int l,r;cin>>l>>r;segs.push_back({l,r});}merge(segs);cout<<segs.size()<<endl;return 0;
}第一章完结撒花，略略略~
