0%

A - 空中走廊

题目描述

同学们因每天要在不同教学楼之间往返而感到烦恼。尤其是在下雨天,地面上全是积水使得在地面上行走是完全不可能的。”为什么不能在教学楼之间修一些空中走廊呢?”

T 同学家缠万贯,因此决定出钱在教学楼之间修建一些空中走廊。学校有 栋教学楼,可以修建
个空中走廊。第 个空中走廊可以连接 号教学楼,需要消耗
的金钱。请你来给出一个施工方案,能够保证消耗最少的钱就能使得能够在下雨天从任意一个教学楼抵达任意一个其他教学楼。

输入数据

第一行有空格分隔的两个数

接下来 行每行包括三个数 ,意义已在上文给出。保证答案唯一,且

输出数据

对于要修建的每个空中走廊,输出一行三个数, ,意义已在上文给出。

输出按照 做从小到大的优先级排序。

如果不可能使得在下雨天能从任意一个教学楼到达其他教学楼,请输出一行 What the HELL?

样例输入

7 7
1 2 3
1 3 3
1 4 3
1 5 3
1 6 4
7 1 3
6 7 1

样例输出

1 2 3
1 3 3
1 4 3
1 5 3
1 7 3
6 7 1

题解

题面重述

显然是个图论题。题目要求说,消耗最少的钱使得能从任意一个教学楼抵达任意一个其他教学楼,因此看出是求图的最小生成树。

注意,**虽然说了 **,但是题目没有明确说明没有重边、自环,因此不能简单认为图是个简单图。

出题人好坑,快去打他

再注意,题目里是 ,也就是

出题人好坑,快去打他

对于最小生成树问题,我们可以使用 Kruskal 算法(就是离散数学课上教的那个)。

有进阶需求的同学看这里:

考虑两种求最小生成树的算法:Kruskal 与 Prim。

Kruskal 的时间复杂度为,Prim算法在使用 Fibonacci 堆的情况下,复杂度才比 Kruskal 优。

所以,在绝大部分情况下,直接使用 Kruskal 即可。

首先介绍并查集:顾名思义,并查集是一种可以合并和查找的集合。一个并查集应该有以下两种操作:

  1. find(i) 查询元素 i 属于的集合的编号。
  2. union(i,j) 合并元素 ij 属于的集合。

我们可以简单的用一个森林的数据结构实现并查集:我们维护一个数组 father[MAXN]father[i]代表第 i 个节点在森林中的父节点。如果 i 是森林中某棵树的根节点,我们规定father[i] = i。这样,对于任意一个元素i,我们不断查询father[i], father[fatehr[i]], ... 即可最终查询到 i 所在树的根节点。我们就可以把这个节点的编号作为 i 所在集合的编号。

而合并操作只需要把 i 所在树的根节点连接到 j 所在树的根节点下即可。

代码:

int father[MAXN] = {0};
void init(int size){
    for (int i = 0; i < size; ++ i){
        father[i] = i; // 最初每个节点单独属于自己的集合。
    }
}
void find(int n){
    if(father[n] != n) return find(father[n]);
    return father[n];
}
void unoin(int x, int y){
    father[find(x)] = find(y);
}

上面代码显然很慢:最坏时间复杂度为。对于每一次查询,我们都需要遍历节点所在的树直到根节点,这个过程无疑很慢,于是我们可以考虑在查询到i所属的根节点后直接把i移动到树的根部,直接连接到根节点:

father[i] = find(father[i]);

image-20201205205059347

这样子,下一次查询就只需要向上遍历一层。效率大大提高。这种优化方法被称为”路径压缩“。Tarjan 证明了其最坏复杂度为,而在姚期智的论文中,证明了仅使用路径压缩优化下的并查集的平均复杂度为,其中为阿克曼函数的反函数,其增长极其缓慢,也就是说其单次操作的平均运行时间可以认为是一个很小的常数。

优化后代码:

int father[MAXN] = {0};
void init(int size){
    for (int i = 0; i < size; ++ i){
        father[i] = i; // 最初每个节点单独属于自己的集合。
    }
}
void find(int n){
    if(father[n] != n) return father[n] = find(father[n]);
    return father[n];
}
void join(int x, int y){
    father[find(x)] = find(y);
}

说完并查集,再来说 Kruskal:

Kruskal 的核心算法是贪心。对于每一步,我们选择一条最短的、两端分别属于两个点的集合的边,标记这条边在 MST 中,把边两端的点的集合合并到一起。

代码:

for(int i = 0; i < m; ++ i){
    if(find(edges[i].u) != find(edges[i].v)){
        join(edges[i].u, edges[i].v); // 合并 u 与 v
        used_edges[num++] = edges[i]; // 把这条边保存到用到的边的数组中
        if(num == n) break;
    }
}

组合一下即可完成本道题,注意要按照 u v c 做优先级排序。

AC代码

#include 
#include 
using namespace std;
#define MAXN 100050
int father[MAXN];
int rk[MAXN];

int find(int v){
    return father[v] == v ? v : father[v] = find(father[v]);
}

void join(int x, int y){
    int px = find(x);
    int py = find(y);
    // 这里使用了优化:按秩合并
    // 也可以直接朴素合并,平均复杂度相同。
    if (rk[px] < rk[py]) {
        join(py, px);
    } else {
        rk[px] += rk[py];
        rk[py] = 0;
        father[py] = px;
    }
}

struct edge{
    int u,v;
    int w;
    bool operator<(const edge &that) const{
        return this->w < that.w;
    }
} edges[MAXN], used_edges[MAXN];

struct edge_magic{
    int u,v;
    int w;
    bool operator<(const edge_magic &that) const{
        if(this->u != that.u){
            return  this->u < that.u;
        }
        if(this->v != that.v){
            return  this->v < that.v;
        }
        return this->w < that.w;
    }
};

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    for(int i = 0; i < m; ++ i){
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        if(edges[i].u > edges[i].v){
            swap(edges[i].u, edges[i].v);
        }
    }
    sort(edges, edges+m);
    for(int i = 1; i <= n; ++ i){
        father[i] = i;
        rk[i] = 1;
    }
    int num = 0;
    for(int i = 0; i < m; ++ i){
        if(find(edges[i].u) != find(edges[i].v)){
            join(edges[i].u, edges[i].v);
            used_edges[num++] = edges[i];
            if(num == n) break;
        }
    }
    if(num != n - 1){
        cout<<"What the HELL?"<

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

2020工大杯题解 - E - Lawn Pattern Design

题目描述

Mr. Leo is a famous computer scientist, he invited you and your classmates to go on a vacation in his new house in the mountains. After a day of playing, many of you felt comfortable and sighed: “It’s quite nice to live in the mountains!”. Mr. Leo agreed with that, and he decided to play a game with you, to make the travel even more interesting.

There is an unmaintained lawn next to Mr. Leo’s house, he let you design a pattern for this lawn, and submit the pattern with a computer program. The lawn is 5 meters wide and 12 meters long, you are supposed to take one square meter as one unit, use “g” to indicate grass, and use “.” to indicate bare ground. For example, an unmaintained lawn can be described as the following:

.gggg
ggggg
gg.gg
ggggg
g..gg
ggggg
ggggg
ggggg
ggggg
ggggg
gggg.
gggg.

You had no idea about the pattern. However, your friend classmate T came to encourage and team up with you. “No matter what difficulties we meet, don’t be afraid, face it with a smile!” classmate T said, “Because the best way to overcome fear is to face it. Come on!”. After listening to the encouraging speech, you felt confident and asked him what could you do to help him. Classmate T explains that he had always believed that nobody knows pattern design better than him, however, he knew nothing about computer science. So he needed you to write his program to output his wonderful design.

You accepted the task at once, and ask him when can you get the final design. classmate T said that good designs need time to perfect, and he needs to find a great way to inform the Chinese character element in his design. Just like he always says: “Normal pretty design, not ok. Pretty design with Chinese character element, ok!”. After a night of work, classmate T finally gave you his design, please write a program to output it.

classmate T’s design:

.g.g.
ggggg
.g.g.
ggggg
g...g
ggggg
g...g
ggggg
..g..
ggggg
..g..
..g..

Input

There isn’t any input for this problem.

Output

Output classmate T’s design.

题解

题目重述

逗比题,直接输出即可。

用草字拼个草。

题目解法

#include <iostream>
using namespace std;
int main(){
    cout<<".g.g.\n"
          "ggggg\n"
          ".g.g.\n"
          "ggggg\n"
          "g...g\n"
          "ggggg\n"
          "g...g\n"
          "ggggg\n"
          "..g..\n"
          "ggggg\n"
          "..g..\n"
          "..g..\n";
    return 0;
}

彩蛋:

c / c++ 语言中, 如果两个字符串挨着, 中间没有代码, 如上面样例一样,就会合并为一个字符串。

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

2020工大杯题解-G - L 同学的睡眠

题目描述

L同学日理万机,睡眠非常不规律,最早下午7点就会睡觉,最晚早上7点才去睡觉。但规律的睡眠才会使L同学精力充沛,善良的你快关心一下L同学吧!

输入

第一行为空格分隔的3个整数。在接下来的天里,细心的你将记录L同学每天的睡眠时间,从第2天开始,如果在你所记录的过去天内(包括当天)L同学最早和最晚睡眠时间差超过了分钟,那么善良的你需要对L同学说句“辛苦了!”。

第二行为空格分隔的个时间,依次表示天你所记录L同学的睡眠时间,采用HH:MM格式的24小时制表示。

输出

输出一个整数表示你一共需要对L同学说多少次“辛苦了!”

样例输入

5 3 30
23:30 1:20 1:07 0:50 19:00

样例输出

3

题解

题目重述

暴力查询的时间复杂度为 ,肯定是不行的。因此,需要一种区间最值查询的数据结构。因此,这是一个 RMQ 问题。

RMQ 是英文 Range Maximum/Minimum Query 的缩写,表示区间最大(最小)值。

可以使用线段树、ST 表、单调栈解决问题。由于线段树和单调栈太简单了,没意思,这里介绍 ST 表。

ST 表是用于解决 可重复贡献问题 的数据结构。

可重复贡献问题 是指对于运算 ,满足 ,则对应的区间询问就是一个可重复贡献问题。例如,最大值有 ,gcd 有 ,所以 RMQ 和区间 GCD 就是一个可重复贡献问题。像区间和就不具有这个性质,如果求区间和的时候采用的预处理区间重叠了,则会导致重叠部分被计算两次,这是我们所不愿意看到的。另外, 还必须满足结合律才能使用 ST 表求解。

ST 表基于 倍增 思想,可以做到 预处理, 回答每个询问。但是不支持修改操作。

基于倍增思想,我们考虑如何求出区间最大值。可以发现,如果按照一般的倍增流程,每次跳 步的话,询问时的复杂度仍旧是 ,并没有比线段树更优,反而预处理一步还比线段树慢。

我们发现 ,也就是说,区间最大值是一个具有“可重复贡献”性质的问题。即使用来求解的预处理区间有重叠部分,只要这些区间的并是所求的区间,最终计算出的答案就是正确的。

如果手动模拟一下,可以发现我们能使用至多两个预处理过的区间来覆盖询问区间,也就是说询问时的时间复杂度可以被降至 ,在处理有大量询问的题目时十分有效。

具体实现如下:

表示区间 的最大值。

显然

根据定义式,第二维就相当于倍增的时候“跳了 步”,依据倍增的思路,写出状态转移方程:

img

以上就是预处理部分。而对于查询,可以简单实现如下:

对于每个询问 ,我们把它分成两部分:

其中

根据上面对于“可重复贡献问题”的论证,由于最大值是“可重复贡献问题”,重叠并不会对区间最大值产生影响。又因为这两个区间完全覆盖了 ,可以保证答案的正确性。

以上内容以 CC BY-SA 4.0 协议和 SATA 协议提供在 OI-WIKI

贡献者:orzAtalod, Henry-ZHR, leoleoasd, Chrogeek, H-J-Granger, ouuan

题目解法

#include <iostream>
using namespace std;
const int logn = 17;
const int maxn = 100050;
int fmax[maxn][logn+1], fmin[maxn][logn+1], Logn[maxn];
void pre() {
    Logn[1] = 0;
    Logn[2] = 1;
    for (int i = 3; i < maxn; i++) {
        Logn[i] = Logn[i / 2] + 1;
    }
}
int querymax(int x,int y){
    return max(fmax[x][Logn[y - x + 1]], fmax[y - (1 << Logn[y - x + 1]) + 1][Logn[y - x + 1]]);
}
int querymin(int x,int y){
    return min(fmin[x][Logn[y - x + 1]], fmin[y - (1 << Logn[y - x + 1]) + 1][Logn[y - x + 1]]);
}
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,d,t;
    int a,b;
    int output = 0;
    char _;
    cin>>n>>d>>t;
    for (int i = 1; i <= n; i++){
        cin>>a>>_>>b;
        fmax[i][0] = (a + 5) % 24 * 60 + b;
        fmin[i][0] = (a + 5) % 24 * 60 + b;
    }
    pre();
    for (int j = 1; j <= logn; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++){
            fmax[i][j] = max(fmax[i][j - 1], fmax[i + (1 << (j - 1))][j - 1]);
            fmin[i][j] = min(fmin[i][j - 1], fmin[i + (1 << (j - 1))][j - 1]);
        }

    for (int i = 1; i <= n; ++ i){
        int mm = querymax( max(i - d + 1, 1), i);
        int mi = querymin( max(i - d + 1, 1), i);
        if (mm - mi  > t){
            output++;
        }
    }
    cout<<output<<endl;
    return 0;
}

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

2020工大杯题解 - F - L 同学的程序课

题目描述

上完体育课之后,L同学接下来要上程序课。程序课自然离不开写代码,而写代码也离不开修BUG。虽然L同学十分优秀,但是也难逃与BUG斗争的命运。

所幸,L同学在与BUG的长时间较量中,积累了不少的经验。他发现他的程序可能出现的BUG共有N种。对于这些BUG,L同学掌握了K种方法,每种方法可以彻底修复一个类BUG,这需要花费的时间。

但对于大部分BUG而言彻底修复是很困难的,在修复的过程中往往会产生一个新的BUG。对此,L同学还掌握了M种方法,每种方法可以修复一个类BUG,但同时会产生一个类BUG,这需要花费的时间。

现在,为了能尽快的完成程序课作业,L同学希望能够知道使用他目前所掌握的方法,彻底修复一个第x类BUG所需要的最短时间是多少。由于L同学学业繁忙,所以只能由你来帮助他了。

输入

第一行,三个整数N、K、M,分别代表一共有N种BUG(BUG的编号从1到N)、L同学掌握K种能够彻底修复一个BUG的方法,和M种在产生一个新BUG的情况下修复一个BUG的方法。

而后K行,每行两个整数,代表L同学掌握一种方法能够用的时间彻底修复一个类BUG。

而后M行,每行三个整数,代表L同学掌握一种方法能够用的时间将一个类BUG修复,但同时会产生一个类BUG。

输出

共一行,用空格隔开的N个整数,第x个整数代表使用L同学使用掌握的方法彻底修复一个第x类BUG需要的最短时间。特别地,如果使用现有的方法无法彻底修复第x类的BUG,请在对应位置输出”INF”。

数据规模

对于100%的数据有:

输入输出样例

Input

5 3 4
1 3
2 9
5 1
1 3 4
4 2 5
1 2 2
2 5 3

Output

3 4 INF 9 1 

题解

题目解法

可以把 bug 视为一个图:有一个虚拟的 0 号节点代表彻底修复的 bug。如果第 个 bug 可以转变为 类 bug ,则由 连接到 一条单向边,权重为所需时间。如果可以彻底修复第类 bug,则由 连接到 一条单向边,权重为所需时间。然后求 号节点到每个节点的最短路即可。

分析时间复杂度: 因此使用堆优化的 (时间复杂度为)即可。

AC代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define MAXN 100050
struct road{
    int from;
    int time;
    road(int from, int time): from(from), time(time){}
    bool operator>(const road& that) const {
        return time > that.time;
    }
};
vector<road> roads[MAXN];
int dji[MAXN] = {0x3fffffff};
int vis[MAXN] = {0};
int n,k,m;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>k>>m;
    int t,a,b;
    for(int i = 0; i < k; ++ i){
        cin>>a>>b;
        roads[0].emplace_back(a, b);
    }
    for(int i = 0; i < m; ++ i){
        cin>>a>>b>>t;
        roads[b].emplace_back(a, t);
    }

    int count = 0;
    priority_queue<road, vector<road>, greater<road> > que;
    for(int i = 1; i <= n; ++ i){
        dji[i] = 0x3fffffff;
        vis[i] = 0;
    }
    dji[0] = 0;
    que.emplace(0,0);
    while(!que.empty()){
        int from = que.top().from;
        que.pop();
        if(vis[from]){
            continue;
        }
        vis[from] = 1;
        for(auto &rr: roads[from]){
            if (dji[rr.from] > rr.time + dji[from]){
                dji[rr.from] = rr.time + dji[from];
                que.emplace(rr.from, dji[rr.from]);
            }
        }
        count++;
        if(count == n+1) break;
    }

    for(int i = 1; i <= n; ++ i){
        if(dji[i] < 0x3fffffff){
            cout<<dji[i]<<" ";
        } else {
            cout<<"INF ";
        }
    }
    return 0;
}

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

2020工大杯题解 - D - L 同学的又一节体育课

题目描述

迫于忘了选体育课, L同学只能上一个没人选的奇怪的体育课. 在这门课上,
学生被要求玩一个奇怪的游戏, 叫做 “能量传输”. 在这个游戏中, 同学们的目标是组成轨道,
把球从起点传输至筒中, 并保证全程球不能脱轨, 不能把筒撞倒. 全班同学被分成两组, 分别比赛,
之后老师会根据完成小组完成任务的时间的排名来赋予平时分. L同学想要在体育课上内卷,
他想知道需要卷到什么程度. 他偷偷瞄到了另一个组的轨道,
想要问问你另一个组需要多久来完成任务.

一个轨道可以视为一个 8 个长度为 16 的字符串, 如下表示:

-
 \
  \
   -----
        \
         \  --
          -/  \
               V
  • - 表示一个横着摆放的轨道.
  • /\ 分别表示 上升/下降 的斜着摆放的轨道.
  • V 表示目标球桶.
  • 行末最后的空格 可以省略. 如, 上面的字符矩阵中的第一行, 右边省略了15个空格.

为了模拟球的行为, 我们可以认为球有以下属性:

  • 坐标 . 表示横坐标,表示高度.
    左下角坐标为, 正方向向上, 正方向向右.
  • 速度 v. 不考虑速度的矢量性.

不同摆放的轨道会对于球的速度有如下影响:

  • -: v -= 3
  • \: v += 10
  • /: v -= 15

在运球过程中, 有以下限制:

  • 任意时刻, 球的速度不能超过40, 否则会冲出轨道外.
  • 任意时刻, 球的速度不能小于或等于0, 否则会停止运动.
  • 落入桶中的时候, 球的速度不能超过15, 不然会把桶撞倒.

我们定义球的一次移动为球的横坐标加一的过程. 在球的一次移动中:

  • 如果当前轨道是 \:
    • 如果下一个轨道是 \: 其高度必须比当前轨道少1.
    • 如果下一个轨道是 /: 其高度必须比当前轨道少1.
    • 如果下一个轨道是 -: 其高度必须比当前轨道少1.
    • 如果下一个轨道是 V: 其高度必须比当前轨道少1.
  • 如果当前轨道是 -:
    • 如果下一个轨道是 \: 其高度必须比当前轨道少1.
    • 如果下一个轨道是 /: 其高度必须和当前轨道相同.
    • 如果下一个轨道是 -: 其高度必须和当前轨道相同.
    • 如果下一个轨道是 V: 无论高度如何, 球会脱轨.
  • 如果当前轨道是 /:
    • 如果下一个轨道是 \: 无论高度如何, 球会脱轨.
    • 如果下一个轨道是 /: 其高度必须比当前轨道多1.
    • 如果下一个轨道是 -: 其高度必须比当前轨道多1.
    • 如果下一个轨道是 V: 无论高度如何, 球会脱轨.

为了简化问题, 我们可以如下进行模拟:

  1. 球的初速度为4.
  2. 如果当前轨道是V: 则已经到达终点. 跳转到第六步.
  3. 把通过当前轨道所需时间 累加到总时间中. 做除法后保留整数部分.
  4. 通过轨道后, 根据轨道类型, 更新当前速度, 并判断是否可以进入下一个轨道.
  5. 跳转到第二步.
  6. 输出完成任务所需要的总时间. 如果不能完成任务, 请输出-1.

球的初始坐标为 (1, 8), 保证这一格的轨道为 -. 保证坐标为的地方的轨道为V.

输入数据

8 行, 每行一个长度为 16 的字符串, 表示轨道.

保证每列只有一个不是空格的字符, 且其属于 / \ - V

输出数据

一个整数, 代表和 L 同学竞争的组完成任务所需时间.

如果不能完成任务, 请输出-1.

样例输入

-
 \
  \
   -----
        \
         \  --
          -/  \
               V

样例输出

80

样例解释

通过每一格的速度分别为:

4 1 11 21 18 15 12 9 6 16 26 23 8 5 2

所需时间分别为

7 30 2 1 1 2 2 3 5 1 1 1 3 6 15

题解

题目重述

大模拟题,暴力模拟即可,考察细节。

题目解法

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

int main(){
    int height[17] = {0};
    int type[17] = {0};
    // -: 0  /: 1 \: 2 v: 3
    int delta_V[4] = {-3,-15,10,0};
    string now;
    for(int i = 0; i < 8; ++ i){
        getline(cin, now);
        int j = 0;
        for(char &c: now){
            switch(c){
                case '-':
                    height[j+1] = 8 - i;
                    type[j+1] = 0;
                    break;
                case '/':
                    height[j+1] = 8 - i;
                    type[j+1] = 1;
                    break;
                case '\\':
                    height[j+1] = 8 - i;
                    type[j+1] = 2;
                    break;
                case 'V':
                    height[j+1] = 8 - i;
                    type[j+1] = 3;
                    break;
                default:
                    break;
            }
            j++;
        }
    }
    int v = 4;
    int x = 1;
    int y = 8;
    int t = 0;
    while(true){
        //cout<<v<<" ";
        if(type[x] == 3){
            if(v > 15){
                t = -1;
            }
            break;
        }
        if(v > 40 or v <= 0){
            t = -1;
            break;
        }
        t += (30 / v);
        if(type[x] == 0){
            if(type[x+1] == 0){
                if(height[x+1] != height[x]){
                    t = -1;
                    break;
                }
            }else if(type[x+1] == 1){
                if(height[x+1] != height[x]){
                    t = -1;
                    break;
                }
            }else if(type[x+1] == 2){
                if(height[x+1] != height[x]-1){
                    t = -1;
                    break;
                } else {
                    y -= 1;
                }
            }else if(type[x+1] == 3) {
                t = -1;
                break;
            }
        }else if(type[x] == 1) {
            if(type[x+1] == 0) {
                if(height[x+1] != height[x] + 1){
                    t = -1;
                    break;
                } else {
                    y += 1;
                };
            }else if(type[x+1] == 1) {
                if(height[x+1] != height[x] + 1){
                    t = -1;
                    break;
                } else {
                    y += 1;
                };
            }else if(type[x+1] == 2) {
                t = -1;
                break;
            }else if(type[x+1] == 3){
                t = -1;
                break;
            }
        }else if(type[x] == 2) {
            if(height[x+1] != height[x] - 1){
                t = -1;
                break;
            }
            y -= 1;
        }
        v += delta_V[type[x]];
        x++;
    }
    cout<<t<<endl;
    return 0;
}

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

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