手机版 欢迎访问it开发者社区(www.mfbz.cn)网站

当前位置: > 开发

【ACWing】238. 银河英雄传说

时间:2021/6/6 6:03:01|来源:|点击: 次

题目地址:

https://www.acwing.com/problem/content/240/

有一个划分为 N N N列的星际战场,各列依次编号为 1 , 2 , … , N 1,2,…,N 1,2,,N。有 N N N艘战舰,也依次编号为 1 , 2 , … , N 1,2,…,N 1,2,,N,其中第 i i i号战舰处于第 i i i列。有 T T T条指令,每条指令格式为以下两种之一:M i j,表示让第 i i i号战舰所在列的全部战舰保持原有顺序,接在第 j j j号战舰所在列的尾部。C i j,表示询问第 i i i号战舰与第 j j j号战舰当前是否处于同一列中,如果在同一列中,它们之间间隔了多少艘战舰。现在需要你编写一个程序,处理一系列的指令。

输入格式:
第一行包含整数 T T T,表示共有 T T T条指令。接下来 T T T行,每行一个指令,指令有两种形式:M i jC i j。其中 M M M C C C为大写字母表示指令类型, i i i j j j为整数,表示指令涉及的战舰编号。

输出格式:
你的程序应当依次对输入的每一条指令进行分析和处理:如果是M i j形式,则表示舰队排列发生了变化,你的程序要注意到这一点,但是不要输出任何信息;如果是C i j形式,你的程序要输出一行,仅包含一个整数,表示在同一列上,第 i i i号战舰与第 j j j号战舰之间布置的战舰数目,如果第 i i i号战舰与第 j j j号战舰当前不在同一列上,则输出 − 1 −1 1

数据范围:
N ≤ 30000 , T ≤ 500000 N≤30000,T≤500000 N30000,T500000

由于不仅要询问两个战舰是否同列,还需要知道两个战舰之间还有多少个战舰,所以需要用带权并查集来解决,即在维护集合的时候同时维护点与点之间的边权。我们可以维护并查集的每个树根为每列的最上面的那个战舰编号,然后再维护两个信息,一个是 s [ i ] s[i] s[i],表示 i i i所在集合的元素个数(只对树根有效),另一个是 d [ i ] d[i] d[i],表示 i i i到其父亲的距离(这里的“距离”指的是之间隔了的战舰数加 1 1 1,应答询问的时候是利用前缀和思想来求的。如果 i i i本身就是树根,则 d [ i ] = 0 d[i]=0 d[i]=0,如果是树根的孩子,并且 i i i号战舰紧挨着树根,则 d [ i ] = 1 d[i]=1 d[i]=1,以此类推)。维护 s s s是容易的,最重要的是怎么维护 d d d。首先在做合并集合的操作的时候,例如我们要将 x x x所在集合并到 y y y里,那么先找到两者的树根,即 p x p_x px p y p_y py,由于合并完之后 p x p_x px就会接到 p y p_y py下面,所以 p x p_x px与树根的距离就会被更新为 s [ p y ] s[p_y] s[py](类比两列战舰的合并,合并后战舰 p x p_x px会挂到 p y p_y py所在列的下面,当然距离就是 s [ p y ] s[p_y] s[py]了)。但是对于 p x p_x px所在集合的其余节点该如何处理呢?由于find函数的路径压缩优化,我们只需要在find里处理即可,在union的时候是不需要特别处理的(因为在询问的时候,会首先执行find,而find完之后由于路径压缩,所有节点都直接指向树根了)。在执行find(u)的时候,处理的方法是采用后序遍历,先递归地找到树根(此时 u u u节点的父亲 p u p_u pu已经连到树根上去了,并且 d [ p u ] d[p_u] d[pu]也算好了),然后将 d [ u ] d[u] d[u]累加其父亲的 d d d值即可,因为此时 d [ u ] d[u] d[u] u u u与父亲 p u p_u pu的距离,然后再累加 p u p_u pu到新树根的距离就行了。代码如下:

#include <iostream>
#include <cstring>
using namespace std;

const int N = 30010;
int m;
// sz[i]存i所在集合的元素个数(只对树根有效),d[i]存i与其父亲的距离
int p[N], sz[N], d[N];

int find(int x) {
    if (p[x] == x) return x;

    int root = find(p[x]);
    d[x] += d[p[x]];
    return p[x] = root;
}

void merge(int x, int y) {
    int px = find(x), py = find(y);
    p[px] = py, d[px] = sz[py];
    sz[py] += sz[px];
}

int main() {
    for (int i = 1; i < N; i++) p[i] = i, sz[i] = 1;

    scanf("%d", &m);
    while (m--) {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if (op[0] == 'M') {
            merge(a, b);
        } else {
            if (a == b) puts("0");

            int pa = find(a), pb = find(b);
            if (pa != pb) puts("-1");
            else printf("%d\n", abs(d[a]- d[b]) - 1);
        }
    }

    return 0;
}

时间复杂度 O ( N + T log ⁡ ∗ N ) O(N+T\log ^*N) O(N+TlogN),每次询问几乎可以看成是常数应答,空间 O ( N ) O(N) O(N)

Copyright © 2002-2019 某某自媒体运营 版权所有