2020工大杯题解-C

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

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;
}