1.基础算法

快速排序

1.快速排序算法模板

int 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];
    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);
}

int main()
{
    quick_sort(q, 0, n - 1);
}

2.快速选择算法（第k大的数）

int q[N];
int quick_sort(int l,int r,int k){
    if(l==r)return q[l];
    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]);
    }

    int sl=j-l+1;
    if(sl>=k)quick_sort(l,j,k);
    else quick_sort(j+1,r,k-sl);
}
int main(){
    printf("%d\n",quick_sort(0,n-1,k));
}

归并排序

1.归并排序算法模板

const int N = 1e5 + 10;

int a[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 = 0, i = l, j = mid + 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(i =l,j=0;i<=r; i ++, j ++ ) q[i] = tmp[j];
}

int main()
{
    merge_sort(a, 0, n - 1);
}

2.归并排序求逆序对数量

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
typedef long long LL;
int n;
int q[N],tmp[N];

LL merge_sort(int l,int r){
    if(l>=r)return 0;
    int mid=(l+r)/2;

    LL res=merge_sort(l,mid)+merge_sort(mid+1,r);

    int k=0,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(int i=l,j=0;i<=r;i++,j++)q[i]=tmp[j];

    return res;
}

int main(){
    cout<<merge_sort(0,n-1);
}

二分

1.二分模板(查找元素 k 的起始位置和终止位置)

整数二分 边界问题

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int q[N];
int main(){
    cin>>n>>m;

    for(int i=0;i<n;i++)scanf("%d",&q[i]);

    while(m--){
        int x;
        cin>>x;
        //查找起始位置
        int l=0,r=n-1;
        while(l<r){
            int mid=(l+r)/2;
            if(q[mid]>=x)r=mid;
            else l=mid+1;
        }

        if(q[l]!=x){
            cout<<"-1 -1"<<endl;
            continue;
        }
        else{//查找终止位置
            cout<<l<<" ";
            l=0,r=n-1;
            while(l<r){
                int mid=(l+r+1)/2;
                if(q[mid]<=x)l=mid;
                else r=mid-1;
            }
            cout<<l<<endl;
        }
    }
}

2.二分求浮点数的三次方根

#include<bits/stdc++.h>
using namespace std;

int main(){
    double x;
    cin>>x;
    double l=-1000,r=1000;
    while(r-l>1e-8){
        double mid=(l+r)/2;
        if(mid*mid*mid>=x)r=mid;
        else l=mid;
    }

    printf("%.6lf",l);
    return 0;
}

高精度

1.高精度加法（高精+高精）

#include<bits/stdc++.h>
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=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--){
        cout<<C[i];
    }
    return 0;
}

2.高精度减法（高精-高精）

#include<bits/stdc++.h>
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.back()==0&&C.size()>1){
        C.pop_back();
    }

    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--)cout<<C[i];
    }else{
        auto C=sub(B,A);
        cout<<"-";
        for(int i=C.size()-1;i>=0;i--)cout<<C[i];
    }

    return 0;
}

3.高精度乘法（高精*低精）

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;

vector<int> get_mul(vector<int> &A,int b){
    vector<int> C;

    int t=0;

    for(int i=0;i<=A.size()-1||t;i++){
        if(i<=A.size()-1)t+=b*A[i];
        C.push_back(t%10);
        t/=10;
    }
    while(C.back()==0&&C.size()>1)C.pop_back();
    return C;
}

int main(){
    string a;
    vector<int> A;
    int b;
    cin>>a>>b;
    for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
    auto C=get_mul(A,b);
    for(int i=C.size()-1;i>=0;i--)cout<<C[i];
    return 0;
}

4.高精度除法（高精/低精）

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;

vector<int> div(vector<int> &A,int &b,int &r){
    r=0;
    vector<int> C;
    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.back()==0&&C.size()>1)C.pop_back();

    return C;
}

int main(){
    string a;
    vector<int> A;
    int b;
    int r;
    cin>>a>>b;

    for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');

    auto C=div(A,b,r);

    for(int i=C.size()-1;i>=0;i--)cout<<C[i];
    cout<<endl<<r;


    return 0;
}

前缀和与差分

1.一维前缀和模板

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;

int a[N],sum[N];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];

    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];

    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<sum[r]-sum[l-1]<<endl;
    }
    return 0;
}

2.二维(矩阵)前缀和模板

#include<bits/stdc++.h>
using namespace std;

const int N=1e3+10;
int n,m,q;
int a[N][N],sum[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++){
            sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
        }
    }

    while(q--){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]<<endl;
    }
}

3.一维差分模板

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;

int a[N],b[N];
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)b[i]=a[i]-a[i-1];

    while(m--){
        int l,r,c;
        cin>>l>>r>>c;
        b[l]+=c;
        b[r+1]-=c;
    }

    for(int i=1;i<=n;i++){
        b[i]=b[i]+b[i-1];
    }
    for(int i=1;i<=n;i++)cout<<b[i]<<" ";
    return 0;
}

4.二维(矩阵)差分模板

#include<bits/stdc++.h>
using namespace std;

const int N=1e3+10;

int n,m,q;

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(){
    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++){
            insert(i,j,i,j,a[i][j]);
        }
    }

    while(q--){
        int x1,y1,x2,y2,c;
        cin>>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][j]+b[i-1][j]+b[i][j-1]-b[i-1][j-1];
            cout<<b[i][j]<<" ";
        }
        cout<<endl;
    }    

    return 0;
}

双指针

1.求最长连续不重复子序列

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
int a[N],s[N]; //a[]存数据，s[]记录每个数字出现的次数 
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
      scanf("%d",&a[i]);
    int res=0;
    for(int i=0,j=0;i<n;i++) //双指针 
    {
        s[a[i]]++; //指向一个数，就把对应数的次数+1 
        while(s[a[i]]>1) //当次数>1时，说明当前区间有重复元素，就是a[i] 
        {
            s[a[j]]--; //把j对应位置的数删掉 
            j++;
        }
        res=max(res,i-j+1); //每次取不包含重复的数的连续区间的长度的最大值 
    }    
    printf("%d\n",res);
    return 0;
}

2.两个有序数组元素的目标和

给定两个升序排序的有序数组 A 和 B，以及一个目标值 x

数组下标从 0 开始。

求出满足 A[i]+B[j]=x 的数对 (i,j)。

#include<bits/stdc++.h>
using namespace std;

const int N= 1e5+10;

int A[N],B[N];

int main(){
    int n,m,x;
    cin>>n>>m>>x;
    for(int i=0;i<n;i++){
        scanf("%d",&A[i]);
    }
    for(int i=0;i<m;i++){
        scanf("%d",&B[i]);
    }

    for(int i=0,j=m-1;i<n;i++){
        while(A[i]+B[j]>x)j--;
        if(A[i]+B[j]==x)cout<<i<<" "<<j<<endl;
    }
    return 0;
}

3.判断 a 序列是否为 b 序列的子序列

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;

int n,m;

int a[N],b[N];

int main(){
    cin>>n>>m;

    for(int i=0;i<n;i++)scanf("%d",&a[i]);

    for(int i=0;i<m;i++)scanf("%d",&b[i]);

    int i=0,j=0;
    while(i<n&&j<m){
        if(a[i]==b[j])i++;
        j++;
    }
    if(i==n)puts("Yes");
    else puts("No");

    return 0;
}

位运算

1.求n的第k位数字模板

n>>k&1

2.返回n的最后一位1 lowbit模板

lowbit(x) ：返回x的最后一位1

比如 x=101000 lowbit(x)=1000

int lowbit(int n){
    return n&-n;//return n&(~n+1);
}

3.求一个数二进制中1的个数 lowbit运用

#include<bits/stdc++.h>
using namespace std;

int lowbit(int n){
    return n&-n;
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        int res=0;
        while(x){
            x-=lowbit(x);
            res++;
        }
        cout<<res<<" ";
    }
    return 0;
}

离散化

1.求离散区间和(大值域)

#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;

const int N = 300010;

int n, m;
int a[N], s[N];

vector<int> alls;//用来保存真实的下标和想象的下标的映射关系
vector<PII> 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; //  因为要求前缀和，故下标从1开始方便，不用额外的再处理边界。
}
int main () {
    cin >> n >> m;
    for (int i = 0; i < n;++ i) {
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});

        alls.push_back(x);//先把下标放入向量中 统一离散化 
    }
    for (int i = 0; i < m;++ i) {
        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());//去除重复元素
   // 1）erase( pos, n); 删除从pos开始的n个字符，例如erase( 0, 1)，
   // 删除0位置的一个字符，即删除第一个字符
    //（2）erase( position); 
    //删除position处的一个字符（position是个string类型的迭代器）
    //（3）erase（first，last）;删除从first到last之间的字符，
   // （first和last都是迭代器）last 不能是x.end()
    //unique 使用 必须要先过一遍sort排序。再者，unique函数返的返回值是
    //一个迭代器，它指向的是去重后容器中不重复序列的最后一个元素的
    //下一个元素。所以如果 想要得到不重复元素的个数就需要用返回值-开始地址。
    for ( auto item : add) { //先对添加里的元素映射 赋值 
        int x = find(item.first);//找到x的映射值 往原数组中加c 
        a[x] += item.second; // 处理插入
    }
    //for(auto a:b)中b为一个容器，效果是利用a遍历并获得b容器中的每一个值，
    //但是a无法影响到b容器中的元素。
    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;
    }//每个元素都对应一组{first, first}键值对（pair），
    //键值对中的第一个成员称为first，第二个成员称为second.
    return 0;
}

区间合并

1.合并所有有交集的区间

给定 n 个区间 [li,ri]，要求合并所有有交集的区间。

#include<bits/stdc++.h>
using namespace std;

int n;
typedef pair<int,int> PII;

vector<PII> segs;

int main(){
    cin>>n;

    for(int i=0;i<n;i++){
        int l,r;
        cin>>l>>r;
        segs.push_back({l,r});
    }

    sort(segs.begin(),segs.end());//按左端点排序
    vector<PII> res;
    int st=-2e9,ed=-2e9;
    for(auto seg:segs){
        if(seg.first>ed){  //情况1：两个区间无法合并
            if(st!=-2e9){
                res.push_back({st,ed});
            }
            st=seg.first,ed=seg.second;
        }else{//情况2：两个区间可以合并
            ed=max(ed,seg.second);
        }
    }
    if(ed!=-2e9)res.push_back({st,ed});
    cout<<res.size();
}