首页 > 其他分享 >【并查集】【中间值范围】NOIP2017]奶酪

【并查集】【中间值范围】NOIP2017]奶酪

时间:2024-10-30 18:00:04浏览次数:1  
标签:NOIP2017 parent 奶酪 查集 rank find rootY rootX ll

https://ac.nowcoder.com/acm/contest/22904/1027

开了ll还见祖宗
注意x^2 + y2算完之后先判断有没有超4r2的范围,没有的话再计算z^2,算是对long long溢出的特判

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;

class UnionFind {
public:
    UnionFind(ll n) : parent(n), rank(n, 1) {
        for (ll i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    ll find(ll x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    void unite(ll x, ll y) {
        ll rootX = find(x);
        ll rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

    bool connected(ll x, ll y) {
        return find(x) == find(y);
    }

private:
    vector<ll> parent;
    vector<ll> rank;
};

// 计算两点之间的欧几里得距离平方
bool isConnected(ll x1, ll y1, ll z1, ll x2, ll y2, ll z2, ll r) {
    ll dx = x1 - x2;
    ll dy = y1 - y2;
    ll dz = z1 - z2;
    if(dx * dx + dy * dy > 4 * r * r) {
        return false;
    }
    return dx * dx + dy * dy + dz * dz <= 4 * r * r;
}

int main() {
    ll T;
    cin >> T;
    while (T--) {
        ll n, h, r;
        cin >> n >> h >> r;

        vector<tuple<ll, ll, ll>> holes(n);
        for (ll i = 0; i < n; ++i) {
            ll x, y, z;
            cin >> x >> y >> z;
            holes[i] = {x, y, z};
        }

        UnionFind uf(n);
        vector<int> bottom, top;

        for (int i = 0; i < n; ++i) {
            auto [x1, y1, z1] = holes[i];
            if (z1 <= r) {
                bottom.push_back(i);
            }
            if (z1 >= h - r) {
                top.push_back(i);
            }
            for (ll j = i + 1; j < n; ++j) {
                auto [x2, y2, z2] = holes[j];
                if (isConnected(x1, y1, z1, x2, y2, z2, r)) {
                    uf.unite(i, j);
                }
            }
        }

        bool canReach = false;
        for (ll b : bottom) {
            for (ll t : top) {
                if (uf.connected(b, t)) {
                    canReach = true;
                    break;
                }
            }
            if (canReach) break;
        }

        cout << (canReach ? "Yes" : "No") << endl;
    }

    return 0;
}

标签:NOIP2017,parent,奶酪,查集,rank,find,rootY,rootX,ll
From: https://www.cnblogs.com/peterzh/p/18516312

相关文章

  • 【寻迹#4】并查集
    并查集一、并查集并查集是一种用于管理元素所属集合的数据结构,实现为一个森林,其中每棵树表示一个集合,树中的节点表示对应集合中的元素。顾名思义,并查集支持两种操作:合并(Union):合并两个元素所属集合(合并对应的树)查询(Find):查询某个元素所属集合(查询对应的树的根节点),这可以用于判......
  • 并查集
    并查集并查集是一种数据结构,它主要处理一些不相交集合的合并问题。一些常见的用途有求连通子图、最小生成树Kruskal算法和求公共祖先等。并查集的主要操作有:初始化Init查询Find合并Union初始化Init()voidInit(intn){vector<int>father(n+1);//创......
  • 经典算法思想--并查集
    前言 (最近在学习Java,所有函数都是用Java语言来书写的)前言部分是一些前提储备知识在并查集(Union-Find)数据结构中,rank(中文称为“秩”)是用来表示树的高度或深度的一种辅助信息。它的主要作用是优化合并操作,以保持并查集的结构尽可能扁平,从而提高查询效率。秩的具体定义......
  • CF771A. Bear and Friendship Condition 题解 并查集
    题目链接:https://codeforces.com/problemset/problem/771/A视频讲解:https://www.bilibili.com/video/BV1tZ1FYPELp/?p=6题目大意:判断一个无向图中的每个连通块是否都是一个完全图。首先我们可以用并查集维护每个连通块的大小。其次,我们可以开一个\(cnt_i\)表示以节点\(i\)......
  • CF1139C. Edgy Trees 题解 并查集
    题目链接:https://codeforces.com/problemset/problem/1139/C视频讲解:https://www.bilibili.com/video/BV1tZ1FYPELp?p=3我们可以求总方案数-不满足条件的方案数。设一个不包含黑色边的极大连通块的大小为\(sz_i\)。则答案为\[n^k-\sum\{sz_i^k\}\]示例程序:#include......
  • CF1800E2. Unforgivable Curse (hard version) 题解 并查集
    题目链接:https://codeforces.com/contest/1800/problem/E2视频讲解:https://www.bilibili.com/video/BV1tZ1FYPELp?p=2把下标\(i\)对应到图中编号为\(i\)的节点。节点\(i\)和\(i+k\)之间连一条边,节点\(i\)和\(i+k+1\)之间也连一条边。同一个连通块里的节点对应的字......
  • 新高一暑假第一期集训恢复性训练【数据结构-晚测】(并查集)(补)
    新高一暑假第一期集训恢复性训练【数据结构-晚测】(并查集)(补)[CF1290C]PrefixEnlightment带权扩展域并查集。任意三个子集的交集为空集,显然,一个点最多只能在两个集合中出现,这样所有集合的大小之和是\(\Theta(n)\)的。一个在两个集合中出现的点ii相当于连接了\(2\)个集合......
  • 带权并查集 学习笔记
    顾名思义,就是并查集带权值。在路径压缩的时候,我们还要维护权值应该怎么办呢?关联题目:P1196[NOI2002]银河英雄传说。我们对于一个舰队维护一个\(fr\)表示到头部的距离,\(cnt\)表示该舰队的战舰数量。那么每一次合并时,先进行路径压缩,找到父亲,在将父亲的权值传下来即可。因为每......
  • 新高一暑假第一期集训恢复性训练【数据结构-并查集】(补)
    新高一暑假第一期集训恢复性训练【数据结构-并查集】(补)C.[POJ1417]TrueLiars先将题目中的好人和坏人转换一下,也即是如果\(x\)说\(y\)是好人,则他们两属于同一组,反之则不属于同一组。然后我们可以想到带权的并查集,用\(val_x\)代表\(x\)与其父节点的关系,当\(val_x\)......
  • 学习笔记 - 并查集
    本人实力不济,如有错误或建议及补充,请指出1.定义并查集是一种用于管理元素所属集合的数据结构,实现为一个森林,其中每棵树表示一个集合,树中的节点表示对应集合中的元素。顾名思义,并查集支持两种操作:合并(Union):合并两个元素所属集合(合并对应的树)查询(Find):查询某个元素所属集合(查询......