简单模板

并查集

int ht[N];
int fa[N];
int n;  // point numers
void init_set() {
    for (int i = 1; i <= n; ++i) fa[i] = i, ht[i] = 0;
}
int Find(int x) {
    if (x != fa[x]) fa[x] = Find(fa[x]);  //路径压缩
    return fa[x];
}
int find_set_circle(int x) {
    int r = x;
    while (fa[r] != r) r = fa[r];  //找到根节点
    for (int i = x, j; i != r; i = j)
        j = fa[i], fa[i] = r;  //把路径上的元素的集改为根节点
    return r;
}
void union_set(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (ht[x] == ht[y])
        ht[x] = ht[x] + 1, fa[y] = x;
    else if (ht[x] < ht[y])
        fa[x] = y;
    else
        fa[y] = x;
}

管理节点数量，无按秩归并

//hdu1856

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 10000005;
int sum[maxn];      //集合总数
int ufs[maxn];      //父节点
void Init(int n) {  //初始化
    for (int i = 1; i <= n; i++) {
        ufs[i] = i;
        sum[i] = 1;
    }
}
int Find(int a) {       //获得a的根节点。路径压缩
    if (ufs[a] != a) {  //没找到根节点
        int tmp = ufs[a];
        ufs[a] = Find(ufs[a]);
    }
    return ufs[a];
}
void Merge(int a, int b) {  //合并a和b的集合
    int x = Find(a);
    int y = Find(b);
    if (x != y) {
        ufs[x] = y;
        sum[y] += sum[x];
    }
}
int main() {
    int t, a, b;
    while (~scanf("%d", &t)) {
        Init(maxn);
        while (t--) {
            scanf("%d%d", &a, &b);
            Merge(a, b);
        }
        int ans = -1;
        for (int i = 1; i <= maxn; ++i) ans = max(ans, sum[i]);
        printf("%d\n",ans);
    }
    return 0;
}

食物链（关系并查集）

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 50010;
struct node {
    int pre;       //父节点
    int relation;  //与父节点之间的关系
} p[N];
/*
在这里，向量指的是“偏移量”，表示的是子节点与父节点之间的关系。
0表示与父节点属于同一种族；
1表示被父节点吃；
2表示吃父节点。
*/
int find(int x) {  //查找根结点
    int temp;
    if (x == p[x].pre) return x;
    temp = p[x].pre;  //路径压缩
    p[x].pre = find(temp);
    p[x].relation = (p[x].relation + p[temp].relation) % 3;  //关系域更新
    return p[x].pre;  //根结点
}
int main() {
    int n, k;
    int sum = 0;  //假话数量
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) {  //初始化
        p[i].pre = i;
        p[i].relation = 0;
    }
    int ope, a, b;
    for (int i = 1; i <= k; ++i) {
        scanf("%d%d%d", &ope, &a, &b);
        if (a > n || b > n || ope == 2 && a == b) sum++;
        else {
            int root1 = find(a);
            int root2 = find(b);
            if (root1 != root2) {  // 合并
                p[root2].pre = root1;
                // 此时 rootx->rooty = rootx->x + x->y + y->rooty
                p[root2].relation = (3 + p[a].relation + (ope - 1) - p[b].relation) % 3;
            } else {
                //验证x->y之间的偏移量是否与题中给出的d-1一致
                if (ope == 1 && p[a].relation != p[b].relation) sum++;
                else if (ope == 2 && (3 - p[a].relation + p[b].relation) % 3 != ope - 1)
                    sum++;
            }
        }
    }
    printf("%d\n", sum);
    return 0;
}

KMP

//模板
void GetNextval(string p, int next[]) {
    int pLen = p.length()-1;
    next[0] = -1;
    for (int i = 0, j = -1; i < pLen;) {
        if (j == -1 || p[i] == p[j]) {
            if (p[++i] != p[++j]) next[i] = j;
            else next[i] = next[j];
        } else j = next[j];
    }
}

区间DP

题意

n个点在数轴上排列，从其中一个点出发。每个点都有要求的最晚到达时间，问能否全部准时到达，如果能，给出完成时间。

分析

题目给出的n个景点是按照位置信息升序排列的。

把起始点，即t为0的点设为k，所有的点分成了两部分：k点左边的点和k点右边的点。

我们用一个数组dp[i][j][f]表示完成左边i个点右边j个点的最少所需时间，f==0时表示在左边结束，f==1时表示在右边结束。

简单模板

并查集

KMP

区间DP

杜教筛

全站热榜

创作者周榜