「NOI2002」银河英雄传说

发布于 2018-02-20  196 次阅读


题意描述

有 300,000 个元素,每种元素初始时以单独队列存在,支持下面两种操作:

1.合并两个队列,即将x元素所在队列首部接至y元素所在队列的尾部。
2.查询两个元素x,y是否在同一队列,如果是,则求两元素的间隔元素的数量

操作 500,000 次

链接

洛谷

题解

我们可以显而易见看出这是一道并查集的题目,在这里我们要使用一种叫做带权并查集的东西。
对于带权并查集,我们需要维护一个权值$ dist[i] $表示$ i $到$ f[i] $的距离。
然后就套用并查集模版,注意路径压缩和合并时候顺便处理一下$ dist[i] $即可。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

const int MAXN = 30000 + 5;

inline void Read(int &x){  //快读提高速度
    int ret = 0,flag = 1;
    x = 0;
    char ch = getchar();
    while(ch > '9' || ch < '0'){
        if(ch == '-') flag = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        ret = (ret << 1) + (ret << 3) + ch - '0';
        ch = getchar();
    }
    x = ret * flag;
}

int f[MAXN],num[MAXN],dist[MAXN],t;
//f[i]表示i的父亲,num[i]表示i所在队列的大小,dist[i]表示i到f[i]的距离。

inline void init(){   //初始化并查集
    for(int i = 1;i <= MAXN;i++){
        f[i] = i;
        num[i] = 1;
    }
}

int find(int x){  //查找+路径压缩
    if(x != f[x]){
        int t = f[x];
        f[x] = find(f[x]);
        dist[x] += dist[t];
        num[x] = num[f[x]];
    }
    return f[x];
}

void Union(int x,int y){  //合并x,y所在的队列
    int fx = find(x), fy = find(y);
    if(fx != fy){
        f[fx] = fy;
        dist[fx] = dist[fy] + num[fy];
        num[fy] += num[fx];
        num[fx] = num[fy];
    }
}

int query(int a,int b){  //查询x,y的距离
    int fa = find(a),fb = find(b);
    if(fa != fb) return -1;
    else
        return std::abs(dist[a] - dist[b]) - 1;
}

inline bool istrue(char ch){  //特判读入
    return ch == 'C' || ch == 'M';
}

int main(){
    int T;
    Read(T);
    init();
    for(int i = 1;i <= T;i++){
        char ch;
        while(!istrue(ch = getchar())); //这里读入有坑,我WA了3次才知道
        //scanf("%c",&ch);   //错误的做法
        int l,r;
        Read(l);Read(r);
        if(ch == 'M') Union(l,r);
        else printf("%d\n",query(l,r));
    }
    //getchar();getchar();
    return 0;
}

一个OIer。