2020工大杯题解-C

发表于 更新于 分类于 本文字数： 1.2k 阅读时长 ≈ 4 分钟

个人题解，和比赛官方无关，仅供参考

2020工大杯题解 - C - I 同学的课间

题目描述

午休期间，I 同学最爱做的就是追跑打闹了。

由于 I 同学力气很大，I 同学追跑打闹的时候，每一步都是从学校的一个教学楼跳到另一个教学楼。

但是学校的教学楼太多，为了避免迷路，I 同学决定用一根绳子跟在身后。

然而 I 同学在教学楼之间跳跃的动作会发出巨大声响，每一步都会得罪附近某栋教学楼中的同学们。

为了向 I 同学复仇，这些教学楼中的同学们决定沿着 I 同学跳跃时留下的绳子寻找位置和速度不能同时确定的 I 同学。聪明的 I 同学有时会记得身后刚刚留下的绳子，但是更多时候，聪明的 I 同学会忙着赶路，留下搭在刚刚跳过的两栋教学楼之间的绳子。

然而 I 同学很懒，他不知道向自己复仇的同学们能不能只沿着绳子就找到自己，聪明的你快来帮帮他，让 I 同学知道自己的人身是否安全吧！

输入

第一行为两个整数 N 和 Q，用一个空格分割，分别为学校教学楼的数目和 I 同学跳跃的总次数。$1 \leq N \leq 1000000$, $1 \leq Q \leq 500000$。
学校的教学楼编号 $1$ 到 $N$，I 同学初始在 $1$ 号教学楼。
接下来的 Q 行，每行为三个整数$ X Y Z$，其中 X 表示 I 同学跳跃的目标楼号，Y 表示 I 同学完成此次跳跃后得罪的同学所在教学楼的编号，Z 的取值为 0 或 1，0 表示 I 同学忘记切断绳子，1 表示 I 同学切断了绳子。

输出

每次 I 同学跳跃后，输出一行，如果 I 同学很安全，输出 “MHAHAHAHAHAHAHAHA!!!”，否则，如果 I 同学可能会遇到危险，输出 “HEEEEEEELP!!!”。
考虑到输出可能过大，如果 Q > 10，则只输出一个整数，为 “MHAHAHAHAHAHAHAHA!!!” 的个数，其余不进行输出。

样例输入和输出

Input

1
2
3
4
5
6
7
8
9
10
11
100 10
2 1 0
3 4 1
4 5 1
6 5 0
7 5 1
8 5 0
9 5 0
10 8 0
11 7 1
6 9 1

Output

1
2
3
4
5
6
7
8
9
10
HEEEEEEELP!!!!!!!!!!!
MHAHAHAHAHAHAHAHA!!!
HEEEEEEELP!!!!!!!!!!!
HEEEEEEELP!!!!!!!!!!!
MHAHAHAHAHAHAHAHA!!!
MHAHAHAHAHAHAHAHA!!!
MHAHAHAHAHAHAHAHA!!!
HEEEEEEELP!!!!!!!!!!!
MHAHAHAHAHAHAHAHA!!!
HEEEEEEELP!!!!!!!!!!!

提示

I 同学很聪明，如果两栋楼之间已经有绳子了，I 同学就不会自寻死路了

题解

题目重述

有 n 个教学楼， I （大写 i）同学从 1 号楼出发，每次跳跃到一个教学楼。有一定可能把两个教学楼用绳子连接起来。

每跳到一个教学楼会得罪附近的一些人。附近的人可以沿着绳子自由移动。于是，我们可以把绳子连接起来的几栋教学楼视为一个整体。只要跳到了一个包括得罪的人的教学楼组中，就凉凉了。

题目解法

复杂度分析：首先，一遍更新一遍查询，应使用在线算法。

其次，查询、更新次数为$500000$，并查集时间复杂度为$O\left(\alpha \left(n\right)\right)$， 可以接受。

于是用并查集。每链接一条绳子，就把两个教学楼所在集合合并到一起。每次得罪某栋楼的人，就把他所在的集合标记为已得罪。如果每次跳跃结束后，当前集合为已得罪，就凉了。反之，就稳了。

伪代码

1
2
3
4
5
6
初始化并查集
读入数据
对于每组数据：
	如果没切断绳子： 合并（当前所在，上一次所在）
	标记得罪了的集合
	输出状态或者保存 MAAAA 的次数

AC 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
using std::cin;
using std::cout;
using std::ios;
#define MH "MHAHAHAHAHAHAHAHA!!!"
#define HELP "HEEEEEEELP!!!!!!!!!!!"
#define endl '\n'
#define MAXN 1000001
// 并查集
int father[MAXN] = {0};
int size[MAXN] = {0};

int annoyed[MAXN] = {0}; // 是否惹了

int find(int i){
    if(father[i] == i) return i;
    return father[i] = find(father[i]);
}

void uni(int a,int b){
    int fa = find(a);
    int fb = find(b);
    if (size[fa] < size[fb]) {
        return uni(b,a);
    }
    size[fa] += size[fb];
    size[fb] = 0;
    father[fb] = fa;
    annoyed[fa] += annoyed[fb];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    for(int i = 1; i <= n; ++ i){
        father[i] = i;
        size[i] = 1;
    }
    int nowpos = 1;
    int to, annoying, cut;
    int help = 0;
    int ma_sum = 0;
    for(int _ = 0; _ < q; ++ _){
        cin>>to>>annoying>>cut;
        help = 0;
        if(!cut){
            uni(nowpos, to);
        }
        nowpos = to;
        annoyed[find(annoying)] = 1;
        int nn = find(nowpos);
        help = annoyed[nn];
        if(q <= 10){
            cout<<(help?HELP:MH)<<endl;
        }
        ma_sum += (help == 0);
    }
    if(q > 10){
        cout<<ma_sum<<endl;
    }
    return 0;
}