0%

2020工大杯题解-C

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

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

题目描述

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

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

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

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

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

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

输入

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

输出

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

样例输入和输出

Input

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

HEEEEEEELP!!!!!!!!!!!
MHAHAHAHAHAHAHAHA!!!
HEEEEEEELP!!!!!!!!!!!
HEEEEEEELP!!!!!!!!!!!
MHAHAHAHAHAHAHAHA!!!
MHAHAHAHAHAHAHAHA!!!
MHAHAHAHAHAHAHAHA!!!
HEEEEEEELP!!!!!!!!!!!
MHAHAHAHAHAHAHAHA!!!
HEEEEEEELP!!!!!!!!!!!

提示

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

题解

题目重述

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

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

题目解法

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

其次,查询、更新次数为,并查集时间复杂度为, 可以接受。

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

伪代码

初始化并查集
读入数据
对于每组数据:
    如果没切断绳子: 合并(当前所在,上一次所在)
    标记得罪了的集合
    输出状态或者保存 MAAAA 的次数

AC 代码

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

欢迎关注我的其它发布渠道