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

博客图片

题目连接

题目概述

初始时每一列有一个整数,现在有(T)条命令,格式为M i j或者C i j,M i j表示的是意思是将数(i)所在的那一列移动到数(j)所在的那一列的末尾,移动时保持数(i)原来列的顺序不变;C i j表示询问(i)和(j)之间有几个数,如果(i)和(j)不在同一列,那么输出-1,否则输出他们之间的数字的个数.数据范围:

[1leq T leq 5cdot 10^5, 1leq i,j leq 3000. ]

解题思路

也是一个集合划分的题目,只不过这个题目需要实时更新维护集合中结点到根节点的路径的长度,集合中元素的数目.通过一个数组(dis[i])记录维护结点(i)到根节点(s[i])的路径的长度,(cnt[i])记录集合的元素是数量.

结点(i)到根节点(s[i])的路径的长度可以在(find_set)操作进行路径压缩优化查询时进行,先逐层向上遍历找到根节点,然后从根节点开始向下更新结点到根节点的路径的长度,可以用递归方便的表示.
在合并集合时主要解决这两个问题,修改更新原来集合根节点(x)到现在合并后本的集合的根节点(y)的路径的长度,是原来根节点(y)所在的原来集合的元素的数量,因为合并时是把一个集合添加到一个集合的末尾;另外一个要更新维护此时结点(x)记录的集合的元素的数量为合并后的集合的元素的数量.
于是可以得到下面这样的程序

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N= 30005;
// 并查集
int s[N];
// 结点x到根节点s[x]的路径的长度
int dis[N];
// 结点x所在集合的结点的数量
int cnt[N];

void init_set(){
    for(int i = 0; i < N; i++){
        s[i] = i;
        dis[i] = 0;
        cnt[i] = 1;
    }
}

// 查询结点x的根节点,同时更新从结点x到根节点s[x]路径上结点到根节点的路径的长度,采用路径压缩算法
int find_set(int x){
    if(s[x] != x){
        // 自底向上寻找x的根节点,同时更新每个结点到根节点的距离
        int root = find_set(s[x]);
        // 更新结点x到根节点的距离
        dis[x] += dis[s[x]];
        // 路径压缩,更新结点x的前驱结点为根节点.
        s[x] = root;
    }
    return s[x];
}

// 将结点x合并到结点y所在的集合,更新结点x未合并前所在集合的根节点到合并后的根节点的长度和记录集合数量的值
void union_set(int x, int y){
    x = find_set(x);
    y = find_set(y);
    if( x != y){
        // 更新未合并前x所在集合的根节点到合并后集合的根节点的路径的长度,也就是未合并前y所在集合的元素的数量
        dis[x] = cnt[y];
        // 更新合并后的集合的元素的数量.
        cnt[y] += cnt[x];
        // 更新根节点
        s[x] = y;
    }
}

int main(int argc, const char** argv) {
    init_set();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin>>t;
    char ch;
    int x,y;
    while(t--){
        cin>>ch>>x>>y;
        if(ch == 'M')
            union_set(x,y);
        else if( ch == 'C'){
            if( find_set(x) != find_set(y))
                cout<<"-1"<<endl;
            else
                cout<<(abs(dis[x] - dis[y])-1)<<endl;
        }
    }
    return 0;
}

最初想的是用两个数组,一个指示当前元素所在集合的首元素,一个指示当前元素所在集合的末尾的元素(因为这个题意下的合并仍是一个线性的序列),然后直接模拟合并和查询的过程,然而时间复杂度太大TLE.