10.14 晚总结

· · 个人记录

P1525 [NOIP 2010 提高组] 关押罪犯

怨气大的肯定是要优先分开的，所以将关系从大到小排序。

将两个监狱分成两个集合，自己的集合为 x，创建一个虚拟点 x + n 代表对面的集合。

对于一组 (x,y,w)，若 \operatorname{find}(x) = \operatorname{find}(y)，则 w 就是答案。否则，\operatorname{unionn}(x,y + n), \operatorname{unionn}(x + n, y)。

#include <bits/stdc++.h>

using namespace std;

int n, m, sum, fa[200005];

struct Node {
    int u, v, w;
} a[100005];

int find(int x) {
    return (fa[x] == x ? x : fa[x] = find(fa[x]));
}

void unionn(int x, int y) {
    x = find(x), y = find(y);
    if (x != y) {
        fa[x] = y;
    }
    return ;
}

bool cmp(Node a, Node b) {
    return a.w > b.w;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i ++) {
        cin >> a[i].u >> a[i].v >> a[i].w;
    }
    for (int i = 1; i <= n + n; i ++)
        fa[i] = i;
    sort (a + 1, a + 1 + m, cmp);
    for (int i = 1; i <= m; i ++) {
        if (find(a[i].u) == find(a[i].v)) {
            cout << a[i].w;
            return 0;
        } else {
            unionn (a[i].u, a[i].v + n);
            unionn (a[i].u + n, a[i].v);
        }
    }
    cout << 0;
    return 0;
}

U125683 [ybt1347]格子游戏

感言：额，很粗心，我服了，输出把 i 写成了 m 调半天没调出来最后输出了个 draw。

用并查集判环。

我们要把二维坐标转为一串数字，(x - 1) * n + y。

令当前坐标为 id1，移动后为 id2。

当 \operatorname{find}(id1) = \operatorname{find}(id2) 时，则说明围了一个环，输出 i。

当 m 次操作结束后没有围成一个环，则输出 draw。

#include <bits/stdc++.h>

using namespace std;

int n, m, fa[200005];

int find(int x) {
    return (fa[x] == x ? fa[x] : fa[x] = find(fa[x]));
}

void unionn(int u, int v) {
    u = find(u), v = find(v);
    if (u != v)
        fa[u] = v;
}

signed main() {
//  freopen("B.in", "r", stdin);
//  freopen("B.out", "w", stdout);
    cin.tie(0), cout.tie(0)->sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n * n; i++) {
        fa[i] = i;
    }
    for (int i = 1; i <= m; i++) {
        char c;
        int x, y;
        cin >> x >> y >> c;
        int id1 = (x - 1) * n + y, id2;
        if (c == 'R')
            id2 = (x - 1) * n + y + 1;
        else if (c == 'D')
            id2 = x * n + y;
        if (find(id1) == find(id2)) {
            cout << i;
            return 0;
        }
        unionn(id1, id2);
    }
    cout << "draw";
    return 0;
}

/*

3 5
1 1 D
1 1 R
1 2 D
2 1 R
2 2 D

(1, 1) -> (2, 1) union 1 and 4     fa[1] = 4

(1, 1) -> (1, 2) union 1 and 2     fa[1] = 2

(1, 2) -> (2, 2) union 2 and 5     fa[2] = 5

(2, 1) -> (2, 2) union 4 and 5     fa[4] = 5

*/

P1621 集合

我们可以在埃氏筛的基础上修改。

枚举每一个 i，因为 i 都是素数，所以他的倍数和他都有一个共同的质因子，将他们 unionn，最后判断有多少个不同的集合即可。

#include <bits/stdc++.h>

using namespace std;

int a, b, p, fa[100005];
bool vis[100005];

int find(int x) {
    return (fa[x] == x ? fa[x] : fa[x] = find(fa[x]));
}

void unionn(int x, int y) {
    x = find(x), y = find(y);
    if (x != y) {
        fa[x] = y;
    }
}

void prime(int n) {
    vis[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            for (int j = i + i; j <= n; j += i) {
                vis[j] = 1;
                if (i >= p) {
                    unionn(i, j);
                }
            }
        }
    }
}

signed main() {
//  freopen("C.in", "r", stdin);
//  freopen("C.out", "w", stdout);
    cin.tie(0), cout.tie(0)->sync_with_stdio(false);
    cin >> a >> b >> p;
    for (int i = 1; i <= b; i++) {
        fa[i] = i;
    }
    prime(b);
    int sum = 0;
    for (int i = a; i <= b; i++) {
        if (find(i) == i)
            sum++;
    }
    cout << sum;
    return 0;
}