0%

背景

最近在校内部署了我们开发的EduOJ以供数据结构与算法课程使用。OJ中使用了 clang 编译器以避免gcc编译器造成的坑(如#include</dev/random>能卡死编译器,以及某段很短的代码能产生数G的错误日志)。同时,按照惯例,开启了O2优化。

上线后不久,很多同学反映说OJ不好用。我问咋回事儿,同学说代码本地运行都是对的,提交到平台上之后就是错的了。相关代码片段如下:

  1. 这段代码运行结果和本地不一样
while (head->next != nullptr) {
  if (cnt == m) {
    cout << p->data << ' ';

    // del 是代码作者定义的一个函数,里面调用了
    // delete p
    del(p); 
    cnt = 0;
  } else {
    cnt += 1;
    if (p->next != nullptr) {
      p = p->next;
    } else {
      p = head->next;
    }
  }
}

可以看到,他在delete p后还访问了p->next

  1. 这段更离谱:
template<typename T> bool ArrayList<T>::append(T const& value) {
  if(_size >= _capacity){ // border check;
    cout<<"SIZE "<<_size<<" CAP "<<_capacity;
    cout << " The List is overflow!" << endl;
    return false;
  }
  _elem[_size++] = value;
}

会输出SIZE 0 CAP 2000 The List is overflow!

看到这里,你可能已经急了。明明size0cap2000,为什么if里的size >= cap会成立呢?先别急,接着看下面的代码:

  1. 这段代码很难找出错(所以建议跳过去不看):
#include <iostream>
using namespace std;
int main() {
  int n, s, m, j, tempt, q, k, flag;
  int count = 1;
  int data[2020];
  cin >> n >> s >> m;
  tempt = s;
  for (int i = 0; i < n; i++) {
    data[i] = i + 1;
  }
  for (; count <= n; count++) { // 主要看这个for循环
    for (k = 1, q = 0; k <= m; q++) {
      if (data[(tempt + q - 1) % n] != 0)
        k++;
    }
    if (count != n) {
      cout << data[(tempt + q - 2) % n];
      cout << ' ';
    } else {
      cout << data[(tempt + q - 2) % n];
      return 0;
    }
    data[(tempt + q - 2) % n] = 0;
    for (j = 1, flag = 0; flag != 1; j++) {
      if (data[(tempt + q + j - 2) % n] != 0)
        flag = 1;
      else
        flag = 0;
    }
    tempt = (tempt + q + j - 2) % n;
  }
  return 0;
}

但是,强大的Clang编译器有各种错误检查。我们编译的时候加上“未定义行为检测器”试试:

$ clang++ a.cpp -Wall --std=c++17 -fsanitize=undefined
$ ./a.out
6 1 1 // 这行是输入的
a.cpp:14:9: runtime error: index -1 out of bounds for type 'int [2020]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior a.cpp:14:9 in 
1 2 3 4 5 6

会发现这个代码访问了数组里下标为-1的地方。

上面的几段代码有什么共同点呢?为什么在平台上的执行结果就和本地不一样呢?为什么这几段代码表现出来好像“平台不好用了”呢?要回答这个问题,首先要理解“未定义行为”的概念。

什么是未定义行为

在我们学习编程的过程中,可能都知道一些行为是“非法”的,是“错误”的,比如:

  1. 数组越界访问
  2. 解引用空指针
  3. 在对象的生命周期结束后访问对象
  4. 有返回类型的函数没有从return结束

但是,我们也仅仅知道这些行为是“错误”的,并不会知道这些行为为什么错误,会造成哪些后果。这些行为在c++语言标准里有一个名字:未定义行为(undefined behavior)。如:

控制流出有返回值的函数(除了 main)的结尾而不经过 return 语句是未定义行为。

翻译成人话就是,除了main之外的函数,如果他有返回值但是不经过return语句就结尾了,行为未定义。

标准中也明确给出了未定义行为的解释:

  • 未定义行为(undefined behavior,UB)——对程序的行为无任何限制。未定义行为的例子是数组边界外的内存访问,有符号整数溢出,空指针的解引用,在一个表达式中对同一标量多于一次的中间无序列点 (C++11 前)无序 (C++11 起)的修改,通过不同类型的指针访问对象,等等。编译器不需要诊断未定义行为(尽管许多简单情形确实会得到诊断),而且所编译的程序不需要做任何有意义的事。

甚至:

翻译成人话就是,如果发生未定义行为,编译器可以把这段代码编译为任何内容,包括但不限于删除你的所有文件,帮你定一杯咖啡,或者时间旅行。这些都是严格符合C++语言标准的。同时,不同的编译器也会对未定义行为采取不同的策略,所以很可能未定义行为的代码在不同编译器上运行结果不同。这样定义”未定义行为“就使得编译器优化更好:很多情况下既然结果未定义,就可以没有结果,因此编译器可以去掉未定义行为发生的代码分支,把代码优化为行为确定的结果。

不理解上面那段话什么意思?没关系,我们回过来看之前的那段代码:

template<typename T> bool ArrayList<T>::append(T const& value) {
  if(_size >= _capacity){ // border check;
    cout<<"SIZE "<<_size<<" CAP "<<_capacity;
    cout << " The List is overflow!" << endl;
    return false;
  }
  _elem[_size++] = value;
}

这段代码中实现了一个顺序表的append方法。看上去没什么问题:由于没有实现扩容算法,在末尾插入时首先要进行边界检查。如果边界检查通过,就把value放到elem里,并size++。但是,上面说了,这段代码的运行结果是if内条件永远成立,即使后面输出的时候size0cap2000。为什么会这样呢?这是不是编译器的Bug?

其实并不是。可能你已经注意到了:这个函数最后缺少return。因此,if内条件不成立的行为未定义。编译器发现了这一点,认为程序员会保证每次调用的时候if内条件都成立(否则就会出现未定义行为),因此直接去掉了if,把代码编译成了大概这个样子:

template<typename T> bool ArrayList<T>::append(T const& value) {
  cout<<"SIZE "<<_size<<" CAP "<<_capacity;
  cout << " The List is overflow!" << endl;
  return false;
}

重新回顾这个优化的过程中编译器的思路:

  1. if内条件不成立的话,行为未定义。
  2. 未定义行为不好,写代码的人会避免未定义行为。
  3. 因此,写代码的人会保证每次调用的时候if内条件均成立。
  4. 因此可以去掉if

可以发现,整个优化过程中编译器严格的遵守了C++语言标准:

  • 如果if内条件成立,这样的执行结果自然是正确的
  • 如果if内条件不成立,那么行为未定义。既然行为未定义,那任何行为都是正确的,因此我执行if内条件成立的代码也是正确的行为。

因此,错的不是编译器,是整个世界你。编译器没那么多bug,当你以为编译器出了bug,绝大部分情况下是你写了bug。

当然,go编译器里还是不少bug的,这个之后再说

因此,到现在你应该知道了什么是未定义行为。任何包括未定义行为的代码运行结果恰好符合你的预期都是巧合任何时候不应该写有未定义行为的代码未定义行为会导致代码在不同平台不同编译器上运行结果不一致

未定义行为的危害

未定义行为对于代码的危害上面已经说的差不多了。你可能会觉得:顶多代码运行结果是错的,又会怎么样呢?NAIVE!前面说道,当遇到未定义行为时:

编译器可以把这段代码编译为任何内容,包括但不限于删除你的所有文件,帮你定一杯咖啡,或者时间旅行。这些都是严格符合C++语言标准的。

不要以为“删除你的所有文件”是危言耸听:有人发现在clang编译器下你真的可能因为未定义行为而格式化你的硬盘:

image-20210404121149762

这段代码首先定义了一个函数f1。在这个函数中,i会不断累加,直到溢出。有符号数溢出是未定义行为。于是,编译器没有给f1生成任何代码,只生成了一个label。

从右侧的汇编可以看到,f1label下面的代码就是f2函数,这个函数会格式化你的硬盘(在这个例子并没有真的格式化,注释掉了。)学过汇编的同学可能会发现,由于f1内没有任何代码,所以调用f1会执行你本来不想执行的f2函数。BOOM!你的硬盘被格式化了。

llvm的issue tracker中有关这个 “bug”的讨论还在进行中。一部分人认为应该“修复”:

This means UB is a potential safety/security problem, and we really should do something about it.

还有一部分人认为不应该:

All sorts of UB manifests in lots of security issues, right? Buffer overruns and the like (I guess this is a buffer overrun, of sorts).

同时,有些人认为应该修复,理由是为了debug更方便。llvm的开发者回复:

It’s not generally that simple - deciding where/how to “recover” from UB would be pretty difficult.

The Clang-advised way to deal with this would be to compile with -fsanitize=undefined

https://godbolt.org/z/3aW69c

example.cpp:4:29: runtime error: signed integer overflow: 2147483647 + 1 cannot be represented in type ‘int’
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior example.cpp:4:29 in

大意是已经有足够强大的未定义行为检测器了(又一个体现clang比msvc/gcc之流强大的点),为了方便debug来改这个UB的行为不值得。

总之,不要写未定义行为,以及当你以为编译器错了,你错了。我的OJ同理,因为就是帮你调用编译器来编译代码而已……

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

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工大杯题解 - 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工大杯题解-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工大杯题解 - 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;
}