基础算法模板

快速排序模板

void quick_sort(int i,int j)
{
    if(i>=j) return;
    ary[0]=ary[rand()%(j-i+1)+i];
    int l=i-1,r=j+1;
    while(l<r)
    {
        do l++; while (ary[l]<ary[0]);
        do r--; while (ary[r]>ary[0]);
        if(l<r)
        {
            swap(ary[r],ary[l]);
        }
    }
    quick_sort(i,r);
    quick_sort(r+1,j);
}

快速选择模板（快排的变形，用于快速找出第k个数）

void quick_sort(int i,int j,int k)
{
    if(j<=i) return;
    ary[0] = ary[rand()%(j-i+1)+i];
    int l=i-1,r=j+1;
    while(l<r)
    {
        do l++; while(ary[l]<ary[0]);
        do r--; while(ary[r]>ary[0]);
        if(l<r) swap(ary[l],ary[r]);
    }
    int len=r-i+1;
    if(k<=len) quick_sort(i,r,k);
    else quick_sort(r+1,j,k-len);
}

二分思想模板

//找左边第一个
while(l<r)
{
    mid=(l+r)>>1;
    if(ary[mid] >= temp) r=mid;
    else l=mid+1;
}
//找右边第一个
while(l<r)
{
    mid=(l+r+1)>>1;
    if(ary[mid] <= temp) l=mid;
    else r=mid-1;
}

归并排序模板

void merge_sort(int ary[],int l,int r)
{
    if(l>=r) return;
    int mid=l+r>>1;
    merge_sort(ary,l,mid);merge_sort(ary,mid+1,r);
    int k=0,i=l,j=mid+1;
    while(i<=mid && j<=r )
        if(ary[i]<=ary[j]) temp[k++]=ary[i++];
        else temp[k++]=ary[j++];
    while(i<=mid) temp[k++]=ary[i++];
    while(j<=r) temp[k++]=ary[j++];
    for(i=l,j=0;i<=r;i++,j++) ary[i]=temp[j];
}

堆排序模板

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5+10;
int n,m,j;
int ary[N];


void down(int x)
{
    int i=x;
    if(2*x<=j && ary[2*x]<ary[i]) i=x*2;
    if(2*x+1<=j && ary[2*x+1]<ary[i]) i=x*2+1; 
    if(x!=i)
    {
        swap(ary[x],ary[i]);
        down(i);
    }
}

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

    for(int i=1;i<=n;i++) scanf("%d",&ary[i]);
    j=n;
    for(int i=n/2;i;i--) down(i);

    while(m--)
    {
        printf("%d ",ary[1]);
        ary[1]=ary[j--];
        down(1);
    }
    return 0;
}

KMP模板

#include<iostream>
using namespace std;
const int N = 1e5+10;
const int M = 1e6+10;

char p[N],s[M];
int ne[N];

int main()
{
    int n,m;
    cin>>n>>p+1>>m>>s+1;
    for(int i=2,j=0;i<=n;i++)
    {
        while(j && p[j+1] != p[i]) j=ne[j];
        if(p[j+1] == p[i]) j++;
        ne[i]=j;
    }
    for(int i=1,j=0;i<=m;i++)
    {
        while(j && p[j+1] != s[i]) j=ne[j];
        if(p[j+1] == s[i]) j++;
        if(j==n)
        {
            printf("%d ",i-j);
             j=ne[j];
        }
    }
    return 0;
}

Trie树

#include <iostream>

using namespace std;

const int N = 100010;

int ary[N][28];
int cnt[N];
char str[N];
int idx;//idx表示唯一标号

void insert()
{
    int m=0;
    scanf("%s",str);
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        if(!ary[m][u]) ary[m][u]=++idx;
        m=ary[m][u];
    }
    cnt[m]++;
}

int query()
{
    int m=0;
    scanf("%s",str);
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        if(!ary[m][u]) return 0;
        m=ary[m][u];
    }
    return cnt[m];
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        char a;
        cin>>a;
        switch(a)
        {
            case 'I':insert();break;
            case 'Q':printf("%d\n",query());break;
        }
    }
    return 0;
}

并查集

#include <iostream>
using namespace std;

const int N = 100010;

int ary[N];
char op[2];
int l,r;

int find(int x)
{
    if(ary[x]!=x) ary[x]=find(ary[x]);
    return ary[x];
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) ary[i]=i;
    while(m--)
    {
        scanf("%s%d%d",&op,&l,&r);
        if(op[0]=='M')
        {
            ary[find(r)] = find(l);
        }
        else
        {
            if(find(l)!=find(r)) cout<<"No"<<endl;
            else cout<<"Yes"<<endl;
        }
    }
    
    return 0;
}