快排

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

归并排序

void merge_sort(int p[], int l, int r) {
    if (l >= r) return;

    int mid = l + r >> 1;

    merge_sort(p, l, mid), merge_sort(p, mid + 1, r);

    int k = 1, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (p[i] <= p[j]) tmp[k++] = p[i++];
        else tmp[k++] = p[j++];
    }
    while (i <= mid) tmp[k++] = p[i++];
    while (j <= r) tmp[k++] = p[j++];
    for (int i = l, j = 1; i <= r; i++, j++) p[i] = tmp[j];
}

二分

    int l = 0, r = n - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (a[mid] >= k) r = mid;//找到大于等于k的第一个数
        else l = mid + 1;
    }
    if (a[l] != k)
        printf("-1 -1\n");
    else
    {
        printf("%d ", l);
        int l1 = 0, r1 = n - 1;
        while (l1 < r1)
        {
            int mid = l1 + r1  + 1 >> 1;
            if (a[mid] <= k) l1 = mid;//找到小于等于k的最后一个数
            else r1 = mid - 1;
        }
        printf("%d\n", l1);
    }

前缀和

    for(int i = 1 ; i <= n ; i ++ ) s[i] = s[i - 1] + a[i];
    while(m -- ){
        int l , r ;
        scanf("%d%d",&l,&r);
        printf("%d\n",s[r] - s[l - 1]);
    }

差分

void insert(int l , int r , int c)
{
    b[l] += c;
    b[r + 1] -= c;
}//插入操作
int main()
{
    int n , m ; 
    scanf("%d%d",&n,&m);
    for(int i = 1 ; i <= n ; i ++ ) scanf("%d",&a[i]);
    for(int i = 1 ; i <= n ; i ++ ) insert(i , i , a[i]);//构建差分数组

    while(m -- ){
        int l , r , c;
        scanf("%d%d%d",&l ,&r,&c);
        insert(l , r , c);
    }
    for(int i = 1 ; i <= n ; i ++ ) b[i] += b[i - 1];
    for(int i = 1 ; i <= n ; i ++ ) printf("%d ",b[i]);
    return 0;
}

位运算

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

KMP

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

并查集

int find(int x)//返回x的祖宗节点 && 路径压缩
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

朴素Dijkstra

int dijkstra() {
    memset(dist, 0x3f, sizeof dist);//初始化每个点到起点的距离
    dist[1] = 0;
    for (int i = 1; i <= n; i++) {
        int t = -1;//记录父节点
        //找出与当前节点相连中路径最短的节点
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if ( t == n && dist[n] != 0x3f3f3f3f ) break;//如果走到了n，那就结束了

        st[t] = true;//标记为true

        //记录该顶点到起点最短的距离
        for (int j = 1; j <= n; j++) {
            dist[j] = min(dist[j], dist[t] + g[t][j]);//更新到临边的最小距离
        }
    }
    if (dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

Dijkstra堆优化

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII> > heap;
    heap.push({ 0, 1 });
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({ dist[j], j });
            }
        }
    }
}

spfa求最短路

void spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size())
    {
        int t = q.front();
        q.pop();
        //t已经出队，把t标为false
        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            //如果j点变小，且j点不在队列中，就把j点加入队列中
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;//j入队
                }
            }
        }
    }
}

Floyd

void floyd()
{
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

Prim

int  prim()
{
    memset(dist, 0x3f, sizeof dist);
    int res = 0;
    for(int i = 0; i < n; i++)
    {
        int t = -1;
        for(int j = 1; j <= n; j++)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;//找到集合外离集合距离最短的点

        if(i && dist[t] == INF) return INF;
        //如果不是第一个点并且t点离集合的距离是正无穷，说明不连通
        if(i) res += dist[t];
        //如果不是第一个点，那res就加上t到集合的距离
        for(int j = 1; j <= n; j++)
            dist[j] = min(dist[j], g[t][j]);
        st[t] = true;
    }
    return res;
}

Kruskal

    sort(edges + 1, edges + m + 1);//把每条边按边权由小到大排序
    for (int i = 1; i <= n; i++) p[i] = i;//初始化并查集数组

    int res = 0, cnt = 0;//res是边权的和，cnt是加入的边数
    for (int i = 1; i <= m; i++)
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);//找到a和b的根节点
        //如果a和b不在一个集合中，就加上这条边，并且把a和b放在一个集合中去
        if (a != b)
        {
            res += w;
            p[a] = b;
            cnt++;
        }
    }
    if (cnt < n - 1) puts("impossible");//如果最后边数小于n-1，说明不连通
    else printf("%d\n", res);

快速幂

//a^k % p
int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        k >>= 1;
        a = (LL)a * a % p;
    }
    return res;
}

01背包

二维

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1010;

int f[N][N];
int n, m;
int v[N], w[N];

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

    for(int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    cout << f[n][m] << endl;
    return 0;
}

一维

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1010;

int f[N];
int n, m;
int v[N], w[N];

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

    for(int i = 1; i <= n; i++)
        for (int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;
    return 0;
}

完全背包

二维

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1010;

int n, m;
int f[N][N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int v, w;
        scanf("%d%d", &v, &w);
        for (int j = 1; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            if(j >= v)
                f[i][j] = max(f[i - 1][j], f[i][j - v] + w);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

一维

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1010;

int n, m;
int f[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int v, w;
        cin >> v >> w;
        for (int j = v; j <= m; j++)
            f[j] = max(f[j], f[j - v] + w);
    }
    cout << f[m] << endl;
    return 0;
}

区间选点

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 100010;

int n;

struct Range{
    int l, r;
    bool operator< (const Range &W)const
    {
        return r < W.r;
    }
}range[N];
//按右端点排序
//从前往后枚举每个区间
//    如果当前区间中已经包含点，则直接pass
//    否则，选择当前区间的右端点 
int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        int l, r;
        scanf("%d%d",&l, &r);
        range[i] = {l, r};
    }
    sort(range, range + n);

    int res = 0, ed = -2e9;
    for(int i = 0; i < n; i ++)
    {
        if(range[i].l > ed)
        {
            res ++;
            ed = range[i].r;
        }
    }
    cout << res << endl;
    return 0;
}