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

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:

1
2
3
4
5
6
7
8
9
10
11
12

.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:

1
2
3
4
5
6
7
8
9
10
11
12

.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.

题解

题目重述

逗比题，直接输出即可。

用草字拼个草。

题目解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#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工大杯题解 - F - L 同学的程序课

题目描述

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

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

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

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

输入

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

而后K行，每行两个整数$A_i$、$T_{1i}$，代表L同学掌握一种方法能够用$T_{1i}$的时间彻底修复一个$A_i$类BUG。

而后M行，每行三个整数$B_j$、$C_j$、$T_{2j}$，代表L同学掌握一种方法能够用$T_{2j}$的时间将一个$B_j$类BUG修复，但同时会产生一个$C_j$类BUG。

输出

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

数据规模

对于100%的数据有：

$1 \leq N \leq 10^5$

$0 \leq K,M \leq 2*10^5$

$0 \leq K+M \leq 2*10^5$

$1 \leq A_i,B_j,C_j \leq N$

$1 \leq T_{1i},T_{2j} \leq 10^4$

$1 \leq \sum_{i=1}^{K}T_{1i}+\sum_{j=1}^{M}T_{2j} \leq 10^9$

输入输出样例

Input

1
2
3
4
5
6
7
8

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

Output

1

3 4 INF 9 1 

题解

题目解法

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

分析时间复杂度：$1 \leq N \leq 10^5$ $0 \leq K,M \leq 2*10^5$ 因此使用堆优化的 $dijkstra$ （时间复杂度为$O\left(m \times \log\left(m\right)\right)$）即可。

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
65
66

#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工大杯题解-G - L 同学的睡眠

题目描述

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

输入

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

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

$2\le N \le 10^5, 2 \le D \le 10^5, 1 \le T \le 719$

输出

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

样例输入

1
2

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

样例输出

1

3

题解

题目重述

$2\le N \le 10^5, 2 \le D \le 10^5, 1 \le T \le 719$

暴力查询的时间复杂度为 $O(D \times N)$，肯定是不行的。因此，需要一种区间最值查询的数据结构。因此，这是一个 RMQ 问题。

RMQ 是英文 Range Maximum/Minimum Query 的缩写，表示区间最大（最小）值。

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

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

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

ST 表基于 倍增 思想，可以做到 $\Theta(n\log n)$ 预处理， $\Theta(1)$ 回答每个询问。但是不支持修改操作。

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

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

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

具体实现如下：

令 $f(i,j)$ 表示区间 $[i,i+2^j-1]$ 的最大值。

显然 $f(i,0)=a_i$ 。

根据定义式，第二维就相当于倍增的时候“跳了 $2^j-1$ 步”，依据倍增的思路，写出状态转移方程： $f(i,j)=\max(f(i,j-1),f(i+2^{j-1},j-1))$ 。

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

对于每个询问 $[l,r]$ ，我们把它分成两部分： $f[l,l+2^s-1]$ 与 $f[r-2^s+1,r]$ 。

其中 $s=\left\lfloor\log_2(r-l+1)\right\rfloor$ 。

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

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

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

题目解法

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

#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工大杯题解 - D - L 同学的又一节体育课

题目描述

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

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

1
2
3
4
5
6
7
8

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

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

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

• 坐标 $\left(x,y\right)$. $x$表示横坐标,$y$表示高度. $1 \leq x \leq 16, 1 \leq y \leq 8$。
  左下角坐标为$\left(1,1\right)$, $x$正方向向上, $y$正方向向右.
• 速度 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. 把通过当前轨道所需时间 $30 / v$ 累加到总时间中. 做除法后保留整数部分.
4. 通过轨道后, 根据轨道类型, 更新当前速度, 并判断是否可以进入下一个轨道.
5. 跳转到第二步.
6. 输出完成任务所需要的总时间. 如果不能完成任务, 请输出-1.

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

输入数据

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

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

输出数据

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

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

样例输入

1
2
3
4
5
6
7
8

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

样例输出

1

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

题解

题目重述

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

题目解法

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

#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 同学跳跃的总次数。$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;
}

编程中极值的选取

很多时候，在编程中我们都需要把一些变量初始化为极大、极小值。下面是对于一些常见极值的比较。

TL; DR:

比较时用 0x7fffffff， 需要参与运算（如 a = max(a+b, c) ）时， 用 0x3fffffff 或 0x3f3f3f3f

不用数了， 7 个 f。

如果是 long long， 用 0x7fffffffffffffffLL 或 0x3f3f3f3f3f3f3f3fLL 或 0x3fffffffffffffffLL

15 个 f。

10000000

此类极值无疑是最简单的一种， 随手写即可。初学阶段可以使用，但是后期就会产生风险。

首先，如果手欠多写了几个 0， 会发生什么呢？

可以运行一下代码测试一下：

1
2

printf("%d", 10000000000);
// Outputs 1410065408

这是为什么呢？ 注意， 在 C 语言中， 字面量也是有类型的。 $10000000000$的类型是 int，但是他超过了 int 所能表示的最大值 $2147483647$，所以溢出为了 $1410065408$。

其次，如果少写了几个 0，会发生什么呢？

”极大值“选取的不够大，程序就会算出错误的结果。

所以， 不建议这样选取极大值。

0x7fffffff

当需要进行比较类型的运算时，（如保存最小值的变量要用一个极大值初始化），可以初始化为0x7fffffff。

原因：

1. 他是 int 类型变量的最大值，绝大部分情境下足够大。
2. 比 10 进制下 int 变量最大值$\left(2147483647\right)$更好记忆。 （7 后 7 个 f）

缺点：

因为它是 int 最大值，加上 1 都会溢出为负数。所以仅能在不需要进行算数运算，仅需要进行比较时使用。

0x3fffffff / 0x3f3f3f3f

需要极值参与的运算大部分情况下都是这样的：

1
2

a = max(a+b, c);
// a 和 b 可能是极大值

这种情况下，仅需要保证 $a+b$ 的过程不溢出，既保证$a \leq INT_MAX / 2$ 即可。所以，a 可以初始化为0x3fffffff。（一样还是 7 个 f）

同样，在图论题中，我们经常需要把一整个二维数组赋值为极值。这种情况下，0x3fffffff不能使用memset进行一次性赋值。因此，采用略小一些的 0x3f3f3f3f 就可以一次性用memset赋值：

1
2

int data[MAXN][MAXM];
memset(data, 0x3f, sizeof data);

还记得吗？ memset 函数是对于给定大小数组的每个字节赋值为指定的值。