模板

基础算法

快速排序

//快速排序是一个递归的过程
//将数组分为两个部分，始终让后半部分的数全部大于左半部分的数，
//那么当不断缩小后，就完成了排序
void quick_sort(int l, int r, int a[])
{
    if(l >= r) return;
    int x = a[(l+r)/2];
    int i = l - 1;
    int j = r + 1;
    while(i < j)
    {
        //找到前半段中大于中间值的（即不属于左半部分的）
        do i ++; while(a[i] < x)
        //找到后半段中小于中间值的（即不属于右半部分的）
        do j --; while(a[j] > x)

        if(i < j) swap(a[i], a[j]);
    }
    quick_sort(l, j, a);
    quick_sort(j + 1, r, a);
}

归并排序

思路与快排相反，先保证小范围内是有序的，然后将两个有序的合在一起

void merge_sort(int a[], int l, int r)
{
    if(l >= r) return;
    int mid = (l + r) >> 1;
    merge_sort(a, l, mid);
    merge_sort(a, mid + 1, r);

    int k = 1, i = l, j = mid + 1;
    //将两个分别有序的数组合并成一个有序的数组
    while(i <= mid && j <= r)
    {
        if(a[i] <= a[j]) temp[k ++] = a[i ++];
        else temp[k ++] = a[j ++];
    }
    while(i <= mid) temp[k ++] = a[i ++];
    while(j <= r) temp[k ++] = a[j ++];

    //然后放回到原始数组中
    for(int i = l, j = 1; i <= r; i ++, j ++) a[i] = temp[j];
}

二分

左0右1

左

while(l < r)
{
    int mid = (l + r) >> 1;
    if(check(mid)) r = mid;
    else l = mid + 1;
}

右

while(l < r)
{
    int mid = (l + r + 1) >> 1;
    if(check(mid)) l = mid;
    else r = mid - 1;
}

离散化

//存的是坐标点
point.push_back(index)
p.push_back({index, value})
//排序，去重
sort(point.bgein(), point.end())
point.erase(unique(point.begin(), point.end()), point.end())

//在开一个组数，表示离散化后

for(auto t : p)
{
    //获得离散化后的坐标
    int index = lower_bound(point.begin(), point.end(), t.first) - point.begin();
    //存入值
    a[index] += t.second;
}

数据结构

并查集

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

//合并
p[find(a)] = find(b)


//维护祖宗节点的个数
int size[N];
//合并集合
size[find(b)] += size[find(a)];
p[find(a)] = find(b);


//维护到祖宗节点的距离
int d[N];

int find(int x)
{
    if(p[x] != x)
    {
        int u = find(p[x]);
        d[x] += d[p[x]];
        p[x] = u;
    }
    return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
    p[i] = i;
    d[i] = 0;
}

// 合并a和b所在的两个集合：
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

图论

邻接表

int h[N], e[N], ne[N], idx;
void add(int a, int b, int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++;
}

拓扑排序

bool topsort()
{
    int hh = 0, tt = -1;

    //先把入度为0的放入队列
    for(int i = 1; i <= n; i ++)
    {
        if(d[i] == 0) q[++ tt] = i;
    }

    while(hh <= tt)
    {
        int t = q[hh ++];

        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(d[j] == 1)
            {
                q[++ tt] = j;
            }
            d[j] --;
        }
    }

    return tt == n-1;
}

Dijkstra

朴素做法

int g[N][N];
int dist[N];
int st[N];

int dijsktra()
{
    //起点
    dist[1] = 0;

    for(int i = 1; i <= n; i ++)
    {
        //找到目前的最小值
        int t = -1;
        for(int j = 1; j <= n; j ++)
        {
            if(!st[j] && (dist[j] < dist[t] || t == -1))
            { 
                t = j;
            }
        }

        //通过当前的最小值进行更新
        for(int j = 1; j <= n; j ++)
        {
            dist[j] = (dist[j], dist[t] + g[t][j]);
        }
        st[j] = 1;
    }

    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];

    return 
}

int main()
{
    memset(g, 0x3f, sizeof g);
    memset(dist, 0x3f, sizeof dist);
}

优化（优先队列）

typedef pair<int, int> P;
priority_queue<P, vector<P>, greater<P>> q;

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    q.push({0, 1});

    while(q.size())
    {
        auto t = q.top();
        q.pop();
        int node = t.second;
        int dis = t.first;
        if(vis[node]) continue;
        vis[node] = 1;
        for(int i = h[node]; ~i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dis + w[i])
            {
                dist[j] = dis + w[i];
                q.push({dist[j], j});
            }
        }
    }

    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

Bellman-Ford

求限定条数下的最短路，可能出现负权，可能出现负权回路

struct EGDE
{
    int a, b, w;
} edge[N];


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

    //走的步数限制
    for(int i = 1; i <= k; i ++)
    {
        //备份，不备份的话不能保证一次大循环只走一步
        //如果出现串联更新，就说明走了多步
        memcpy(backup, dist, sizeof dist);
        for(int j = 1; j <= m; j ++)
        {
            auto t = edge[j];
            dist[t.b] = min(dist[t.b], backup[t.a] + t.w);
        }
    }
}


if(dist[n] > 0x3f3f3f3f/2)

spfa

维护一个队列，从队列中的点计算他能得到的最短

int spfa()
{
    memset(dist, 0x3f, sizeof dist);

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

    while(q.size())
    {
        auto t = q.front();
        q.pop();
        st[t] = false;

        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i]
                if(!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        } 
    }

    return dist[n];
}

floyd

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

prim

找到到集合的最短距离

int prim()
{
    memset(dist, 0x3f, sizeof dist);
    int ans = 0;

    for(int i = 0; i < n; i ++)
    {
        int t = -1;
        for(int j = 1; j <= n; j ++)
        {
            if(!st[j] && (dist[j] < dist[t] || t == -1))
            {
                t = j;
            }
        }

        //当前的最短也无限长，说明没有最小生成树
        if(i && dist[t] == 0x3f3f3f3f) return 0x3f3f3f3f;
        if(i) ans += dist[t];
        st[t] = true;

        for(int j = 1; j <= n; j ++)
        {
            dist[j] = min(dist[j], dist[i] + g[i][j]);
        }
    }

    return ans;
}

Kruskal

每次取最短的边

void kruskal()
{
    sort(edge + 1, edge + m + 1, cmp);

    //每次取短边，如果不在树里的话，加入树里
    for(int i = 1; i <= m; i ++)
    {
        int pa = find(edge[i].a);
        int pb = find(edge[i].b);

        if(pa != pb)
        {
            ans += dege[i].w;
            p[pa] = pb;
            cnt ++;
        }
    }
}

if(cnt < n - 1) 

染色法二分图

二分图：两个点集，一个点集中的点不相连，只能与另外一个点集中的点相连
判定是不是二分图

//染色
bool dfs(int index, int c)
{
    color[index] = c;

    for(int i = h[index]; i != -1; i = ne[i])
    {
        int j = e[i];
        //如果没被染色
        if(!color[j])
        {
            //相反的颜色
            if(!dfs(j, 3-c)) return false;
        }
        else if(color[j] && color[j] != 3-c) return false; //相同的颜色
    }

    return true;
}

for(int i = 1; i <= n; i ++)
{
    //没被染色
    if(!color[i])
    {
        if(!dfs(i, 1))
        {
            st = false;
            break;
        }
    }
}

匈牙利算法

二分图最大匹配

bool find(int x)
{
    for(int i = h[x]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!st[j])
        {
            st[j] = true;

            //如果j没和别的点连，或者和别的点连的那个点能找到别的相连点
            if(match[j] == 0 || find(match[j]))
            {
                match[j] = x;   
                return true;
            }
        }
    }

    return false;
}

int ans = 0;
for(int i = 1; i <= n1; i ++)
{
    memset(st, false, sizeof st);
    if(find(i)) ans ++;
}

数学公式

质数

线性筛

for(int i = 2; i <= n; i ++)
{
    if(!st[i]) primes[cnt ++] = i;
    for(int j = 0; prime[j] <= n/i; j ++)
    {
        st[prime[j] * i] = 1;
        if(i % primes[j] == 0) break;
    }
}

试除法分解质因数

void divide(int x)
{
    for(int i = 2; i <= n/i; i ++)
    {
        int cnt = 0;
        while(x % i == 0)
        {
            x /= i;
            cnt ++;
        }
        cout<<i<<" "<<cnt<<endl;
    }

    if(x) cout<<x<<" 1"<<endl;
}

试除法求约数

辗转相除法

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

欧拉函数

按照定义求：

int phi(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);

    return res;
}

快速幂

求

$$a_i^{b_i}\mathrm{~mod~}p_i$$

//思路：把b进行二进制划分，那么快速幂就相当于a的不同次方相乘
ll quick(ll a, ll b, ll p)
{
    ll res = 1;
    while(b)
    {
        if(b & 1) res = (res * a)%p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

求组合数（递推）

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

求逆元

fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++ )
{
    fact[i] = (LL)fact[i - 1] * i % mod;
    infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}