快速排序

void quick_sort(int l, int r){
    if(l >= r)
        return;
    int x = a[(l + r) / 2];
    int i=l-1, j=r+1;
    while (i < j) {
        while(a[++i] < x);
        while(a[--j] > x);
        if (i < j) swap(a[i], a[j]);
    }
    quick_sort(l, j);
    quick_sort(j+1, r);
}
void quick_sort(int l, int r){
    if(l >= r)
        return;
    int i=l, j=r;
    int a0 = a[l];
    while (i < j) {
        while(i<j and a[j]>=a0)
            j--;
        a[i] = a[j];
        while(i<j and a[i]<=a0)
            i++;
        a[j] = a[i];
    }
    a[i] = a0;
    quick_sort(l, j);
    quick_sort(j+1, r);
}

归并排序

void merge_sort(int l, int r){
    if(l >= r)
        return;
    int m = (l + r) / 2;
    merge_sort(l, m), merge_sort(m+1, r);
    int i=l, j=m+1, idx=l;
    while(i<=m && j<=r){
        if(a[i] <= a[j])
            t[idx++] = a[i++];
        else
            t[idx++] = a[j++];
    }
    while(i <= m)
        t[idx++] = a[i++];
    while(j <= r)
        t[idx++] = a[j++];
    for(int i=l; i<=r; i++)
        a[i] = t[i];
}

数的二分

int lower_bound(int l, int r, int x){
    while(l < r){
        int m = (l + r) / 2;
        if(x <= a[m])
            r = m;
        else
            l = m + 1;
    }
    return l;
}
int upper_bound(int l, int r, int x){
    while(l < r){
        int m = (l + r + 1) / 2;
        if(x >= a[m])
            l = m;
        else
            r = m-1;
    }
    return r;
}

高精度加法

vector<int> add(vector<int> x, vector<int> y){      
    if(x.size() < y.size())
        return add(y, x);
    vector<int> ans;
    int getin = 0;
    for(int i=0; i<x.size(); i++){
        int u = x[i] + getin;
        if(i < y.size())
            u += y[i];
        getin = u / 10;
        ans.push_back(u%10);
    }
    if(getin)
        ans.push_back(getin);
    return ans;
}

高精度减法

vector<int> sub(vector<int> a, vector<int> b){
    if(a < b){
        return sub(b, a);
    }
    vector<int> ans;
    int owe = 0;
    for(int i=0; i<a.size(); i++){
        int u = a[i] - owe;
        if(i < b.size())
            u -= b[i];
        if(u < 0)
            owe = 1;
        else
            owe = 0;
        ans.push_back((u+10)%10);
    }
    while(ans.size()>1 && ans.back()==0)
        ans.pop_back();
    return ans;
}

高精度乘法

vector<int> mult(vector<int> a, int b){
    vector<int> ans;
    int getin = 0;
    for(int i=0; i<a.size(); i++){
        int u = a[i] * b + getin;
        getin = u / 10;
        ans.push_back(u % 10);
    }
    while(getin){
        ans.push_back(getin % 10);
        getin /= 10;
    }
    while(ans.size()>1 && ans.back()==0)
        ans.pop_back();
    return ans;
}

高精度除法

pair<vector<int>, int> divition(vector<int> a, int b){
    pair<vector<int>, int> ans;
    int s = 0;
    for(int i=0; i<a.size(); i++){
        s = s * 10 + a[i];
        int u = s / b;
        s = s % b;
        ans.first.push_back(u);
    }
    ans.second = s;
    while(ans.first.size()>1 && ans.first.front()==0)
        ans.first.assign(ans.first.begin()+1, ans.first.end());
    return ans;
}

一维前缀和

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

二维前缀和

for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
        scanf("%d", &x);
        S[i][j] = S[i][j-1] + S[i-1][j] - S[i-1][j-1] + x;
    }
}
printf("%ld\n", S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1]);

一维差分

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

二维差分

for(int i=1; i<=n; i++)
    for(int j=1; j<=m; j++){
        scanf("%d", &s[i][j]);
        a[i][j] = s[i][j]-s[i-1][j]-s[i][j-1]+s[i-1][j-1];
    }
while(q--){
    scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
    a[x1][y1] += c;
    a[x1][y2+1] -= c;
    a[x2+1][y1] -= c;
    a[x2+1][y2+1] += c;
}

二进制中1的个数

int fun(int x){
    int ans = 0;
    while(x){
        int u = x&(-x);
        if(u)
            ans++;
        x -= u;
    }
    return ans;
}

离散化

void work(int a[]){
    for(int i=0; i<n; i++)
        p[i] = i;
    sort(p, p+n, [&](int x, int y){
        return a[x] < a[y];
    });
    for(int i=0; i<n; i++)
        a[p[i]] = i;
}
sort(all.begin(), all.end());
all.erase(unique(all.begin(), all.end()), all.end());   //排序去重

区间合并

sort(p, p+n);
int st = p[0].first, ed = p[0].second;
vector<PII> ans;
for(int i=0; i<n; i++){
    if(p[i].first <= ed)
        ed = max(ed, p[i].second);
    else{
        ans.push_back({st, ed});
        st = p[i].first, ed = p[i].second;
    }
}
ans.push_back({st, ed});
cout << ans.size() << endl;

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){
        cout << i-n << ' ';
        j = ne[j];
    }
}

Trie字典树

int t[N][26], cnt[N], idx=1;
void insert(char s[]){
    int p=0;
    for(int i=0; s[i]; i++){
        int u = s[i] - 'a';
        if(t[p][u])         
            p = t[p][u];
        else{
            t[p][u] = idx++;
            p = t[p][u];
        }
    }
    cnt[p]++;
}
int query(char s[]){
    int p = 0;
    for(int i=0; s[i]; i++){
        int u = s[i] - 'a';
        if(t[p][u])
            p = t[p][u];
        else
            return 0;
    }
    return cnt[p];
}

并查集

int find(int x){
    if(x != f[x])
        f[x] = find(f[x]);
    return f[x];
}
a = find(a), b = find(b);
if(a != b){
    cnt[b] += cnt[a];
    f[a] = b;
}

模拟堆

void down(int u){
    int t = u;
    if(u*2<=n && a[u*2]<a[u])
        t = u*2;
    if(u*2+1<=n && a[u*2+1]<a[t])
        t = u*2+1;
    if(t != u){
        swap(a[t], a[u]);
        down(t);
    }
}
void up(int u){
    if(u/2 && a[u/2]>a[u]){
        swap(a[u], a[u/2]);
        up(u/2);
    }
}

字符串hash

const int N = 1e5+9, P = 131;
ULL p[N], s[N];
ULL get(int l, int r){
    return s[r] - s[l-1]*p[r-l+1];    
}
p[0] = 1;
for(int i=1; i<=n; i++){
    p[i] = p[i-1] * P;
    s[i] = s[i-1]*P + str[i];
}

树的重量

int dfs(int u){
    st[u] = 1;
    int total = 1;
    for(int i=h[u]; i!=-1; i=ne[i]){
        int j = e[i];
        if(st[j] == 0){
            int s = dfs(j);
            total += s;
        }
    }
    return total;
}

BFS走迷宫

void bfs(){
    int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
    queue<pair<int, int>> q;
    q.push({0, 0});
    st[0][0] = 1;
    while(q.size()){
        auto t = q.front();
        q.pop();
        for(int i=0; i<4; i++){
            int x = t.first + dx[i];
            int y = t.second + dy[i];
            if(x>=0 && x<n && y>=0 && y<m && st[x][y] == 0 && a[x][y]==0){
                st[x][y] = 1;
                q.push({x, y});
                d[x][y] = d[t.first][t.second] + 1;
            }
        }
    }
}

有向图topo排序

int d[N], res[N], ans;
bool topo(){
    queue<int> Q;
    for(int i=1; i<=n; i++)
        if(d[i] == 0){
            Q.push(i);
            res[ans++] = i;
        }
    while(!Q.empty()){
        int k = Q.front();
        Q.pop();
        for(int i=h[k]; i!=-1; i=ne[i]){
            int j = e[i];
            if(d[j]){
                if(--d[j] == 0){
                    Q.push(j);
                    res[ans++] = j;
                }
            }
        }
    }
    for(int i=1; i<=n; i++)
        if(d[i])
            return false;
    return true;
}

朴素Dijkstra

void dijkstra(int n, int m){
    st[1] = 1;
    for(int k=1; k<n; k++){
        int ip = 1, minn = 1e9;
        for(int i=1; i<=n; i++){
            if(st[i] == 0 and d[1][i] < minn)
                minn = d[1][i], ip = i;
        }
        st[ip] = 1;
        for(int i=1; i<=n; i++){
            if(st[i] == 0 and d[1][i] > d[1][ip] + d[ip][i])
                d[1][i] = d[1][ip] + d[ip][i];
        }
    }
    if(d[1][n] > 0x3f3f3f3f / 2)
        cout << -1 << endl;
    else    
        cout << d[1][n] << endl;
}

堆优化Dijkstra

void dijkstra(int n, int m){
    d[1] = 0;
    q.push({d[1], 1});
    while(q.size()){
        int u = q.top().second;
        q.pop();
        if(st[u] == 1)
            continue;
        st[u] = 1;
        for(int i=h[u]; i!=-1; i=ne[i]){
            int j = e[i];
            if(st[j] == 0 and d[j] > d[u] + w[i]){
                d[j] = d[u] + w[i];
                q.push({d[j], j});
            }
        }
    }
    if(d[n] > 0x3f3f3f3f / 2)
        cout << -1 << endl;
    else    
        cout << d[n] << endl;
}

bellman_ford算法

int d[N], backup[N];
void bellman_ford(int n, int m, int k){
    d[1] = 0;
    for(int t=1; t<=k; t++){
        memcpy(backup, d, sizeof d);
        for(int i=0; i<=m; i++){
            int a=e[i].a, b=e[i].b, w=e[i].w;
            d[b] = min(d[b], backup[a] + w);
        }
    }
    if(d[n] > 0x7f7f7f7f / 2)
        cout << "impossible" << endl;
    else
        cout << d[n] << endl;
}

spfa最短路

void spfa(int n, int m){
    d[1] = 0;
    st[1] = 1;
    q.push(1);
    while(q.size()){
        int u = q.front();
        q.pop();
        st[u] = 0;
        for(int i=h[u]; ~i; i=ne[i]){
            int j =e[i];
            if(d[j] > d[u] + w[i]){
                d[j] = d[u] + w[i];
                if(st[j] == 0){
                    st[j] = 1;
                    q.push(j);
                }
            }
        }
    }
    if(d[n] > 0x3f3f3f3f / 2)
        cout << "impossible" << endl;
    else
        cout << d[n] << endl;
}

spfa判断负环

int spfa(int n, int m){
    for(int i=1; i<=n; i++){
        st[i] = 1;
        q.push(i);
    }
    while(q.size()){
        int u = q.front();
        q.pop();
        st[u] = 0;
        for(int i=h[u]; ~i; i=ne[i]){
            int j =e[i];
            if(d[j] > d[u] + w[i]){
                d[j] = d[u] + w[i];
                cnt[j] = cnt[u] + 1;
                if(cnt[j] >= n)
                    return true;
                if(st[j] == 0){
                    st[j] = 1;
                    q.push(j);
                }
            }
        }
    }
    return false;
}

floyd最短路

void floyd(){
    for(int i=1; i<=n; i++)
        d[i][i] = 0;
    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]);
}

Kruskal最小生成树

void kruskal(){
    sort(edge, edge+m);
    for(int i=1; i<=n; i++)
        f[i] = i;
    int cnt=1, ans=0;
    for(int i=0; i<m; i++){
        int a = edge[i].a, b = edge[i].b, c = edge[i].c;
        a = find(a), b = find(b);
        if(a != b){
            cnt++, ans+=c;
            f[a] = b;
        }
    }
    if(cnt == n)
        printf("%d", ans);
    else
        printf("impossible");
}

染色法判断二分图

void dfs(int u){
    st[u] = 1;
    for(int i=h[u]; ~i; i=ne[i]){
        int j = e[i];
        if(st[j] == 0){
            c[j] = !c[u];
            dfs(j);
        }
        else if(c[j] == c[u])
            flag = 1;
    }
}
int check(){
    for(int i=1; i<=n; i++){
        if(st[i] == 0)
            dfs(i);
        if(flag == 1)
            return false;
    }
    return true;
}

最大二分图匹配

int st[N], arc[N];
int check(int u){
    for(int i=h[u]; ~i; i=ne[i]){
        int j = e[i];
        if(st[j] == 0){
            st[j] = 1;
            if(arc[j] == 0 or check(arc[j])){
                arc[j] = u;
                return true;
            }
        }
    }
    return false;
}

试除法判断素数

bool is_prime(int x){
    if(x < 2)
        return false;
    for(int i=2; i<=x/i; i++)
        if(x %i == 0)
            return false;
    return true;
}

分解质因数

void fun(int x){
    for(int i=2; i<=x/i; i++){
        if(x % i == 0){
            int num=0;
            while(x % i == 0){
                num++;
                x /= i;
            }
            cout << i << ' ' << num << endl;
        }
    }
    if(x > 1){
        cout << x << ' ' << 1 << endl;
    }
}

线性筛质数

int p[N], st[N], cnt;
void getprime(int n){
    for(int i=2; i<=n; i++){
        if(st[i] == 0)
            p[cnt++] = i;
        for(int j=0; p[j]<=n/i; j++){
            st[ p[j] * i] = 1;
            if(i % p[j] == 0)
                break;
        }
    }    
}

试除法求约束

vector<int> fun(int x){
    vector<int> ans;
    for(int i=1; i<=x/i; i++){
        if(x % i ==0){
            ans.push_back(i);
            if(i != x/i)
                ans.push_back(x/i);
        }
    }
    sort(ans.begin(), ans.end());
    return ans;
}

最大公约数

int gcd(int a, int b){
    if(b)
        return gcd(b, a % b);
    else
        return a;
}

欧拉函数

int ol(int x){
    vector<int> p;
    for(int i=2; i<=x/i; i++){
        if(x % i == 0){
            p.push_back(i);
            while(x % i == 0){
                x /= i;
            }
        }
    }
    if(x > 1)
        p.push_back(x);
    int ans = x;
    for(auto i : p){
        ans = (long long)ans * (i - 1) / i;
    }
    return ans;
}

快速幂

int qmi(int a, int b, int p){
    int ans = 1;
    while(b){
       if(b & 1)
            ans = (long long)ans * a % p;
        b = b >> 1;
        a = (long long)a * a % p;
    }
    return ans;
}

快速幂求逆元

//p为质数，且a与p互质
if(a % p == 0)
    cout << "impossible" << endl;
else
    cout << qmi(a, p-2, p) << endl;

扩展欧几里得

PII exgcd(int a, int b){
    PII ans;
    if(b == 0){
        ans = {1, 0};
        return ans;
    }
    else{
        PII t =  exgcd(b, a % b);
        ans = {t.second, t.first - a / b * t.second};
        return ans;
    }
}

组合数1

void init(){
    for(int i=0; i<N; i++){
        for(int j=0; j<=i; j++){
            if(j == 0)
                c[i][j] = 1;
            else
                c[i][j] = (c[i-1][j-1] + c[i-1][j]) % mod;
        }
    }
}

组合数2

int fact[N], infact[N];
void init(){
    fact[0] = infact[0] = 1;
    for(int i=1; i<N; i++){
        fact[i] = (LL)fact[i-1] * i % mod;
        infact[i] = qmi(fact[i], mod-2, mod);
    }
}
cin >> a >> b;
cout << (LL)fact[a] * (LL)infact[a-b] % mod * (LL)infact[b] % mod << endl;

组合数3(lucas定理)

LL c(int a, int b, int p){
    if(a < b)
        return 0;
    fact[0] = infact[0] = 1;
    for(int i=1; i<=a; i++){
        fact[i] = fact[i-1] * i % p;
    }
    infact[b] = qmi(fact[b], p-2, p);
    infact[a-b] = qmi(fact[a-b], p-2, p);
    return fact[a] * infact[b] % p * infact[a-b] % p;
}
LL lucas(LL a, LL b, LL p){
    if(a < p && b < p)
        return c(a, b, p);
    else
        return c(a%p, b%p, p) * lucas(a/p, b/p, p) % p;
}

01背包

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

完全背包

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

多重背包

for(int i=1; i<=n; i++)
    for(int j=m; j>=0; j--)
        for(int k=0; k<=s[i] && k*v[i]<=j; k++)
            dp[j] = max(dp[j], dp[j-k*v[i]]+k*w[i]);