首页 > 其他分享 >洛谷 P1196 [NOI2002] 银河英雄传说

洛谷 P1196 [NOI2002] 银河英雄传说

时间:2024-04-04 10:34:03浏览次数:28  
标签:sz dist int return fa findSet NOI2002 洛谷 P1196

题意:30000列军队,每列初始有1个。编号从1~30000.每次操作有两种,将现在第i列所在的列合并到第j列所在列的末尾。 或者查询第i列举例第j列的距离。

思路:带权并查集。合并时将第i列头节点接到第j列头节点上。然后直接查询dist取绝对值相减就好。

总结:一开始没看清题,以为要把从i列从当前所在列中截取出来接到第j列所在列末尾,就多了一个i列队头减i列元素数量的情况。

class DisjointSet{
public:
    DisjointSet(int sz): sz_(sz){
        fa_.resize(sz_);
        iota(fa_.begin(), fa_.end(), 0);
        set_size_.assign(sz_, 1);
        dist_.assign(sz_, 0);
    }

    int findSet(int x){
        if (fa_[x] == x){
            return x;
        }
        return updateDist(x), fa_[x];
    }

    bool isSameSet(int x, int y){
        return findSet(x) == findSet(y);
    }

    void unionSet(int x, int y){
        int px = findSet(x);
        int py = findSet(y);
        fa_[px] = py;
        dist_[px] = set_size_[py];
        set_size_[py] += set_size_[px];
    }

    int getDist(int x){
        updateDist(x);
        return dist_[x];
    }


private:
    int sz_;
    vector<int> fa_;
    vector<int> set_size_;
    vector<int> dist_;

    inline void updateDist(int x){
        if (fa_[x] == x){
            return;
        }
        int par = fa_[x];
        fa_[x] = findSet(fa_[x]);
        dist_[x] += dist_[par];
    }
};



void solve(){
    int q;
    cin >> q;

    DisjointSet dsu(300010);

    while (q --){
        char t;
        cin >> t;
        int i, j;
        cin >> i >> j;
        if (t == 'M'){
            dsu.unionSet(i, j);
        }
        else{
            if (dsu.isSameSet(i, j) == false){
                cout << -1 << '\n';
            }
            else{
                cout << abs(dsu.getDist(j) - dsu.getDist(i)) - 1 << '\n';
            }
        }
    }
}

标签:sz,dist,int,return,fa,findSet,NOI2002,洛谷,P1196
From: https://www.cnblogs.com/yxcblogs/p/18113955

相关文章

  • 洛谷:P8671 [蓝桥杯 2018 国 AC] 约瑟夫环
    时间限制1.00s     内存限制256.00MB     难易度:普及+/提高【题目描述】n 个人的编号是1∼n,如果他们依编号按顺时针排成一个圆圈,从编号是 1 的人开始顺时针报数。(报数是从 1 报起)当报到 k 的时候,这个人就退出游戏圈。下一个人重新从 1 开始报......
  • 每日一题 第六十六期 洛谷 小朋友排队
    [蓝桥杯2014省B]小朋友排队题目描述nnn个小朋友站成一排。现在要把他们按身高从低到高的顺序排列,但是每次只能交换位置相邻的两个小朋友。每个小朋友都有一个不高......
  • 洛谷题单指南-图的基本应用-P1347 排序
    原题链接:https://www.luogu.com.cn/problem/P1347题意解读:在给出多对关系字母的比较关系之后,判断能否确定所有字母的顺序。解题思路:对字母的关系建立图,如A<B建立A指向B的一条边。如果在拓扑排序过程中,每次寻找入度为0的点只有一个,且最终可以形成拓扑序,则可以确定所有字母的顺......
  • 【洛谷 P8695】[蓝桥杯 2019 国 AC] 轨道炮 题解(映射+模拟+暴力枚举+桶排序)
    [蓝桥杯2019国AC]轨道炮题目描述小明在玩一款战争游戏。地图上一共有NNN个敌方单位,可以看作2D平面上的点。其中第i......
  • 【洛谷 P8672】[蓝桥杯 2018 国 C] 交换次数 题解(字符串+映射+全排列)
    [蓝桥杯2018国C]交换次数题目描述IT产业人才需求节节攀升。业内巨头百度、阿里巴巴、腾讯(简称BAT)在某海滩进行招聘活动。招聘部门一字排开。由于是自由抢占席位,三大公司的席位随机交错在一起,形如:ABABTATT,这使得应聘者十分别扭。于是,管理部门要求招聘方进行必要的......
  • 【洛谷 P8700】[蓝桥杯 2019 国 B] 解谜游戏 题解(字符串+映射+周期性)
    [蓝桥杯2019国B]解谜游戏题目背景题目描述小明正在玩一款解谜游戏。谜题由242424根塑料棒组成,其中黄色塑料棒4......
  • 洛谷题单指南-图的基本应用-P1363 幻象迷宫
    原题链接:题意解读:迷宫可以无限扩展,对第一个样例进行模拟,扩展4块的示意图:从起点S,沿着红色虚线,是可以无限走下去的,要判断是否能够无限走下去。解题思路:直观上,会考虑把迷宫复制多块,但是会面临2个问题:1、内存可能爆掉2、如何有效判断可以无限走下去?只考虑竖向或者横向连通是不......
  • 洛谷4555-回文串
    link:https://www.luogu.com.cn/problem/P4555题:顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串,而abc不是:abc的顺序为abc,逆序为cba,不相同。输入长度为\(n\)的串\(S\),求\(S\)的最长双回文子串\(T\),即可将\(T\)分为两部分\(X,Y\)(\(|X|,|Y|≥1\))且\(X......
  • 洛谷 P1008 [NOIP1998 普及组] 三连击
    这道题我们可以用桶排序来做,代码如下:#include<bits/stdc++.h>//万能头 usingnamespacestd;//好习惯 inta[10];//一个桶数组,来确定是否有重复的 intmain(){   ints1,s2,s3;//定三个函数,用于判断    intsum=0;//用于判断数字是否重复    for(int......
  • 可视化红黑树详解(gif图演示,洛谷P3369 普通平衡树)
    写在前面推荐一个很实用的工具:红黑树可视化本文参考OIwiki中的红黑树代码,读者也可以参考该篇解析(写得还是很不错的),不过OIWiki里删除后平衡维护的Case4和Case5在代码细节上稍微有些问题(把c......